Java面試過程中，經(jīng)常會(huì)被問到數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的知識(shí)。對(duì)于工作多年的程序員來說，這些理論的知識(shí)可能已經(jīng)忘得差不多了吧，所以面試前還是有必要臨時(shí)抱抱佛腳的。

　　一、線性表(重點(diǎn))

　　線性表是由N個(gè)元素組成的有序序列，也是最常見的一種數(shù)據(jù)結(jié)構(gòu)。重點(diǎn)有兩個(gè)數(shù)組和鏈表。

　　1、數(shù)組

　　數(shù)組是一種存儲(chǔ)單元連續(xù)，用來存儲(chǔ)固定大小元素的線性表。java中對(duì)應(yīng)的集合實(shí)現(xiàn)，比如ArrayList。

　　2、鏈表

　　鏈表又分單鏈表和雙鏈表，是在物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中指針的鏈接次序?qū)崿F(xiàn)的。java中對(duì)應(yīng)的集合實(shí)現(xiàn)，比如LinkedList。

　　二、棧與隊(duì)列

　　1、棧

　　棧，是一種運(yùn)算受限的線性表，重點(diǎn)掌握其后進(jìn)先出的特點(diǎn)。表的末端叫棧頂，基本操作有push(進(jìn)棧)和pop(出棧)。java中stack就是簡單的棧實(shí)現(xiàn)。

　　2、隊(duì)列

　　隊(duì)列也是一種操作受限制的線性表，重點(diǎn)掌握其先進(jìn)先出的特點(diǎn)。表的前端只允許進(jìn)行刪除操作，表的后端進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。java中很多Queue的實(shí)現(xiàn)，消息中間件的隊(duì)列本質(zhì)也是基于此的。

　　三、樹(重點(diǎn))

　　在非線性結(jié)構(gòu)里面，樹是非常非常重要的一種數(shù)據(jù)結(jié)構(gòu)。基于其本身的結(jié)構(gòu)優(yōu)勢，尤其在查找領(lǐng)域，應(yīng)用廣泛，其中又以二叉樹最為重要。樹的話我們這里只重點(diǎn)說一下二叉樹。

　　1、二叉搜索樹

　　二叉搜索樹又叫二叉查找樹，又叫二叉排序樹。性質(zhì)如下：(1) 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;(2) 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;(3) 左、右子樹也分別為二叉排序樹;(4) 沒有鍵值相等的結(jié)點(diǎn)。

　　2、平衡二叉樹

　　平衡二叉樹又叫AVL樹。性質(zhì)如下：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對(duì)值不超過1。

　　3、紅黑樹

　　紅黑樹是一種特殊的平衡二叉樹，它保證在最壞情況下基本動(dòng)態(tài)集合操作的事件復(fù)雜度為O(log n)。

　　紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時(shí)間復(fù)雜度相差不大的情況下，保證每次插入最多只需要三次旋轉(zhuǎn)就能達(dá)到平衡，實(shí)現(xiàn)起來也更為簡單。平衡二叉樹追求絕對(duì)平衡，條件比較苛刻，實(shí)現(xiàn)起來比較麻煩，每次插入新節(jié)點(diǎn)之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知。

　　四、圖

　　圖是比線性表和樹更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，面試中基本不太會(huì)問到，大家有興建的可以自己去了解下。

　　綜上，說了下常見的幾種數(shù)據(jù)結(jié)構(gòu)，上面的內(nèi)容大家不用死記硬背，重要的是理解，面試過程中能說出大體原理即可。

      以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java數(shù)據(jù)結(jié)構(gòu)面試題及答案”的內(nèi)容，希望對(duì)大家有幫助，如有疑問，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。

相關(guān)推薦

最新最全java面試題及答案（初級(jí)到高級(jí)）

史上最全的中高級(jí)JAVA工程師面試題及答案匯總

Java高級(jí)開發(fā)工程師面試題

2019史上最全java面試題題庫大全800題

哪有資深java工程師面試題