資料結構-LinkedList

什麼是 Linked List?

它是一個擁有數個 node 的 list，這些 node 與 node 之間彼此會 link 一起。

有兩種 linked list，分別為 singly linked list 和 doubly linked list:
singly linked list
每一個 node 只含有緊跟著在其後方的 node 的參照(reference)資訊。
doubly linked list
每一個 node 會含有在其前方的 node 和在其後方的 node 的參照資訊。

上方圖片，
如果是 singly linked list 則每個 node 只會含有藍色箭頭的資訊，
若是 doubly linked list 則每個 node 會含有藍色箭頭和紅色箭頭的資訊。

Linked List 含有的資訊

每一個 LinkedList 含有的資訊

Linked list 只會含有兩個 pointer 的資訊，分別為 head pointer 和 tail pointer。
Linked list 會透過 head pointer 和 tail pointer 來分別記住 head node 和 tail node 的資訊，如下圖所示:

每一個 node 含有的資訊

如果是在一個 doubly linked list 底下的 node 的話，每一個 node 會含有以下三種屬性

value: 該 node 帶有的資訊
next: 下一個 node 的參照
prev: 上一個 node 的參照
如果它是在一個 singly linked list 底下的 node ，就不會有 prev 這個資訊囉。

Linked List 主要會執行哪些操作?

• 在既有的 linked list 的 head node 前方新增一個 node，並將既有的 head pointer 指向這個新增的 node。
• 在既有的 linked list 的 tail node 後方新增一個 node，並將既有的 tail pointer 指向這個新增的 node。
• 刪除既有 linked list 的 head node，並將既有的 head pointer 指向刪除 head node 的 linked list 的第一個 node。
• 刪除既有 linked list 的 tail node，並將既有的 tail pointer 指向刪除 tail node 的 linked list 的最後一個 node。
• 搜尋某個資料是否有出現在 linked list 的 node 中。

Big O of LinkedList

Constant Time - O(1)

• add/removing head
• adding/removing tail

Linear time complexity - O(n)

• Search

Memory Management Benefits

使用 Linked List 來儲存資料的好處在於，
它不需要一個連續的記憶體空間才有辦法將資料存起來，因為 Linked List 的 node 彼此之間有用 prev 和 next 串聯起來，所以，它不需要是一個連續的記憶體空間，也能完整儲存資料。
如果今天是一個含有 [a, b, c, d] 4 個元素的陣列，那它就需要一個可以儲存 4 個元素的連續記憶體空間，如下圖所示

接下來我想要新增第五個元素到這個陣列裡面，假設 105 這個空間是可以被儲存的那當然可以直接將新元素儲存在 105 的位置，但是，如果 105 已經被占用了，那是不是就需要重找一個由 5 個連續位址所組成的記憶空間呢。

由此就可以看出 Linked List 在分配記憶體空間上比起陣列是更方便且有效率的，以下是 Linked List 在記憶體空間裡儲存的樣子。

Linked List 和 Array 的差別

	Linked List	Array
記憶體	不需要連續的記憶體空間	需要一個連續的記憶體空間
新元素加入/刪除	1. 若是新增/刪除 tail node 或 head node 相對較快，時間為 O(1) 2. 但若是有指定位置的話，時間就是 O(n)	相對慢，新增和刪除都是 O(n)
資料取出	相對慢，因為有可能需要遍尋整個 Linked List，時間為 O(n)	相對快，可以直接指定元素的 index 取出，時間為 O(1)

Source Code

以下為 Doubly Linked List 的程式碼

function LinkedList() { // the Constructor of LinkedList
  this.head = null;
  this.tail = null;
}

function Node(value, prev, next) { // the Constructor of Node
  this.value = value;
  this.prev = prev;
  this.next = next;
}

LinkedList.prototype.addToHead = function (value) {
  /*
  新的 head node，它的 next 指向舊有的 head node
  也因為它是 head node 所以它的 prev 是指向 null，表示前面沒有 node
  */
  const newNode = new Node(value, null, this.head);

  /*
  如果 LinkedList 裡面已經有存在 node 了，就代表 head pointer 一定有指向某個 node 的位址，
  所以，可以透過 head pointer 是否有指向位址來判斷是否有存在 node，
  若有，就將舊有的 head node pointer 的 prev 屬性指向新的 head node，
  若沒有，就將 tail pointer 指向新的 head node。
  */
  if (this.head) this.head.prev = newNode;
  else this.tail = newNode;
  this.head = newNode; // 最後，將 head pointer 指向新的 head node
};

