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)。

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

　　四、圖

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

　　綜上，說了下常見的幾種數據結構，上面的內容大家不用死記硬背，重要的是理解，面試過程中能說出大體原理即可。

      以上就是動力節點Java培訓機構小編介紹的“Java數據結構面試題及答案”的內容，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為你服務。

相關推薦

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

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

Java高級開發工程師面試題

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

哪有資深java工程師面試題