?現在出去找工作,如果你不能很好的和面試官去聊聊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"。

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