js數(shù)據(jù)結(jié)構(gòu)-鏈表

LuDongWei 發(fā)布于2019-08-23 14:24 / 1684人閱讀

摘要：從而就引出了鏈表這種數(shù)據(jù)結(jié)構(gòu)，鏈表不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)所具有的缺點(diǎn)，當(dāng)然它也失去了數(shù)組在一塊連續(xù)空間內(nèi)隨機(jī)存取的優(yōu)點(diǎn)。

鏈表和數(shù)組

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

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

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

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

單向鏈表

單向鏈表的特點(diǎn)：

用一組任意的內(nèi)存空間去存儲數(shù)據(jù)元素（這里的內(nèi)存空間可以是連續(xù)的，也可以是不連續(xù)的）

每個(gè)節(jié)點(diǎn)(node)都由數(shù)據(jù)本身和一個(gè)指向后續(xù)節(jié)點(diǎn)的指針組成

整個(gè)鏈表的存取必須從頭指針開始，頭指針指向第一個(gè)節(jié)點(diǎn)

最后一個(gè)節(jié)點(diǎn)的指針指向空（NULL）

鏈表中的幾個(gè)主要操作

創(chuàng)建節(jié)點(diǎn)

插入節(jié)點(diǎn)

搜索/遍歷節(jié)點(diǎn)

刪除節(jié)點(diǎn)

合并

初始化節(jié)點(diǎn)

指針指向空

存儲數(shù)據(jù)

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

初始化單向鏈表

每個(gè)鏈表都有一個(gè)頭指針，指向第一個(gè)節(jié)點(diǎn)，沒節(jié)點(diǎn)則指向NULL

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

創(chuàng)建節(jié)點(diǎn)

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

這里說明一下，這一塊我是向外暴露了一個(gè)靜態(tài)方法來創(chuàng)建節(jié)點(diǎn)，而并非直接把它封裝進(jìn)插入操作里去，因?yàn)槲腋杏X這樣的邏輯會更加正確一些。從創(chuàng)建一個(gè)鏈表 -> 創(chuàng)建一個(gè)節(jié)點(diǎn) -> 將節(jié)點(diǎn)插入進(jìn)鏈表中?？赡苣銜龅揭恍┪恼陆榻B的方式是直接將一個(gè)數(shù)據(jù)作為參數(shù)去調(diào)用insert操作，在insert內(nèi)部做了一個(gè)創(chuàng)建節(jié)點(diǎn)。

插入節(jié)點(diǎn)（插入到頭節(jié)點(diǎn)之后）

插入操作只需要去調(diào)整節(jié)點(diǎn)的指針即可,兩種情況：

head沒有指向任何節(jié)點(diǎn)，說明當(dāng)前插入的節(jié)點(diǎn)是第一個(gè)

head指向新節(jié)點(diǎn)

新節(jié)點(diǎn)的指針指向NULL

head有指向的節(jié)點(diǎn)

head指向新的節(jié)點(diǎn)

新節(jié)點(diǎn)的指針指向原本head所指向的節(jié)點(diǎn)

    insert(node) {
        // 如果head有指向的節(jié)點(diǎn)
        if(this.head){
           node.next = this.head;
        }else {
           node.next = null;
        }
        this.head = node;
    }

搜索節(jié)點(diǎn)

從head開始查找

找到節(jié)點(diǎn)中的key等于想要查找的key的時(shí)候，返回該節(jié)點(diǎn)

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

刪除節(jié)點(diǎn)

這里分三種情況：

所要?jiǎng)h除的節(jié)點(diǎn)剛好是第一個(gè)，也就是head指向的節(jié)點(diǎn)

將head指向所要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)(node.next)

要?jiǎng)h除的節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)

尋找到所要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)(prevNode)

將prevNode中的指針指向NULL

在列表中間刪除某個(gè)節(jié)點(diǎn)

尋找到所要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)(prevNode)

