JavaScript中鍊錶的詳細介紹

這篇文章帶給大家的內容是關於JavaScript中鍊錶的詳細介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

鍊錶與陣列

大家都用過js中的陣列，陣列其實是線性表的順序儲存結構，它的特色就是用一組位址連續的儲存單元依序儲存資料元素。而它的缺點也正是其特點而造成，例如對陣列做刪除或插入的時候，可能需要移動大量的元素。

這裡大致模擬一下陣列的插入操作：

    insert(arr, index, data){
        for(let i = index + 1; i <p>從上面的程式碼可以看出陣列的插入以及刪除都有可能會是一個O(n)的運算。從而引出了鍊錶這種資料結構，鍊錶不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結構所具有的缺點，當然它也失去了數組在一塊連續空間內隨機訪問的優點。 </p><h3>單向鍊錶</h3><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/880/877/695/1546394138978971.png" title="1546394138978971.png" alt="JavaScript中鍊錶的詳細介紹"></span></p><h4>#單向鍊錶的特點：</h4>

• 用一群組任意的記憶體空間去儲存資料元素（這裡的記憶體空間可以是連續的，也可以是不連續的）

• 每個節點(node)都由資料本身和一個指向後續節點的指標組成

• 整個鍊錶的存取必須從頭指標開始，頭指標指向第一個節點

• ##最後一個節點的指標指向空（NULL）

鍊錶中的幾個主要操作

• 建立節點

• 插入節點

• 搜尋/遍歷節點

• #刪除節點

##合併
初始化節點

#指標指向空
儲存資料

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

初始化單向鍊錶

每個鍊錶都有一個頭指針，指向第一個節點，沒節點則指向NULL

• ##

      class List {
          constructor() {
              this.head = null;
          }
      }

  建立節點

    static createNode(key) {
        return new createNode(key);
    }

這裡說明一下，這一塊我是向外暴露了一個靜態方法來創建節點，而並非直接把它封裝進插入操作裡去，因為我感覺這樣的邏輯會更加正確一些。從建立一個鍊錶 -> 建立一個節點 -> 將節點插入進鍊錶。可能你會遇到一些文章介紹的方式是直接將一個資料當作參數去呼叫insert操作，在insert內部做了一個建立節點。

插入節點（插入到頭節點之後）

插入操作只需要去調整節點的指標即可,兩種情況：

head沒有指向任何節點，說明目前插入的節點是第一個

head指向新節點

• 新節點的指標指向NULL
head有指向的節點
#head指向新的節點

• 新節點的指標指向原本head所指向的節點

•     insert(node) {
          // 如果head有指向的节点
          if(this.head){
             node.next = this.head;
          }else {
             node.next = null;
          }
          this.head = node;
      }

#搜尋節點

從head開始尋找

• 找到節點中的key等於想要尋找的key的時候，返回該節點

•     find(key) {
          let node = this.head;
          while(node !== null && node.key !== key){
              node = node.next;
          }
          return node;
      }

  刪除節點

這裡分三種情況：

要刪除的節點剛好是第一個，也就是head指向的節點

• ##將head指向所要刪除節點的下一個節點(node.next)

• 要刪除的節點為最後一個節點

• 尋找到要刪除節點的上一個節點(prevNode)

• 將prevNode中的指標指向NULL

• ##在清單中間刪除某個節點

• 尋找到所要刪除節點的上一個節點(prevNode)

• 將prevNode中的指標指向目前要刪除的這個節點的下一個節點

•     delete(node) {
          // 第一种情况
          if(node === this.head){
              this.head = node.next;
              return;
          }
          
          // 查找所要删除节点的上一个节点
          let prevNode = this.head;
          while (prevNode.next !== node) {
              prevNode = prevNode.next;
          }
          
          // 第二种情况
          if(node.next === null) {
              prevNode.next = null;
          }
          
          // 第三种情况
          if(node.next) {
              prevNode.next = node.next;
          }
      }

  單向鍊錶整體的程式碼

  class ListNode {
    constructor(key) {
      this.next = null;
      this.key = key;
    }
  }
  
  class List {
    constructor() {
      this.head = null;
      this.length = 0;
    }
  
    static createNode(key) {
      return new ListNode(key);
    }
  
    // 往头部插入数据
    insert(node) {
      // 如果head后面有指向的节点
      if (this.head) {
        node.next = this.head;
      } else {
        node.next = null;
      }
      this.head = node;
      this.length++;
    }
  
    find(key) {
      let node = this.head;
      while (node !== null && node.key !== key) {
        node = node.next;
      }
      return node;
    }
  
    delete(node) {
      if (this.length === 0) {
        throw 'node is undefined';
      }
  
      if (node === this.head) {
        this.head = node.next;
        this.length--;
        return;
      }
  
      let prevNode = this.head;
  
      while (prevNode.next !== node) {
        prevNode = prevNode.next;
      }
  
      if (node.next === null) {
        prevNode.next = null;
      }
      if (node.next) {
        prevNode.next = node.next;
      }
      this.length--;
    }
  }

雙向鍊錶

如果你把上面介紹的單向列表都看懂了，那這裡介紹的雙向列表其實差不多。

從上面的圖可以很清楚的看到雙向鍊錶和單向鍊錶的差異。雙向鍊錶多了一個指向上一個節點的指標。 初始化節點

指向前一個節點的指標

指向后一个节点的指针

节点数据

    class ListNode {
        this.prev = null;
        this.next = null;
        this.key = key;
    }

初始化双向链表

• 头指针指向NULL

    class List {
        constructor(){
            this.head = null;
        }
    }

创建节点

    static createNode(key){
        return new ListNode(key);
    }

插入节点（（插入到头节点之后）

• 看上图中head后面的第一个节点可以知道，该节点的prev指向NULL

• 节点的next指针指向后一个节点, 也就是当前头指针所指向的那个节点

• 如果head后有节点，那么原本head后的节点的prev指向新插入的这个节点(因为是双向的嘛)

• 最后将head指向新的节点

    insert(node) {
        node.prev = null;
        node.next = this.head;
        if(this.head){
            this.head.prev = node;
        }
        this.head = node;
    }

搜索节点

这里和单向节点一样，就直接贴代码了

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

删除节点

和之前单向链表一样，分三种情况去看：

• 删除的是第一个节点

• head指向所要删除节点的下一个节点

• 下一个节点的prev指针指向所要删除节点的上一个节点

• 删除的是中间的某个节点

• 所要删除的前一个节点的next指向所要删除的下一个节点

• 所要删除的下一个节点的prev指向所要删除的前一个节点

• 删除的是最后一个节点

• 要删除的节点的上一个节点的next指向null（也就是指向删除节点的next所指的地址）

    delete(node) {
        const {prev,next} = node;
        delete node.prev;
        delete node.next;
        if(node === this.head){
            this.head = next;
        }
        if(next){
            next.prev = prev;
        }
        if(prev){
            prev.next = next;
        }
    }

双向链表整体代码

    class ListNode {
  constructor(key) {
    // 指向前一个节点
    this.prev = null;
    // 指向后一个节点
    this.next = null;
    // 节点的数据(或者用于查找的键)
    this.key = key;
  }
}

/**
 * 双向链表
 */
class List {
  constructor() {
    this.head = null;
  }

  static createNode(key) {
    return new ListNode(key);
  }

  insert(node) {
    node.prev = null;
    node.next = this.head;
    if (this.head) {
      this.head.prev = node;
    }
    this.head = node;
  }

  search(key) {
    let node = this.head;
    while (node !== null && node.key !== key) {
      node = node.next;
    }
    return node;
  }

  delete(node) {
    const { prev, next } = node;
    delete node.prev;
    delete node.next;

    if (node === this.head) {
      this.head = next;
    }

    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
  }
}

总结

这里做一个小总结吧，可能有一部分人读到这里还不是特别的明白，我的建议是先好好看懂上面的单向链表。 其实只要你明白了链表的基础概念，就是有一个head，然后在有好多的节点(Node)，然后用一个指针把他们串起来就好了，至于里面的插入操作也好，删除也好，其实都是在调整节点中指针的指向。

以上是JavaScript中鍊錶的詳細介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！