LinkedList.prototype.addToTail = function (value) {
  /*
  新創建的 tail node ，因為是最後一個 node ，
  所以它的 `next` 為 `null`，因為後面沒有其他 node 了，
  所以它的 `prev` 為 `this.tail`，因為它即將變成最後一個 node，所以，它的前一個 node 會指向舊的 tail node。
  */
  const newNode = new Node(value, this.tail, null);

  /*
  透過 this.tail 是否有值來判斷是否 LinkedList 裡已有存在 node，
  若有，則將既有的 tail node 的 next 屬性指向 newNode，
  若沒有，則將 LinkedList 的 head pointer 指向 newNode，因為只有一個 node 的話， head pointer 和 tail pointer 都會指向這一個 node，
  最後，將 LinkedList 的 tail pointer 指向 newNode，因為，它是新的 tail node。
  */
  if (this.tail) this.tail.next = newNode;
  else this.head = newNode;
  this.tail = newNode;
};

LinkedList.prototype.removeHead = function () {
  /*
  判斷如果 LinkedList 裡面沒有任何 node 存在的話，就直接回傳 null，
  不需要再執行下面的程式碼
  */
  if (!this.head) return null;

  const value = this.head.value; // 若有 head node 存在 LinkedList 中的話，將這個 head node 的 value 值存起來。

  /*
  將 LinkedList 的 head pointer 指向原本的 head node 的 next 指向的 node，
  將它設成 LinkedList 的新 head node。
  */
  this.head = this.head.next;

  /*
  完成更改 LinkedList 的新 head node 後，判斷是否這個新 head node 存在，
  因為，有可能 LinkedList 原本就只含有一個 node，那將 LinkedList 的 head pointer 指向這個唯一 node 的 next 位址，就會是 null，
  若新的 head node 存在，則將新 head node 的 prev 指向 null，因為 head node 前面不會有 node 了。
  若新的 head node 不存在，則將 LinkedList 的 tail pointer 也指向 null，因為代表 LinkedList 裡，已經不存在任何的 node 了。
  */
  if (this.head) this.head.prev = null;
  else this.tail = null;

  return value; // 回傳被刪除 node 的 value 值。
};

LinkedList.prototype.removeTail = function () {
  /*
  判斷是否現在 LinkedList 是否含有任何 node，如果不含任何 node，那 LinkedList 的 tail pointer 一定會是指向 null，
  所以，若 tail pointer 為 null 那就不繼續執行後面的程式碼，直接回傳 null。
  */
  if (!this.tail) return null;
  const value = this.tail.value; // 將既有的 LinkedList 的 tail pointer 指向的 node 的 value 值記起來。

  /*
  將 LinkedList 既有的 tail pointer 的 prev 屬性指向的 node 位址，設給 LinkedList 的 tail pointer，
  這樣一來， LinkedList 的 tail node 就變成既有 linkedList 的倒數第二個 node。
  */
  this.tail = this.tail.prev;

  /*
  完成更改 tail pointer 的指向後，
  我們就要檢查是否這個新的 tail pointer 是否有值，
  如果 tail pointer 有值，那就代表 linkedList 還有含有 node，那就要將 tail pointer 的 next 屬性指向 null，因為， LinkedList 的 tail node 後面不會接任何 node，
  如果 tail pointer 指向 null，那就代表 LinkedList 已經不含有任何 node，這個時候，就要連帶地將 LinkedList 的 head pointer 指向 null，因為已經不存在任何 node 了。
  */
  if (this.tail) this.tail.next = null;
  else this.head = null;

  return value; // 回傳被刪除的 node 的 value 值
};

LinkedList.prototype.search = function (searchValue) {
  let currentNode = this.head; // 將 LinkedList 的 head node 當作查詢的起點。

  /* 
  若 currentCode 有值，則進入到 while 迴圈，
  若 currentCode 的 value 等於要搜尋的值 searchValue 那就回傳 currentCode 的 value 值，
  若 currentCode 的 value 不等於要搜尋的值 searchValue，那就將 currentCode 設定成 currentCode.next 指向的下一個 node。
  */
  while (currentNode) {
    if (currentNode.value === searchValue) return currentNode.value;
    currentNode = currentNode.next;
  }

  return null; // 若 LinkedList 裡，沒有任何 node 的 value 符合 searchValue 那就回傳 null。
};

LinkedList.prototype.indexOf = function (searchValue) {
  let result = [];
  let index = 0;
  let currentNode = this.head;
  while (currentNode) {
    if (currentNode.value === searchValue) result.push(index);
    currentNode = currentNode.next;
    index++;
  }
  return result; // 回傳儲存所有符合搜尋值的元素的 index 的陣列
};

const ll = new LinkedList();
ll.addToHead(1000);
ll.addToHead(2000);
ll.addToHead(3000);
ll.addToHead(1000);
ll.addToHead('start');
ll.addToTail(4000);
console.log(ll.head.value, ll.tail.value); // start  4000
console.log(ll.search('end'), ll.search('start')); // null start
ll.removeHead();
console.log(ll.head.value, ll.tail.value); // 1000 4000
console.log(ll.indexOf(1000)); // [0, 3]

Reference Link

• Learning Data Structures in JavaScript from Scratch by Eric Traub @ Udemy
• https://pjchender.dev/dsa/dsa-array-linked-list/
• Describe the way of allocation of array