---
tags: 資料結構, LeetCode
disqus: HackMD
---

# 鏈結串列(Linked list)

:::spoiler 文章目錄
[toc]
:::

## 介紹

鏈結串列是線性的數據結構`(linear collection)`，與陣列不同，鏈結的元素不存儲在連續位置，元素使用指針鏈接。它們包括一系列連接的節點。每個節點存儲數據和下一個節點的位置(如下圖所示)，便於追加或刪除，但儲存數據很費時。


### 優缺點

#### 優點

* 新增以及刪除資料比陣列來的更快
* 動態陣列，不會有陣列重新定義大小問題

#### 缺點

* 數據儲存不連續記憶體位置
* 訪問指定位置必須從頭開始查找
* 需而外記憶體空間儲存儲存指標

### 複雜度

(圖片取自於[bigocheatsheet](https://www.bigocheatsheet.com/))

#### 時間複雜度

| 動作 | 時間複雜度 |
| ----| ---------- |
| 插入 | $O(N)$ \/ $O(1)$ 插入頭節點 |
| 刪除 | $O(N)$ \/ $O(1)$ 刪除頭節點 |
| 搜尋 | $O(N)$ |
| 訪問index | $O(N)$ |

#### 空間複雜度

$O(n)$

其中 `n` 是列表中元素的數量，因為列表中的每個節點都需要內存來存儲其數據和指向下一個節點的指針。

### 常見種類

* 單向鏈結串列（Singly Linked List）
* 雙向鏈結串列（Doubly Linked List）
* 迴圈鏈結串列（Circularly Linked List）

#### 單向鏈結串列（Singly Linked List）

每兩個節點間只有一個單向的鏈結。

(圖片取自於[types-of-linked-list](https://www.geeksforgeeks.org/types-of-linked-list/))

#### 雙向鏈結串列（Doubly Linked List）

帶有兩個指標指向前後數據，缺點是必須增加數據儲存領域，追加數據以及刪除數據時，要變更方向的指標也變多了。

* 查找值為`Singly Linked List`一半時間(平均)
* 可從前往後讀取，或從後往前讀取

(圖片取自於[types-of-linked-list](https://www.geeksforgeeks.org/types-of-linked-list/))

#### 迴圈鏈結串列（Circularly Linked List）

沒有頭尾概念，用於想維持最新數據為固定數量時。

(圖片取自於[types-of-linked-list](https://www.geeksforgeeks.org/types-of-linked-list/))

## 實作鏈結串列

### 單向鏈結串列（Singly Linked List）

以下使用 `JavaScript` 實作

#### 建立Node

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

#### 建立鏈結串列

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
}

#### 新增`push`方法

> 將新節點新增至末端

1. 建立`Node`，`value`為傳入的值
2. 如果head為空，則將`head`設置為新節點
3. 否則，使用一個`while`循環，遍歷`Linked List`直到找到最後一個節點
4. 最後一個節點的`next`指向新節點
5. 增加`Linked List`的長度

(圖片來自於[visualgo](https://visualgo.net/zh/list))

push(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    }
    this.length++;
}

#### 新增`pop`方法

> 移除尾端節點

1. 如果`head`為空，則返回`null`
1. 如果鏈表長度為`1`，則將`head`設置為`null`並返回原本的`head`節點
1. 否則，使用一個`for`循環，遍歷`Linked List`直到找到倒數第二個節點
1. 將倒數第二個節點的`next`設置為`null`
1. 減少`Linked List`長度，並返回尾端節點

(圖片來自於[visualgo](https://visualgo.net/zh/list))

pop() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let currentNode = this.head;
      for (let i = 1; i <= this.length - 2; i++) {
        currentNode = currentNode.next;
      }
      let temp = currentNode.next;
      currentNode.next = null;
      this.length--;
      return temp;
    }
}

#### 新增`shift`方法

> 刪除開頭的節點

1. 如果`head`為空，則返回`null`
1. 如果`Linked List`長度為`1`，則將`head`設置為`null`並返回原本的`head`節點
1. 否則，將`head`設置為`head`的下一個節點
1. 減少`Linked List`長度，並返回原本的head節點

(圖片來自於[visualgo](https://visualgo.net/zh/list))

shift() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let temp = this.head;
      this.head = this.head.next;
      this.length--;
      return temp;
    }
}

#### 新增`unshift`方法

> 新增新節點在頭部

1. 如果`head`為空，則將`head`設置為新節點。
1. 否則，創建一個新節點，將`head`設置為新節點，並將新節點的`next`指向原本的`head`節點。
1. 增加`Linked List`的長度

(圖片來自於[visualgo](https://visualgo.net/zh/list))

unshift(value) {
    if (!this.head) {
      this.head = new Node(value);
    } else {
      let temp = this.head;
      let newNode = new Node(value);
      this.head = newNode;
      this.head.next = temp;
    }
    this.length++;
}

#### 新增`insertAt`方法

> 在`Linked List`中的特定索引位置新增一個新節點

1. 如果索引大於`Linked List`的長度或小於`0`，則返回`null`。
1. 如果索引等於`0`，則通過`unshift`方法在`Linked List`開頭添加一個新節點。
1. 如果索引等於`Linked List`的長度，則通過`push`方法在`Linked List`末尾添加一個新節點。
1. 否則，創建一個新節點，遍歷到索引位置的節點，將新節點的`next`指向當前節點的下一個節點，並將當前節點的`next`指向新節點。
1. 增加`Linked List`的長度

(圖片來自於[visualgo](https://visualgo.net/zh/list))

insertAt(index, value) {
    if (index > this.length || index < 0) {
      return null;
    } else if (index === 0) {
      this.unshift(value);
      return;
    } else if (index === this.length) {
      this.push(value);
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(value);
    // for loop index - 1 steps
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    newNode.next = currentNode.next;
    currentNode.next = newNode;
    this.length++;
    return;
}

#### 新增`removeAt`方法

> 在`Linked List`中的特定索引位置刪除一個節點

1. 首先檢查指定的索引是否在`Linked List`的範圍之外，在這種情況下返回`null`
2. 如果索引為`0`則使用`shift`方法刪除頭節點，返回刪除節點
3. 如果索引等於`Linked List`長度則使用`pop`方法刪除尾端節點並返回
4. 否則，遍歷`Linked List`找到要移除的索引位置減一，更新指針已移除目標節點，並返回刪除節點
5. 減少`Linked List`的長度

(圖片來自於[visualgo](https://visualgo.net/zh/list))

removeAt(index) {
    if (index > this.length - 1 || index < 0) {
      return null;
    } else if (index === 0) {
      let result = this.shift();
      return result;
    } else if (index === this.length - 1) {
      let result = this.pop();
      return result;
    }

    let currentNode = this.head;
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    let temp = currentNode.next;
    currentNode.next = currentNode.next.next;
    this.length--;
    return temp;
}

#### 新增`get`方法

> 返回索引位置的值

1. 檢查索引是否大於或等於`Linked List`的長度或小於 `0`，在範圍外則返回`null`
2. 範圍內則迭代至`index`位置則返回

(圖片來自於[visualgo](https://visualgo.net/zh/list))

get(index) {
    if (index >= this.length || index < 0) {
      return null;
    }
    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode.value;
}

#### 完整程式碼

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

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  push(value) {
    let newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let currentNode = this.head;
      while (currentNode.next !== null) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    }
    this.length++;
  }

  pop() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let currentNode = this.head;
      for (let i = 1; i <= this.length - 2; i++) {
        currentNode = currentNode.next;
      }
      let temp = currentNode.next;
      currentNode.next = null;
      this.length--;
      return temp;
    }
  }

  shift() {
    if (!this.head) {
      return null;
    } else if (this.length === 1) {
      let temp = this.head;
      this.head = null;
      this.length = 0;
      return temp;
    } else {
      let temp = this.head;
      this.head = this.head.next;
      this.length--;
      return temp;
    }
  }

  unshift(value) {
    if (!this.head) {
      this.head = new Node(value);
    } else {
      let temp = this.head;
      let newNode = new Node(value);
      this.head = newNode;
      this.head.next = temp;
    }
    this.length++;
  }

  insertAt(index, value) {
    if (index > this.length || index < 0) {
      return null;
    } else if (index === 0) {
      this.unshift(value);
      return;
    } else if (index === this.length) {
      this.push(value);
      return;
    }

    let currentNode = this.head;
    let newNode = new Node(value);
    // for loop index - 1 steps
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    newNode.next = currentNode.next;
    currentNode.next = newNode;
    this.length++;
    return;
  }

  removeAt(index) {
    if (index > this.length - 1 || index < 0) {
      return null;
    } else if (index === 0) {
      let result = this.shift();
      return result;
    } else if (index === this.length - 1) {
      let result = this.pop();
      return result;
    }

    let currentNode = this.head;
    for (let i = 1; i <= index - 1; i++) {
      currentNode = currentNode.next;
    }
    let temp = currentNode.next;
    currentNode.next = currentNode.next.next;
    this.length--;
    return temp;
  }

  get(index) {
    if (index >= this.length || index < 0) {
      return null;
    }
    let currentNode = this.head;
    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }
    return currentNode.value;
  }

  printAll() {
    if (this.length === 0) {
      console.log("Nothing in this linked list.");
      return;
    }
    let currentNode = this.head;
    while (currentNode !== null) {
      console.log(currentNode.value);
      currentNode = currentNode.next;
    }
  }
}

let myLinkedList = new LinkedList();
myLinkedList.push("Joe");
myLinkedList.push("Cherry");
myLinkedList.push("Denny");
myLinkedList.push("Fred");
myLinkedList.removeAt(1);
myLinkedList.insertAt(1, "Ted");

myLinkedList.printAll(); // Joe Ted Denny Fred
// console.log(myLinkedList.length);

(圖片取自於[GeeksforGeeks](https://www.geeksforgeeks.org/what-is-linked-list/?ref=lbp))

(圖片取自於[GeeksforGeeks](https://www.geeksforgeeks.org/what-is-linked-list/?ref=lbp))

#### 實戰

[707. Design Linked List](https://leetcode.com/problems/design-linked-list/)

##### 題目說明

設計一個 `Linked list` 可以選擇使用單向鏈結或雙向鏈結，單向鏈結的 `node` 須包含 `val` 和 next，而雙向鏈結則需再多一個 `prev` 屬性。


##### code

[詳細解法](https://leetcode.com/problems/design-linked-list/solutions/3139775/javascript-solution-detail/?orderBy=hot)

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

var MyLinkedList = function() {
    this.head = null;
    this.tail = null;
    this.length = 0;
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this.length) return -1;
    let current = this.head;
    let i = 0;
    while (i !== index) {
        current = current.next;
        i++;
    }
    return current.val;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let newNode = new Node(val);
    if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head = newNode;
    }
    this.length++;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let newNode = new Node(val);
    if (!this.tail) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        this.tail = newNode;
    }
    this.length++;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    let newNode = new Node(val);
    if (index < 0 || index > this.length) return -1;
    if (index === 0) {
        this.addAtHead(val);
    } else if (index === this.length) {
        this.addAtTail(val);
    } else {
        let current = this.head;
        let i = 0;
        while (i !== index - 1) {
            current = current.next;
            i++;
        }
        newNode.next = current.next;
        current.next = newNode;
        this.length++;
    }
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index < 0 || index >= this.length) return -1;
    if (index === 0) {
        this.head = this.head.next;
        this.length--;
    } else{
        let current = this.head;
        let i = 0;
        while (i !== index - 1) {
            current = current.next;
            i++;
        }
        current.next = current.next.next;
        if (index === this.length - 1) {
            this.tail = current;
        }
        this.length--;
    }
};

/** 
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

## 參考來源

[資料結構與演算法 (JavaScript)](https://www.udemy.com/course/algorithm-data-structure/)