鏈表！比數組更適合做增刪操作的數據結構

什麼是鏈表？鏈表和數組的對比：在大多數語言中，數組的大小是固定的，從數組的起點或中間添加或刪除元素的成本很高，因為需要移動元素。鏈表中的每一個元素在記憶體中不是連續放置的，和它左右兩側元素是沒有關係的。每個元素有一個存儲元素本身的節點和指向下一個元素的引用組成。相對於數組，鏈表的好處在於添加或 ...

什麼是鏈表？

鏈表和數組的對比：在大多數語言中，數組的大小是固定的，從數組的起點或中間添加或刪除元素的成本很高，因為需要移動元素。
鏈表中的每一個元素在記憶體中不是連續放置的，和它左右兩側元素是沒有關係的。
每個元素有一個存儲元素本身的節點和指向下一個元素的引用組成。
相對於數組，鏈表的好處在於添加或刪除元素的時候不需要移動其它元素。
在數組中我們可以直接訪問任何位置的任何元素，而要想訪問鏈表中的某一個元素，則需要從起點（鏈表頭）開始迭代鏈表直到找到所需的元素。

舉個慄子：一列火車是由一系列車廂組成的。每節車廂或車皮都相互連接，你很容易分離一節車箱，改變它的位置、添加或移除它。每節車廂相當於鏈表的元素，車廂間的對接扣就是元素的引用。

創建一個鏈表類

const defaultCompare = function (a, b) { // 一個比較函數
  if (a === b) return 0;
  return a < b ? -1 : 1;
}

class Node { // 一個助手類，用來表示我們想要添加到鏈表中的元素
  constructor(element, next) {
    this.element = element; // 元素的值
    this.next = next; // 指向鏈表中下一個元素的指針
  }
}

class LinkedList { // 鏈表類
    constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn; // 比較鏈表中的元素是否相等，預設a===b
    this.count = 0; // 鏈表中的元素數量
    this.head = undefined; // 表頭
  }
}

創建幾個鏈表的方法

向鏈表的尾部添加元素

push(element) {
    const node = new Node(element); // 創建node項
    let current; // 聲明一個指向鏈表中的臨時項
    if (this.head == undefined) { // 如果鏈表頭為空，即鏈表為空
      this.head = node; // 直接讓表頭等於當前元素就好了，下一項（next）未傳，因此為undefined
    } else {
      current = this.head; // 先讓current等於第一個元素
      while (current.next != null) { // 只要當前元素的下一項元素不是假的，便繼續迴圈
        current = current.next;
      }
      current.next = node; // 找到最後一個元素後，讓它的下一個元素等於傳進來的元素
    }
    this.count++;// 最後把總長度自增就好了
  }

首先初始化node類，把element作為值傳入。
尾部添加元素分為兩種情況，一種是鏈表為空，一種是鏈表有值，在後者時，因為鏈表只有鏈表頭的引用，因此在向鏈表尾部添加元素時，我們需要迴圈列表，直到找到最後一個元素，為此我們需要一個指向鏈表中current項的變數。
如果鏈表頭沒值表示在向鏈表添加第一個元素，直接讓表頭等於當前元素就好了，下一項的引用（next）未傳，因此為undefined
然後就是第二種情況，首先讓current等於鏈表頭，然後迴圈訪問列表，直到找到最後一個元素，然後就是讓最後一個元素的下一項的引用指向想要添加到鏈表的節點。
最後把總長度自增就好了

從特定位置移除一個元素

