java常見(jiàn)數(shù)據(jù)結(jié)構(gòu)面試

java常見(jiàn)數(shù)據(jù)結(jié)構(gòu)面試

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

其實(shí)面試官的要求也很簡(jiǎn)單，只要大體懂得其原理即可，并不太會(huì)深究，尤其對(duì)社招。校招在此不做討論，畢竟剛出校園，理論知識(shí)正值巔峰，哈哈。

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

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

1、數(shù)組

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

2、鏈表

鏈表又分單鏈表和雙鏈表，是在物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?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就是簡(jiǎn)單的棧實(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ì)也是基于此的。

三、樹(shù)（重點(diǎn)）

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

1、二叉搜索樹(shù)

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

2、平衡二叉樹(shù)

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

3、紅黑樹(shù)

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

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

四、圖

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