[數組 array] 連續空間存儲 與 [鏈表 linked list] 離散空間存儲 是兩種基本的數據結構,分別代表數據在計算機內存中的兩種存儲方式,兩者的特點呈現出互補的特性。
數組 array#
[數組 array] 是一種線性數據結構,其將相同類型元素存儲在連續的內存空間中。數組的長度是不可變的。
插入和刪除缺點:時間複雜度高 O (n),丟失元素、內存浪費。
典型應用:隨機訪問、排序和搜索、查找表、機器學習、數據結構實現。
鏈表 linked list#
[鏈表 linked list] 是一種線性數據結構,其中的每個元素都是一個節點對象,各個節點通過 “引用” 相連接。
引用記錄了下一個節點的內存地址。鏈表的設計使得各個節點可以被分散存儲在內存各處。
頭節點,尾節點,尾節點指向的是” 空 “。
鏈表因為保存引用,所以比數組佔用更多的內存空間。
// **單向**鏈表(singly linked list)
// **典型應用:棧與隊列、哈希表、圖**
class ListNode {
int val;
ListNode? next;
ListNode(int x) => val = x;
}
// **雙向**鏈表(doubly linked list)
// **典型應用(快速查找前/後元素):高級數據結構、瀏覽器歷史、LRU 算法。**
class ListNode {
int val;
ListNode? next;
ListNode? prev;
ListNode(int x) => val = x;
}
// **環形**鏈表(circular linked list)
// 和雙向鏈表一樣,區別是首尾相接
// **典型應用(周期性操作):時間片輪轉調度算法、數據緩衝區。**
class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode(int x) => val = x;
}