js數據結構-鏈表

LuDongWei 發布于2019-08-23 14:24 / 1667人閱讀

摘要：從而就引出了鏈表這種數據結構，鏈表不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結構所具有的缺點，當然它也失去了數組在一塊連續空間內隨機存取的優點。

鏈表和數組

大家都用過js中的數組，數組其實是一種線性表的順序存儲結構，它的特點是用一組地址連續的存儲單元依次存儲數據元素。而它的缺點也正是其特點而造成，比如對數組做刪除或者插入的時候，可能需要移動大量的元素。

這里大致模擬一下數組的插入操作：

    function insert(arr, index, data) {
      for (let i = arr.length; i >index; i--) {
        arr[i] = arr[i - 1];
      }
      arr[index] = data;
    }

從上面的代碼可以看出數組的插入以及刪除都有可能會是一個O(n)的操作。從而就引出了鏈表這種數據結構，鏈表不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結構所具有的缺點，當然它也失去了數組在一塊連續空間內隨機存取的優點。

單向鏈表

單向鏈表的特點：

用一組任意的內存空間去存儲數據元素（這里的內存空間可以是連續的，也可以是不連續的）

每個節點(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)，然后用一個指針把他們串起來就好了，至于里面的插入操作也好，刪除也好，其實都是在調整節點中指針的指向。

后續

后續可能還會是數據結構，可能是講二叉堆，也可能回過頭來講一些隊列和棧的思想在程序中的應用。歡迎大家指出文章的錯誤，如果有什么寫作建議也可以提出。我會持續的去寫關于前端的一些技術文章，如果大家喜歡的話可以關注一下哈

云服務器 GPU云服務器鏈表數據結構隊列 linux 數據結構鏈表 java鏈表數據結構 C++數據結構鏈表

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/100556.html

JS數據結構與算法_鏈表

摘要：上一篇數據結構與算法棧隊列下一篇數據結構與算法集合字典寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到上一篇博客發布以后，僅幾天的時間竟然成為了我寫博客以來點贊數最多的一篇博客。上一篇：JS數據結構與算法_棧&隊列下一篇：JS數據結構與算法_集合&字典寫在前面說明：JS數據結構與算法系列文章的代碼和示例均可在此找到上一篇博客發布以后，僅幾天的時間竟然成為了我寫博客以...

NeverSayNever 2019-08-23 14:53 評論0 收藏0
JS數據結構0x004：鏈表

摘要：概述這篇文章是說鏈表，鏈表這種數據結構非常普遍，有時候我們根本就沒有意識到用的是鏈表啥是鏈表鏈表就是用繩子連起來的酒瓶子，酒就是數據，每個酒瓶子都連著下一個酒瓶子。 0x000 概述這篇文章是說鏈表，鏈表這種數據結構非常普遍，有時候我們根本就沒有意識到用的是鏈表 0x001 啥是鏈表鏈表就是用繩子連起來的酒瓶子，酒就是數據，每個酒瓶子都連著下一個酒瓶子。 showImg(https...

sumory 2019-08-23 12:47 評論0 收藏0
js合并有序鏈表

摘要：關于鏈表區別于數組，數組的所有的元素在內存中都是連續存儲的，而鏈表則是分散在內存中的，通過指針連接起來的一種數據結構。接下來，我們嘗試使用合并兩個有序鏈表。關于鏈表區別于數組，數組的所有的元素在內存中都是連續存儲的，而鏈表則是分散在內存中的，通過指針連接起來的一種數據結構。接下來，我們嘗試使用js合并兩個有序鏈表。一些準備首先我們需要聲明一些我們需要用到的函數。鏈表中的節點 ...

jollywing 2019-08-21 17:10 評論0 收藏0
Leetcode：刷完31道鏈表題的一點總結

摘要：既然說到地址空間了就順帶說一下上面環形鏈表這道題的另一種很的解法吧。介紹完常規操作鏈表的一些基本知識點后，現在回到快慢指針。 ??前幾天第一次在 Segmentfault 發文—JavaScript：十大排序的算法思路和代碼實現，發現大家似乎挺喜歡算法的，所以今天再分享一篇前兩個星期寫的 Leetcode 刷題總結，希望對大家能有所幫助。 ??本文首發于我的blog 前言 ??今天終于...

DevTalking 2019-08-23 17:50 評論0 收藏0
JS數據結構學習：鏈表

摘要：在存儲多個元素時，我們最常用的數據結構可能是數組，究其原因可能是數組訪問方便，可以直接通過訪問，但是數組也存在一定的缺點，數組的大小是固定，數組在執行插入或者刪除的時候成本很高。在存儲多個元素時，我們最常用的數據結構可能是數組，究其原因可能是數組訪問方便，可以直接通過[]訪問，但是數組也存在一定的缺點，數組的大小是固定，數組在執行插入或者刪除的時候成本很高。鏈表存儲的是有序的元素集合...

XanaHopper 2019-08-23 15:26 評論0 收藏0
鏈表在js中的實現

摘要：最近在看數據結構與算法，但是一直搞不明白在代碼中的實現。今天結合找到的一些資料總結一下鏈表在中的實現。這種結構允許在迭代期間有效地從序列中的任何位置插入或刪除元素。最近在看js數據結構與算法，但是一直搞不明白在代碼中的實現。今天結合找到的一些資料總結一下鏈表在js中的實現。首先說下鏈表，在計算機科學中, 一個鏈表是數據元素的線性集合, 元素的線性順序不是由它們在內存中的物理位置給出的...

xiyang 2019-08-23 12:39 評論0 收藏0