removeAt(index) {
    if (index >= 0 && index < this.count) { // 檢查越界值
      let current = this.head;
      if (index === 0) { // 如果是表頭
        this.head = current.next; // 就讓表頭等於下一個引用
      } else {
        let previous；
        for (let i = 0; i < index； i++) { // 嗯，開始迭代把~~~
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        // 上一個的下一個等於現在的下一個，，，（現在內心os:我是誰，我在哪？？？）當前節點就會被丟棄在電腦記憶體中，等著被垃圾回收器移除
      }
      this.count--;// 長度自減
      return current.element; // 返回移除的元素
    }

    return undefined;
  }

由於該方法需要得到移除元素的index（位置），我們需要驗證該index是從0到鏈表的長度之間的。如果不是就返回undefined。
如果移除的是鏈表中的第一個元素，就要讓head指向列表的第二個元素。我們將current變數創建一個對鏈表中第一個元素的引用。這樣current變數就是對鏈表中第一個元素的引用。這時候如果如果把head賦為current.next，就會移除第一個元素。我們也可以直接把head賦為head.next，不使用current。
如果我們要移除的是鏈表的最後一個元素或者中間的某個元素。就需要對鏈表進行迭代，直到到達目標位置。
在到達目標位置後，current變數就會變成我們想要從鏈表中移除的節點。因此，要從鏈表中移除當前元素，要做的就是將previous.next和current.next鏈接起來。這樣，當前節點就會被丟棄在電腦記憶體中，等著被垃圾回收器清除。

迴圈迭代鏈表直到目標位置

getElementAt(index) {
    if (index >= 0 && index <= this.count) return undefined; // 檢查越界值
    let node = this.head; // 預設等於表頭
    for (let i = 0; i < index && node != null; i++) { // 嗯，開始迭代把~~~
      node = node.next;
    }
    return node;
  }

在remove方法中，我們需要迭代整個鏈表直到到達我們的目標索引index(位置)。迴圈到目標index的代碼片段在鏈表方法中會經常用到。因此，我們可以將這部分邏輯獨立為單獨的辦法，這樣就可以在不同的地方復用它。
然後我們可以使用剛剛創建的getElementAt方法來重構remove方法

if(index===0){
    // 第一個位置的邏輯
} else {
    const previous = this.getElementAt(index - 1);
    current = previous.next;
    previous.next = current.next;
}
this.count--;

在任何位置插入元素

insert(element, index) {
    if (index >= 0 && index <= this.count) { // 邊界處理
      const node = new Node(element); // 實例化當前元素
      if (index === 0) { // 如果插在表頭
        const current = this.head;// 聲明一個變數，等於原來的表頭
        node.next = current;// 傳入元素的下一個引用等於current
        this.head = node; // 當前表頭等於傳入的元素
      } else {
        const previous = this.getElementAt(index - 1);// 找到傳入索引的上一個值
        previous.next = node;// 上一個的引用等於傳入的值
        node.next = previous.next;// 傳入值的下一個引用等於上一個的下一個引用
        
      }
      this.count++;// 總長度自增
      return true; // 最後返回true
    }
  return false; // 如果位置未找到返回false
}

先慣例的做一下邊界處理。
首先如果是插在鏈表頭，我們先聲明一個變數等於原來的鏈表頭，再讓插入元素的先一個引用等於原來的current變數，最後讓當前表頭等於傳入的元素。
如果是在鏈表中間或者末尾我們需要用getElementAt方法先找到目標位置的上一個元素，然後讓上一個的引用等於傳入的值。再把傳入值的下一個引用等於上一個的下一個引用。最後一定記得把總長度加一，返回true

返回一個元素的位置

indexOf(element) {
    let current = this.head; // 等於表頭
    for (let i = 0; i < this.size() && current != null; i++) { // 迴圈迭代所有元素
      if (this.equalsFn(element, current.element)) { // 找到和當前元素相等的第一個元素
        return i;// 返回索引
      }
      current = current.next;// 如果不相等，就繼續迭代下一個
    }
    return -1; // 如果都沒找到，就返回-1
  }

indexOf方法接收一個元素的值，如果在鏈表中找到了它，就返回元素的位置，否則返回-1。
一如既往，需要一個變數來幫助我們迴圈訪問列表。該變數是current，它的初始值是head
然後迭代元素，從鏈表頭開始，直到鏈表長度為止。為了確保不會發生運行時錯誤，我們可以驗證一下current變數是否為null或undefined。
迴圈迭代所有元素直到找到和當前元素相等的第一個元素，返回它的所在位置
如果沒找到，就返回-1

移除傳入的元素

remove(element) { 
    const index = this.indexOf(element); // 先找到這個元素的第一個索引
    return this.removeAt(index); // 利用刪除指定位置元素的方法，搞掉它
  }

我們已經有了一個用來移除給定位置元素的方法，也有了indexOf方法。利用indexOf方法找到它的位置，利用刪除指定位置元素的方法，搞掉它。

檢查是否為空，長度，獲取鏈表頭

isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }

還是比較簡單的。

把所有元素轉換成字元串

toString() {
    if (this.head == null) { // 如果列表為空，就返回空字元串
      return '';
    }
    let objString = `${this.head.element}`; // 創建一個變數，先讓他等於表頭的元素
    let current = this.head.next; // 等於表頭的下一個引用
    for (let i = 1; i < this.size() && current != null; i++) { // 迴圈迭代所有元素
      objString = `${objString},${current.element}`; // 讓這個字元串等於原來的字元串加上當前元素
      current = current.next; // 當前元素等於當前的下一個引用
    }
    return objString; // 最後把這個字元串返回
  }

首先，如果鏈表為空，我們就返回一個空字元串。
如果有值我們就用鏈表第一個元素的值來初始化方法最後返回的字元串。
然後我們迭代鏈表中的所有其它元素，將元素值添加到字元串上。
最後把這個字元串返回。

最後

今天的隨手筆記就記到這裡了，等有時間我會再寫一篇關於鏈表的各種增強版本。總之，在我閱讀完這一章後覺得鏈表相比數組，更適合做增刪操作，而數組更適合存儲一些比較固定不變的有序集合。