數據結構基本概念

相互之間存在一種或多種特定關系的數據元素集合。

(ER圖：實體關系圖)

數據對象中數據元素之間的關系

邏輯結構

1、集合結構

2、線性結構

3、樹形結構

4、圖形結構

下圖：從又到左對應1-4

物理結構

1、順序存儲結構

2、鏈式存儲結構

線性表

說明：線性表指的是邏輯結構、順序表和鏈表指的是存儲結構(也叫物理結構)。

概念：a1是a2的前驅，ai+1 是ai的后繼，a1沒有前驅，an沒有后繼，n為線性表的長度 ，若n==0時，線性表為空表

順序存儲

存儲位置連續，可以很方便計算各個元素的地址

如每個元素占C個存儲單元，那么有：

Loc(An) = Loc(A1)+(i-1)*C;

優缺點： 查詢效率高、插入刪除效率低

代表：Java中的ArrayList(底層數據結構采用的數組的方式)

鏈式存儲

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以是連續的，也可以是不連續的。

1、單向鏈表

2、雙向鏈表

雙向鏈表(LinkedList)由前驅、后繼、數據三部分組成，并且尾部節點和頭部節點未連接起來。

3、循環鏈表

將單鏈表中終端結點的指針端由空指針改為指向頭結點，就使整個單鏈表形成一個環，這種頭尾相連的單鏈表稱為單循環鏈表，簡稱循環鏈表

4、雙向循環鏈表

雙向循環鏈表是單向循環鏈表的每個結點中，再設置一個指向其前驅結點的指針域。(LinkedHashMap)

對于空的雙向循環鏈表

雙向循環鏈表插入過程，p和p->表示兩個節點。

雙向循環鏈表刪除。(可參考LinkedList源碼中的remove方法)

參考：

https://www.cnblogs.com/ysocean/p/7928988.html