本篇的完整程式碼在這裡

How to implement Linked List in Javascript

要在 javascript 內寫 Linked List 會動用到 class constructor
如果對此概念不熟的話可以看這裡

Quickly recap concept of Class in js

這裡快速複習一下 class 在 js 中的寫法

• Create instance properties in the constructor
• Create child classes extends from parent class
• Write own method in the children classes

class Character {
    constructor(name, lifePoint) {
        this.name = name;
        this.lifePoint = lifePoint;
    }
    speak() {
        console.log(`${this.name} make a noise.`);
    }
}

class Human extends Character {
    constructor(name, lifePoint) {
        super(name, lifePoint);
    }
    greeting() {
        console.log(`Hi, I'm ${this.name}, nice to meet you.`);
    }
}

class Griffin extends Character {
    constructor(name, lifePoint) {
        super(name, lifePoint);
    }
    speak() {
        console.log(`Griffin ${this.name} is howling.`);
    }
}

const player1 = new Human("Mark", 100); 
const monster1 = new Griffin("Shadowclaw", 999);

monster1.speak(); // Griffin Shadowclaw howl.
player1.greeting(); // Hi, I'm Mark, nice to meet you.

Linked List Push method

建立名為 Node 的 class(因為 Linked List 由 Node 構成)
然後建立 class Linked List

初始化新的 Linked List 時是空的，所以head為 null 且 length=0
並在 Linked List 上寫 push method，來達成 push Node into excisting Linked List

push method 執行的內容：

• 建立新的 Node 到 Linked List 中
• 如果 Linked List 為空 / head of Linked List 為 null，則把 Linked List 的 head 指到新建立的 Node 上；當 Link List 的 head 非 null（表示 Link List 有其他 Nodes，但不知道有幾個 Nodes 所以用 while traverse ），則 traverse 到 last Node 並將 last Node 的 next 指到 newNode（而 newNode 則成為新的 last Node）

class Node{
    constructor(value){
        this.value = value;
        this.next=null;
    }
}

class LinkedList{
    constructor(){
        this.head = null;
        this.length = 0;
    }
    // add Nodes into LinkedList
    push(value){
        let newNode = Node(value);
        /* 
        this.length === 0 || this.head === null
        if there's no head then set newNode to head
        else traverse whole linked list and set head of currentNode to newNode
        */
        if(this.length === 0){
            this.head = newNode;
        }else{
            let currentNode = this.head;
            while(currentNode.head!==null){
                currentNode = currentNode.next;
            }
            currentNode.next = newNode;
        }
        this.length++;
    }
}

這樣就完成了 push，create new Linked List 並 push Nodes 看看

let nameLinkedList = new LinkedList();
nameLinkedList.push('Andrew');
nameLinkedList.push('Fiona');
nameLinkedList.push('Emily');

console.log(nameLinkedList);

Linked List Pop method

接下來寫 pop method

pop method 執行的內容：

跟 Array.pop 類似，將最後一個 Node pop 掉並 return the popped Node
有以下情況

• 如果 Linked List 沒有任何 Node，return null
• 如果 Linked List 只有ㄧ個 Node，set head of Linked List 為 null; length of Linked List 為 0，用 temp variable 將 popped Node 存起來並 return
• 如果 Linked List 有複數個 Node，traverse 到 lastNode 前一個 Node（newLastNode），將 newLastNode 的 next set to null; length of Linked List -1，用 temp variable 將 popped Nodes 存起來並 return

...
pop() {
     if (!this.head) {
         return null;
     } else if (this.length === 1) {
         // store this.head in temp
         let temp = this.head;
         this.head = null;
         this.length = 0;
         return temp;
      } else {
         let currentNode = this.head;
         // traverse to the Node which previous of last Node
         for (let i = 1; i < this.length - 1; i++) {
             currentNode = currentNode.next;
         }
         // set the next value of new last Node to null
         let temp = currentNode.next;
         currentNode.next = null;
         this.length--;
         return temp;
       }
}
...

試著 pop Nodes 看看

nameLinkedList.pop();
console.log(nameLinkedList);

這時候可以看到 nameLinkedList 原本最後的 Node 被 pop 出來，且 length of nameLinkedList 也減少了

其他資源

linked list data structure
https://www.geeksforgeeks.org/linked-list-data-structure/
types of linked list
https://www.geeksforgeeks.org/types-of-linked-list/