線性表、順序表與鏈表：邏輯結構與存儲結構深度對比

線性表、順序表與鏈表：邏輯結構與存儲結構深度對比

線性表邏輯定義

線性表是 相同數據類型 的 有限序列（n≥0）。除首尾元素外，每個元素有且僅有一個直接前驅/後繼。特點：長度有限、邏輯有序、類型統一、僅關注邏輯關係。線性表是邏輯結構，順序表/鏈表是其存儲實現。

順序表（數組實現）

用連續內存塊存儲，支持靜態分配與動態擴容。邏輯下標從 1 起，物理下標從 0 起。

• 優勢：O(1) 隨機訪問、存儲密度高、局部性好；
• 劣勢：插入/刪除需移動元素 O(n)、容量固定或擴容拷貝開銷。

邊界處理（長度 len=7）：

// 插入位置 index ∈ [1, len+1]
for (i = len; i >= index; i--) items[i] = items[i-1];
// 刪除位置 index ∈ [1, len]
for (i = index; i < len; i++) items[i-1] = items[i];

鏈表（鏈式存儲）

節點定義：class Node { T item; Node next; }。允許離散內存，插刪只改指針 O(1)（定位除外），查找需遍歷 O(n)。

單鏈表核心操作

• 頭插法：新節點接舊頭，順序反轉；
• 尾插法：維護尾指針，順序一致；
• 指定位置插入：找前驅 p，s.next=p.next; p.next=s;（先斷後連）；
• O(1) 插入技巧：插到目標後再交換數據域；
• 刪除：p.next=q.next; q=null; 或數據域前移覆蓋。

雙鏈表

節點增設 prior，給定節點可 O(1) 插刪：

// p 後插 s
s.next = p.next; p.next.prior = s;
s.prior = p; p.next = s;

// 刪 p 後繼 q
p.next = q.next; q.next.prior = p;

循環鏈表與靜態鏈表

• 循環單鏈表：尾指向頭，單尾指針可 O(1) 訪問頭尾；
• 循環雙鏈表：頭 prior 指尾，尾 next 指頭；
• 靜態鏈表：數組模擬，指針為下標，next==-1 為終止。

順序表 vs 鏈表 總結

選型口訣：查多改少用順序，改多查少用鏈表；大小不明或頻繁擴容首選鏈表。