Skip to main content

[資料結構] Array and Linked List

TL;DR#

Singly Linked List#

  • 每個 Node 會包含 valuenext 的資訊
  • Linked List 會包含 head, tail 的資訊
  • Linked List 包含 append, prepend, insert, remove, printList 的方法
class NodeType {
value: number;
next: NodeType | null;
constructor(value: number) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
head: NodeType;
tail: NodeType;
length: number;
constructor(value: number) {
const theNode = new NodeType(value);
this.head = theNode;
this.tail = theNode;
this.length = 1;
}
append(value: number) {}
prepend(value: number) {}
insert(index: number, value: number) {}
remove(index: number) {}
printList() {}
private traverseToIndex(index: number) {}
}

Doubly Linked List#

  • 每個節點(Node)包含了 next, prevvalue
  • Linked List 會紀錄 head, tail 的資訊
  • Linked List 實作了 append, prepend, insert, remove printList 的方法
class NodeType {
value: number;
next: NodeType | null;
prev: NodeType | null;
constructor(value: number) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
head: NodeType;
tail: NodeType;
length: number;
constructor(value: number) {
const newNode = new NodeType(value);
this.head = newNode;
this.tail = newNode;
this.length = 1;
}
append(value: number) {}
prepend(value: number) {}
insert(index: number, value: number) {}
remove(index: number) {}
private traverseToIndex(index: number) {}
printListFromHead() {}
printListFromTail() {}
}
export {};

Doubly Linked List#

Imgur

  • Singly Linked List 和 Doubly Linked List 的差別在於,Singly Linked List 的每一個 Node 只會紀錄 next 是誰,因此只能從頭開始一路往後;而 Double Linked List 在 Node 中則會同時紀錄 next 和 previous,因此可以由後往前找:
    • Singly List 使用較少的記憶體空間,appen 和 prepend 時會快一些,但沒辦法從後往前 traverse,search, insert, delete 會花比較多時間
    • Doubly Linked List 使用較多的記憶體空間,append 和 prepend 會比較慢一些,但可以由前往後 traverse,search, insert, delete 時會花較少時間
  • Doubly Linked List 和 Array 有一個差異在於,Array 會被配置到一連串的記憶體空間,而 Linked List 的各個節點(Node)則是會分散在記憶體的不同位置,因此在做疊代(iterate)的時候,相較之下速度會稍微慢些。
  • Doubly Linked List 和 Hash Table(相較於 Array)都較容易進行增減,但 Linked List 又多了順序的概念。
  • Linked List 和 Array 雖然都有順序的概念在,但如果我們想要直接從某個 Node 開始往前或往後找時,Linked List 會比 Array 容易(例如,瀏覽器的上一頁或下一頁)
  • Doubly Linked List 中,會紀錄該 Linked 的 headtail
  • 每一個 Node 則會紀錄它的 value, prevnext
  • 其中會包含的方法為:
    • addToHead, addToTail
    • removeHead, removeTail
    • search, indexOf

Big O Notation#

Constant Time - O (1)#

  • prepend:新增/移除 Head
  • append:新增/移除 Tail

Linear Time - O (n)#

  • lookup:搜尋元素是否存在、搜尋元素的 index 位置
  • Insert, delete:元素的新增和刪除
tip

雖然 doubly linked list 和 singly linked list 在 Time Complexity 上的 Big O Notation 是相同的,但實際上 doubly linked list 會更快一些。

Memory Manage Benefits#

使用 Linked List 的資料結構可以更有效率的使用記憶體,因為每一個元素都是獨立,彼此之間是透過 next 和 prev 來關聯在一起:

Imgur

Sample Code#

data-structures-in-javascript @ PJCHENder Github

Singly Linked List#

class NodeClass {
value: number;
next: NodeClass | null;
constructor(value: number) {
this.value = value;
this.next = null;
}
}
class LinkedList {
head: NodeClass;
tail: NodeClass;
length: number;
constructor(value: number) {
const newNode = new NodeClass(value);
this.head = newNode;
this.tail = newNode;
this.length = 1;
}
append(value: number) {
const newNode = new NodeClass(value);
// this.tail 是指稱到某個 Node
this.tail.next = newNode;
this.tail = newNode;
this.length++;
return this;
}
prepend(value: number) {
const newNode = new NodeClass(value);
newNode.next = this.head;
this.head = newNode;
this.length++;
return this;
}
insert(index: number, value: number) {
const newNode = new NodeClass(value);
const temp = this.traverseToIndex(index - 1);
newNode.next = temp.next;
temp.next = newNode;
return this;
}
remove(index: number) {
const temp = this.traverseToIndex(index - 1);
if (temp.next === null) {
throw new Error('the index if over the length of linked list');
}
temp.next = temp.next.next;
}
private traverseToIndex(index: number) {
let temp = this.head;
let i = 0;
while (i !== index) {
if (temp.next === null) {
throw new Error('the index if over the length of linked list');
}
temp = temp.next;
i++;
}
return temp;
}
printList() {
const list: number[] = [];
let currentNode: NodeClass | null = this.head;
while (currentNode !== null) {
list.push(currentNode.value);
currentNode = currentNode.next;
}
return list;
}
}
// 2 -> 3 -> 1 -> 10 -> 5 -> 16
const myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);
myLinkedList.prepend(2);
myLinkedList.insert(1, 3);
myLinkedList.remove(3);
console.log(myLinkedList.printList());

Doubly Linked List - Started Template#

/* eslint-disable */
function LinkedList() {
this.head = null;
this.tail = null;
}
function Node({ value, next, prev }) {
this.value = value;
this.next = next;
this.prev = prev;
}
// 輸入 value 後,把該值添加到 Linked List 的最前方
LinkedList.prototype.addToHead = function addToHead(value) {
/* ... */
};
// 輸入 value 後,把該值添加到 Linked List 的最後方
LinkedList.prototype.addToTail = function addToTail(value) {
/* ... */
};
// 移除 Linked List 的第一個 Node,若 Head 存在則回傳被移除的值,否則回傳 null
LinkedList.prototype.removeHead = function removeHead() {
/* ... */
};
// 移除 Linked List 的最後一個 Node,若 Head 存在則回傳被移除的值,否則回傳 null
LinkedList.prototype.removeTail = function removeTail() {
/* ... */
};
// 輸入 value 後,搜尋此 LinkedList 中是否有此值
// 找不到的話回傳 null,否則回傳找的的值
LinkedList.prototype.search = function search(searchValue) {
/* ... */
};
// 列出所有等同於 searchValue 的 indexes
LinkedList.prototype.indexOf = function indexOf(searchValue) {
/* ... */
};
module.exports = {
LinkedList,
Node,
};

參考#

Last updated on