1. 資料結構三要素
1）邏輯結構 指的是資料間的邏輯關係，與資料的儲存無關，獨立於計算機之外。它又分為線性結構和非線性結構
線性結構：線性表，棧，佇列，串，陣列和廣義表非線性結構：樹，圖，集合2）儲存結構 是邏輯結構的儲存映像，就是資料間的關係在計算機中的表現形式。也成為物理結構。它又分為 4 類：順序儲存 ，鏈式儲存，索引儲存和雜湊儲存
順序儲存：把邏輯上相鄰的元素儲存在物理位置也相鄰的儲存單元裡鏈式儲存：不要求物理位置的相鄰，藉助指示元素儲存地址的指標表示元素之間的邏輯關係索引儲存：在儲存元素資訊的同時，新增附加的索引表，透過索引對節點進行操作雜湊儲存：也稱 Hash 儲存，根據結點的關鍵字透過雜湊函式計算出結點的儲存地址相同的邏輯結構在計算機裡可以用不同的儲存結構實現。比如邏輯結構中的線性結構，可以用陣列（順序儲存）或單向連結串列（連結儲存）來實現。
3）資料運算： 施加在資料上的運算（包括定義與實現）。運算的定義是針對邏輯結構，運算的實現是針對物理結構
2. 線性表的定義
線性表定義：
具有相同資料型別的 n 個數據元素的有限序列線性表是一種邏輯結構，表示元素之間一對一的邏輯關係使用線性表儲存資料的方式可以這樣理解，把所有資料用一根線兒串起來，再儲存到物理空間中
下圖中，左側是“串”起來的資料，右側是空閒的物理空間。把這 “一串兒” 資料放置到物理空間，我們可以選擇以下兩種方式：
將具有“一對一”關係的資料“線性”地儲存到物理空間中，這種儲存結構就稱為線性儲存結構：
① 順序表（如上圖左邊）：將資料依次儲存在連續的整塊物理空間中② 連結串列（如上圖右邊）：資料分散的儲存在物理空間中，透過一根線儲存著它們之間的邏輯關係 單鏈表 雙鏈表 迴圈單鏈表 迴圈雙鏈表下面詳細講解這兩種儲存結構
3. 順序表① 順序表定義線性表的順序儲存。邏輯上相鄰的兩個元素在物理位置上也相鄰
陣列就是順序表，下標一般從 0 開始：
順序表的特點：
隨機訪問（透過首地址和元素序號可在時間 O(1) 內找到元素）插入和刪除需要移動大量元素儲存密度高，每個結點只儲存資料元素② 順序表基本操作Ⅰ 插入在陣列 a 的第 i 個位置 (下標 i-1) 插入元素 e
// 第i個元素及其之後的元素後移for (int j = a.length; j >= i; j--) a[j] = a[j - 1];a[i - 1] = e;length++;複製程式碼
// 從第 i 個位置元素前移for(int j = i; j < a.length; j++) a[j-1] = a[j];length --;複製程式碼
for (int i = 0; i < a.length; i++) if (a[i] == e) return i;複製程式碼線性表的鏈式儲存。邏輯上相鄰的兩個元素在物理位置不一定也相鄰
例如，使用連結串列儲存 {1,2,3}，資料的物理儲存狀態如下圖所示：
可以看到，上圖根本無法體現出各資料之間的邏輯關係。對此，連結串列的解決方案是，每個資料元素在儲存時都配備一個指標，用於指向自己的直接後繼元素。如下圖所示：
當然，指標可以指向自己的直接後繼元素，也可以指向自己的直接前驅元素。為此，連結串列可分為：
單鏈表（指標指向自己的直接後繼元素）雙鏈表（指標指向自己的直接後繼元素和直接前驅元素）迴圈單鏈表（指標指向自己的直接後繼元素，表尾節點的指標指向頭節點）迴圈雙鏈表（指標指向自己的直接後繼元素和直接前驅元素，表尾節點的指標指向頭節點）透過以上大家應該也知道了，連結串列中每個資料的儲存都由以下兩部分組成：
資料域：資料元素本身指標域：指向該元素直接後繼/前驅/...元素的指標
上圖所示的結構在連結串列中稱為節點。也就是說，連結串列實際儲存的是一個一個的節點，真正的資料元素包含在這些節點中，舉個單鏈表的例子：
當然，上所示的連結串列結構並不完整。一個完整的連結串列需要由以下幾部分構成：
頭指標：一個普通的指標，它的特點是永遠指向連結串列第一個節點的位置。很明顯，頭指標用於指明連結串列的位置，便於後期找到連結串列並使用表中的資料節點：連結串列中的節點又分為頭節點、首元節點和其他節點 頭節點：其實就是一個不存任何資料的空節點，通常作為連結串列的第一個節點。對於連結串列來說，頭節點不是必須的，它的作用只是為了方便解決某些實際問題 首元節點：由於頭節點（也就是空節點）的緣故，連結串列中稱第一個存有資料的節點為首元節點。首元節點只是對連結串列中第一個存有資料節點的一個稱謂，用於和頭節點進行區分，沒有實際意義 其他節點：連結串列中其他的節點因此，一個儲存 {1,2,3} 的完整單鏈表結構如圖所示：
引入頭節點的優點：
連結串列的首元節點的操作與其他位置的元素操作一樣，無須進行特殊處理無論連結串列是否為空，其頭指標都是指向頭節點的非空指標，空表和非空表的處理得到了統一② 單鏈表Ⅰ 定義單鏈表就是指標指向自己的直接後繼元素的連結串列
以 Java 為例，我們自定義一個單鏈表結構：
public class Node{ private T t; private Node next; ......}複製程式碼單鏈表可以解決順序表需要大量連續儲存空間的缺點，但單鏈表附加指標域，也存在浪費儲存空間的缺點
單鏈表是非隨機儲存的儲存結構：即不能直接找到表中某個特點的結點。需要從頭開始遍歷。
單鏈表訪問前驅的時間複雜度為 O(n)，訪問後繼 O(1)
Ⅱ 基本操作頭插法在頭節點 L 的後面插入節點 s，即 s 節點成為當前連結串列的首元節點
頭插法的讀入順序和生成順序相反
s.next = L.next;L.next = s;複製程式碼在連結串列最後一個節點 r 的後面插入節點 s，即 s 節點成為當前連結串列的最後一個節點
尾插法的讀入順序和生成順序相同
r.next = s;r = s; // s 節點成為連結串列的最後一個節點複製程式碼p 節點之後插入 s 節點
雙鏈表訪問前驅和後繼結點時間複雜度都是 O(1)
以 Java 為例，我們自定義一個雙鏈表結構：
public class Node{ private T t; private Node next; private Node prior; ......}複製程式碼p 節點之後插入 s 節點
上圖中 2、3 順序可調換
判空條件：表尾結點的 next 是否是等於頭指標
④ 迴圈雙鏈表迴圈雙鏈表就是表尾節點的指標指向頭節點的雙鏈表
5. 順序表和連結串列的比較1）存取方式
順序表可以順序存取，也可以隨機存取連結串列只能從表頭順序存取元素2）邏輯結構與物理結構
對於按值查詢，順序表無序時，兩者的時間複雜度均為 O(n)；順序表有序時，可採用折半查詢，此時的時間複雜度為 O(log2n) 對於按序號查詢，順序表支援隨機訪問，時間複雜度僅為 O(1)，而連結串列的平均時間複雜度為 O(n)。順序表的插入、刪除操作，平均需要移動半個表長的元素 連結串列的插入、刪除操作，只需要修改相關結點的指標域既可。由於連結串列的每個結點都有指標域，所以在儲存空間上要比順序表付出的代價大，儲存密度不夠大。4）空間分配
順序儲存在靜態儲存分配情況下，一旦儲存空間裝滿就不能擴充，若再加入新元素，則會出現溢位，所以需要預先分配足夠大的儲存空間。預先分配過大，可能會導致順序表候補大量閒置；預先分配過小，又會造成溢位。 動態儲存分配雖然儲存空間可以擴充，但需要移動大量元素，導致操作效率降低，而且若記憶體中沒有更大的連續儲存空間，則會導致分配失敗連結串列只在需要時申請分配，高效靈活轉載：https://juejin.cn/post/6911580913004789768