大廠面試必問之Java集合核心內容之數組和鏈表

?現在出去找工作，如果你不能很好的和面試官去聊聊Java基礎里面的算法和用到的數據結構，基本是沒戲的，所以本篇開始我們會給大家詳細的聊聊Java集合中的相關實現涉及到的數據結構和算法實現，本文先來介紹下最最簡單的數據結構，數組和鏈表。

一、數組

??數組是我們使用到的最簡單的一個數據結構,數組的使用

// 動態初始化：初始化時由程序員只指定數組長度，由系統為數組元素分配初始值
char c1[] = new char[5];
// 靜態初始化： 初始化時由程序員顯示置頂每個數組的初始值，由系統決定數組長度
char c2[] = new char[]{'E','D','U','Y','U'};
char c3[] = {'E','D','U','Y','U'};

??? 1
??? 2
??? 3
??? 4
??? 5

??具有如下的特點：

??? 內存地址連續，
??? 可以通過下標的成員訪問,下標訪問的性能高
??? 增刪操作帶來更大的性能消耗(保證數據越界的問題,需動態擴容)

二、鏈表

??鏈表也是線性的順序存儲數據。只是在內存地址上不是連續的，每一個節點里存到下一個節點的指針(Pointer)
1 單向鏈表

??單向鏈表(單鏈表)是鏈表的一種，它由節點組成，每個節點都包含下一個節點的指針，下圖就是一個單鏈表，表頭為空，表頭的后繼節點是"結點10"(數據為10的結點)，“節點10"的后繼結點是"節點20”(數據為10的結點)

??

然后我們來看下刪除鏈表的操作，比如刪除30這個節點

?

?在上面的結構基礎上我們再來添加一個節點到鏈表中

2 雙向鏈表

??雙向鏈表(雙鏈表)是鏈表的一種。和單鏈表一樣，雙鏈表也是由節點組成，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構造雙向循環鏈表。

??雙鏈表的示意圖如下：

??

雙向鏈表的具體實現可以參考

??? static final class Node {
?????? // 前一個節點
??????? volatile Node prev;

??????? // 后一個節點
??????? volatile Node next;

?? ??? ?// 鏈表節點存儲的具體數據
??????? volatile Thread thread;


??? }

??? 1
??? 2
??? 3
??? 4
??? 5
??? 6
??? 7
??? 8
??? 9
??? 10
??? 11
??? 12

??我們看看雙向鏈表刪除節點的操作，比如說下面這個單鏈表中我們要刪除"節點30"。

刪除之前：“節點20"的后繼節點為"節點30”，“節點30” 的前繼節點為"節點20"?！肮濣c30"的后繼節點為"節點40”，“節點40” 的前繼節點為"節點30"。

刪除之后：“節點20"的后繼節點為"節點40”，“節點40” 的前繼節點為"節點20"。

??

我們再來看看雙向鏈表添加節點的操作，比如說下面這個雙向鏈表在"節點10"與"節點20"之間添加"節點15"

添加之前：“節點10"的后繼節點為"節點20”，“節點20” 的前繼節點為"節點10"。

添加之后：“節點10"的后繼節點為"節點15”，“節點15” 的前繼節點為"節點10"?！肮濣c15"的后繼節點為"節點20”，“節點20” 的前繼節點為"節點15"。

~數據和鏈表的內容相對來說比較簡單，我們就給大家介紹到這里了