Data Structure - Linked List

Linked List 連結串列

Linked list 是一種常見的資料結構，其使用 node (節點) 來記錄、表示、儲存資料 (data)，並利用每個 node 中的 pointer 指向下一個 node，藉此將多個 node 串連起來，形成 Linked list，並以 NULL 來代表 Linked list的終點。

優點：

append、prepend： 只要對 head 或 tail 調整 pointer 所指向的 node 即可 O(1)，不需要像 array 一樣搬動其餘元素。

• 不需使用連續記憶體空間，不需事先指定串列大小

• 各節點資料型態並不一定要相同

缺點：

lookup： 沒有像 Array 的 index 那樣方便，若要找到特定node，需要從頭(head node) traverse，搜尋的時間複雜度為 O(n)。

insert、remove： node，需要先作 O(n) traverse 到特定 node 後，再作後續新增、刪除 node …的動作。

• 需要額外的記憶體空間來儲存指到下一個 node 的 pointer。

使用時機：

• 無法預期資料數量時，使用 Linked List 沒有 resize 的問題。

• 需要頻繁地新增/刪除資料時。

• 不需要快速存取查詢資料時。

Javascript Linked List：

建立 class

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    };
    this.tail = this.head;
    this.length = 1;
  }
}

let myLinkedList = new LinkedList(0);

append

class LinkedList {
  //...以上省略
  append(value) {
    const newNode = {
      value: value,
      next: null
    }
    //直接將最後一個 node 指向新的 node
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }
  //照順序打印所有value
  printList() {
    const array = [];
    let currentNode = this.head;
    while(currentNode !== null){
      array.push(currentNode.value)
      currentNode = currentNode.next
    }
    return array;
  }
}

myLinkedList.append(1);
myLinkedList.printList(1);

prepend

prepend(value) {
  const newNode = {
    value: value,
    next: null
  }
  // 將新節點 pointer 指向原本的 head，再將 head 變更為新節點 
  newNode.next = this.head;
  this.head = newNode;
  this.length++;
  return this;
}

insert

insert(index, value){
  //檢查輸入index是否存在
  if(index >= this.length) {
      console.log('yes')
      return this.append(value);
  }

  const newNode = {
    value: value,
    next: null
  }
  //找到要 insert 的上一個節點，將 pointer 指向新節點，新節點的 pointer 指向原來 index 上的節點
  const leader = this.traverseToIndex(index-1);
  const holdingPointer = leader.next;
  leader.next = newNode;
  newNode.next = holdingPointer;
  this.length++;
  return this.printList();
}

traverseToIndex(index) {
  let counter = 0;
  let currentNode = this.head;
  while(counter !== index){
    currentNode = currentNode.next;
    counter++;
  }
  return currentNode;
}

remove

remove(index) {   
  const leader = this.traverseToIndex(index-1);
  const unwantedNode = leader.next;
  leader.next = unwantedNode.next;
  this.length--;
  return this.printList();
}

indexOf

indexOf(value) {
  let currentNode = this.head;
  let index = 0;
  while(currentNode) {
    if(value === currentNode.value) {
      return index;
    }
    index++;
    currentNode = currentNode.next;
  }
  return -1;
}