Linked List為抽象的資料結構,概念有點像三國的連環船,一艘船(節點)連結著下一艘船(節點),每個節點除了擁有自己的值之外也記錄自己的下一個節點是指向哪個節點,而Linked List又分為下列幾種
單向的Linked List,最後一個節點next指向null
最後一個節點的next指向第一個,形成一個循環
雙向的Linked List,可以看到節點除了紀錄next指向誰,也會記錄是誰指向自己
Linked List為不連續的記憶體空間,因此在存放每個元素的同時 ,也會記錄下一個元素存放的位置,但假設今天想要取得鏈結串列的最後一個元素時 ,就必須從第一個元素開始讀取, 逐一讀到最後一個,讀取效率較為不理想,但是做插入和刪除資料的時候非常快,時間複雜度只有O(1)。
Array為連續的記憶體空間,所以可以直接用索引(index)來取得需要的值 ,讀取相當的快,不過假如要刪除一個元素或新增一個元素都會影響到其他元素的排序,統一往後或是往前挪,因此時間複雜度為O(n),n為陣列長度。
下圖是操作兩者所需的時間複雜度比較
不需要快速的查詢資料以及有頻繁新增刪除資料的需求
創建一個linked list,初始節點的值為apple並且將next指向banana
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor(value) {
//初始的節點命名為head
this.head = new ListNode(value);
}
add(value) {
const newNode = new ListNode(value);
//head的next指向新的節點
this.head.next = newNode;
console.log("head", this.head);
}
}
let linkedList = new LinkedList("apple");
linkedList.add("banana");
成功做出一個Linked List!