將prevNode中的指針指向當(dāng)前要?jiǎng)h除的這個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

    delete(node) {
        // 第一種情況
        if(node === this.head){
            this.head = node.next;
            return;
        }
        
        // 查找所要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
        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);
  }

  // 往頭部插入數(shù)據(jù)
  insert(node) {
    // 如果head后面有指向的節(jié)點(diǎn)
    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--;
  }
}

雙向鏈表

如果你把上面介紹的單向列表都看明白了，那么這里介紹的雙向列表其實(shí)差不多。

從上面的圖可以很清楚的看到雙向鏈表和單向鏈表的區(qū)別。雙向鏈表多了一個(gè)指向上一個(gè)節(jié)點(diǎn)的指針。

初始化節(jié)點(diǎn)

指向前一個(gè)節(jié)點(diǎn)的指針

指向后一個(gè)節(jié)點(diǎn)的指針

節(jié)點(diǎn)數(shù)據(jù)

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

初始化雙向鏈表

頭指針指向NULL

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

創(chuàng)建節(jié)點(diǎn)

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

插入節(jié)點(diǎn)（（插入到頭節(jié)點(diǎn)之后）

看上圖中head后面的第一個(gè)節(jié)點(diǎn)可以知道，該節(jié)點(diǎn)的prev指向NULL

節(jié)點(diǎn)的next指針指向后一個(gè)節(jié)點(diǎn), 也就是當(dāng)前頭指針?biāo)赶虻哪莻€(gè)節(jié)點(diǎn)

如果head后有節(jié)點(diǎn)，那么原本head后的節(jié)點(diǎn)的prev指向新插入的這個(gè)節(jié)點(diǎn)(因?yàn)槭请p向的嘛)

最后將head指向新的節(jié)點(diǎn)

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

搜索節(jié)點(diǎn)

這里和單向節(jié)點(diǎn)一樣，就直接貼代碼了

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

刪除節(jié)點(diǎn)

和之前單向鏈表一樣，分三種情況去看：

刪除的是第一個(gè)節(jié)點(diǎn)

head指向所要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

下一個(gè)節(jié)點(diǎn)的prev指針指向所要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)

刪除的是中間的某個(gè)節(jié)點(diǎn)

所要?jiǎng)h除的前一個(gè)節(jié)點(diǎn)的next指向所要?jiǎng)h除的下一個(gè)節(jié)點(diǎn)

所要?jiǎng)h除的下一個(gè)節(jié)點(diǎn)的prev指向所要?jiǎng)h除的前一個(gè)節(jié)點(diǎn)

刪除的是最后一個(gè)節(jié)點(diǎn)

要?jiǎng)h除的節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next指向null（也就是指向刪除節(jié)點(diǎn)的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) {
    // 指向前一個(gè)節(jié)點(diǎn)
    this.prev = null;
    // 指向后一個(gè)節(jié)點(diǎn)
    this.next = null;
    // 節(jié)點(diǎn)的數(shù)據(jù)(或者用于查找的鍵)
    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;
    }
  }
}

總結(jié)

這里做一個(gè)小總結(jié)吧，可能有一部分人讀到這里還不是特別的明白，我的建議是先好好看懂上面的單向鏈表。其實(shí)只要你明白了鏈表的基礎(chǔ)概念，就是有一個(gè)head，然后在有好多的節(jié)點(diǎn)(Node)，然后用一個(gè)指針把他們串起來就好了，至于里面的插入操作也好，刪除也好，其實(shí)都是在調(diào)整節(jié)點(diǎn)中指針的指向。

后續(xù)

后續(xù)可能還會是數(shù)據(jù)結(jié)構(gòu)，可能是講二叉堆，也可能回過頭來講一些隊(duì)列和棧的思想在程序中的應(yīng)用。歡迎大家指出文章的錯(cuò)誤，如果有什么寫作建議也可以提出。我會持續(xù)的去寫關(guān)于前端的一些技術(shù)文章，如果大家喜歡的話可以關(guān)注一下哈