java常見數據結構面試

Java面試過程中，經常會被問到數據結構和算法相關的知識。對于工作多年的程序員來說，這些理論的知識可能已經忘得差不多了吧，所以面試前還是有必要臨時抱抱佛腳的。

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

一、線性表（重點）

線性表是由N個元素組成的有序序列，也是最常見的一種數據結構。重點有兩個數組和鏈表。

1、數組

數組是一種存儲單元連續，用來存儲固定大小元素的線性表。java中對應的集合實現，比如ArrayList。

2、鏈表

鏈表又分單鏈表和雙鏈表，是在物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。java中對應的集合實現，比如LinkedList。

二、棧與隊列

1、棧

棧，是一種運算受限的線性表，重點掌握其后進先出的特點。表的末端叫棧頂，基本操作有push（進棧）和pop（出棧）。java中stack就是簡單的棧實現。

2、隊列

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

三、樹（重點）

在非線性結構里面，樹是非常非常重要的一種數據結構。基于其本身的結構優勢，尤其在查找領域，應用廣泛，其中又以二叉樹最為重要。樹的話我們這里只重點說一下二叉樹。

1、二叉搜索樹

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

2、平衡二叉樹

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

3、紅黑樹

紅黑樹是一種特殊的平衡二叉樹，它保證在最壞情況下基本動態集合操作的事件復雜度為O（log n）。

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

四、圖

圖是比線性表和樹更復雜的數據結構，面試中基本不太會問到，大家有興建的可以自己去了解下。