JavaScript數(shù)據(jù)結構04 - 鏈表

cheukyin 發(fā)布于2019-08-23 10:39 / 1034人閱讀

摘要：類表示要加入鏈表的項。循環(huán)鏈表和普通鏈表之間唯一的區(qū)別在于，最后一個元素指向下一個元素的指針不是引用，而是指向第一個元素。這里就不進行代碼實現(xiàn)了，大家可以結合上面的單向鏈表和雙向鏈表自己實現(xiàn)一個循環(huán)鏈表。

一、定義 1.1 概念

前面我們學習了數(shù)組這種數(shù)據(jù)結構。數(shù)組（或者也可以稱為列表）是一種非常簡單的存儲數(shù)據(jù)序列的數(shù)據(jù)結構。在這一節(jié)，我們要學習如何實現(xiàn)和使用鏈表這種動態(tài)的數(shù)據(jù)結構，這意味著我們可以從中任意添加或移除項，它會按需進行擴容。

要存儲多個元素，數(shù)組（或列表）可能是最常用的數(shù)據(jù)結構，它提供了一個便利的[]語法來訪問它的元素。然而，這種數(shù)據(jù)結構有一個缺點：（在大多數(shù)強類型語言中）數(shù)組的大小是固定的，需要預先分配，從數(shù)組的起點或中間插入或移除項的成本很高，因為需要移動元素。
（注意：在JavaScript中數(shù)組的大小隨時可變，不需要預先定義長度）

鏈表存儲有序的元素集合，但不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本身的節(jié)點和一個指向下一個元素的引用（也稱指針或鏈接）組成。

相對于傳統(tǒng)的數(shù)組，鏈表的一個好處在于，添加或刪除元素的時候不需要移動其他元素。然而，鏈表需要使用指針，因此實現(xiàn)鏈表時需要額外注意。數(shù)組的另一個細節(jié)是可以直接訪問任何位置的元素，而想要訪問鏈表中間的一個元素，需要從起點（表頭）開始迭代列表直到找到所需的元素。

火車可以當做生活中一個典型的鏈表的例子。一列火車是由一系列車廂組成的。每節(jié)車廂都相互連接。你很容易分離一節(jié)車廂，改變它的位置，添加或移除它。

1.2 分類

鏈表最常用的有三類：

單向鏈表

雙向鏈表

循環(huán)鏈表

二、鏈表的實現(xiàn) 2.1 單向鏈表

創(chuàng)建單向鏈表類：

// SinglyLinkedList
function SinglyLinkedList () {
  function Node (element) {
    this.element = element;
    this.next = null;
  }

  var length = 0;
  var head = null;
  
  this.append = function (element) {};
  this.insert = function (position, element) {};
  this.removeAt = function (position) {};
  this.remove = function (element) {};
  this.indexOf = function (element) {};
  this.isEmpty = function () {};
  this.size = function () {};
  this.getHead = function () {};
  this.toString = function () {};
  this.print = function () {};
}

SinglyLinkedList需要一個輔助類Node。Node類表示要加入鏈表的項。它包含一個element屬性，即要添加到鏈表的值，以及一個next屬性，即指向鏈表中下一個節(jié)點項的指針。

鏈表里面有一些聲明的輔助方法：

append(element)：向鏈表尾部添加新項

insert(position, element)：向鏈表的特定位置插入一個新的項

removeAt(position)：從鏈表的特定位置移除一項

remove(element)：從鏈表中移除一項

indexOf(element)：返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回-1

isEmpty()：如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0，返回false

size()：返回鏈表包含的元素個數(shù)，與數(shù)組的length屬性類似

getHead()：返回鏈表的第一個元素

toString()：由于鏈表使用了Node類，就需要重寫繼承自JavaScript對象默認的toString()方法，讓其只輸出元素的值

print()：打印鏈表的所有元素

下面我們來一一實現(xiàn)這些輔助方法：

  // 向鏈表尾部添加一個新的項
  this.append = function (element) {
    var node = new Node(element);
    var currentNode = head;

    // 判斷是否為空鏈表
    if (currentNode === null) {
      // 空鏈表
      head = node;
    } else {
      // 從head開始一直找到最后一個node
      while (currentNode.next) {
        // 后面還有node
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }

    length++;
  };

  // 向鏈表特定位置插入一個新的項
  this.insert = function (position, element) {
    if (position < 0 && position > length) {
      // 越界
      return false;
    } else {
      var node = new Node(element);
      var index = 0;
      var currentNode = head;
      var previousNode;

      if (position === 0) {
        node.next = currentNode;
        head = node;
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next; 
        }
  
        previousNode.next = node;
        node.next = currentNode;
      }

      length++;

      return true;
    }
  };

  // 從鏈表的特定位置移除一項
  this.removeAt = function (position) {
    if (position < 0 && position >= length || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        head = currentNode.next;
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
      }

      length--;

      return true;
    }
  };

  // 從鏈表的特定位置移除一項
  this.removeAt = function (position) {
    if (position < 0 && position >= length || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        head = currentNode.next;
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
      }

      length--;

      return true;
    }
  };

  // 從鏈表中移除指定項
  this.remove = function (element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在鏈表的索引，如果鏈表中沒有該元素則返回-1
  this.indexOf = function (element) {
    var currentNode = head;
    var index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0，返回false
  this.isEmpty = function () {
    return length == 0;
  };

  // 返回鏈表包含的元素個數(shù)，與數(shù)組的length屬性類似
  this.size = function () {
    return length;
  };

  // 獲取鏈表頭部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于鏈表使用了Node類，就需要重寫繼承自JavaScript對象默認的toString()方法，讓其只輸出元素的值
  this.toString = function () {
    var currentNode = head;
    var string = "";

    while (currentNode) {
      string += "," + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);
  };

  this.print = function () {
    console.log(this.toString());
  };

創(chuàng)建單向鏈表實例進行測試：

// 創(chuàng)建單向鏈表實例
var singlyLinked = new SinglyLinkedList();
console.log(singlyLinked.removeAt(0));              // true
console.log(singlyLinked.isEmpty());              // true
singlyLinked.append("Tom");                       
singlyLinked.append("Peter");
singlyLinked.append("Paul");
singlyLinked.print();                             // "Tom,Peter,Paul"
singlyLinked.insert(0, "Susan");                  
singlyLinked.print();                             // "Susan,Tom,Peter,Paul"
singlyLinked.insert(1, "Jack");                   
singlyLinked.print();                             // "Susan,Jack,Tom,Peter,Paul"
console.log(singlyLinked.getHead());              // "Susan"
console.log(singlyLinked.isEmpty());              // false
console.log(singlyLinked.indexOf("Peter"));       // 3
console.log(singlyLinked.indexOf("Cris"));        // -1
singlyLinked.remove("Tom");                       
singlyLinked.removeAt(2);                         
singlyLinked.print();                             // "Susan,Jack,Paul"

2.2 雙向鏈表

雙向鏈表和普通鏈表的區(qū)別在于，在普通鏈表中，一個節(jié)點只有鏈向下一個節(jié)點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素。

創(chuàng)建雙向鏈表類：

// 創(chuàng)建雙向鏈表DoublyLinkedList類
function DoublyLinkedList () {
  function Node (element) {
    this.element = element;
    this.next = null;
    this.prev = null;        // 新增
  }

  var length = 0;
  var head = null;
  var tail = null;          // 新增
}

可以看到，雙向鏈表在Node類里有prev屬性（一個新指針），在DoublyLinkedList類里也有用來保存對列表最后一項的引用的tail屬性。

雙向鏈表提供了兩種迭代列表的方法：從頭到尾，或者從尾到頭。我們可以訪問一個特定節(jié)點的下一個或前一個元素。

在單向鏈表中，如果迭代鏈表時錯過了要找的元素，就需要回到鏈表起點，重新開始迭代。在雙向鏈表中，可以從任一節(jié)點，向前或向后迭代，這是雙向鏈表的一個優(yōu)點。

實現(xiàn)雙向鏈表的輔助方法：

  // 向鏈表尾部添加一個新的項
  this.append = function (element) {
    var node = new Node(element);
    var currentNode = tail;

    // 判斷是否為空鏈表
    if (currentNode === null) {
      // 空鏈表
      head = node;
      tail = node;
    } else {
      currentNode.next = node;
      node.prev = currentNode;
      tail = node; 
    }

    length++;
  };

  // 向鏈表特定位置插入一個新的項
  this.insert = function (position, element) {
    if (position < 0 && position > length) {
      // 越界
      return false;
    } else {
      var node = new Node(element);
      var index = 0;
      var currentNode = head;
      var previousNode;

      if (position === 0) {
        if (!head) {
          head = node;
          tail = node;
        } else {
          node.next = currentNode;
          currentNode.prev = node;
          head = node;
        }
      } else if (position === length) {
        this.append(element);
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next; 
        }
  
        previousNode.next = node;
        node.next = currentNode;

        node.prev = previousNode;
        currentNode.prev = node;
      }

      length++;

      return true;
    }
  };

  // 從鏈表的特定位置移除一項
  this.removeAt = function (position) {
    if (position < 0 && position >= length || length === 0) {
      // 越界
      return false;
    } else {
      var currentNode = head;
      var index = 0;
      var previousNode;

      if (position === 0) {
        // 移除第一項
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          head = currentNode.next;
          head.prev = null;
        }
      } else if (position === length - 1) {
        // 移除最后一項
        if (length === 1) {
          head = null;
          tail = null;
        } else {
          currentNode = tail;
          tail = currentNode.prev;
          tail.next = null;
        }
      } else {
        while (index < position) {
          index++;
          previousNode = currentNode;
          currentNode = currentNode.next;
        }
        previousNode.next = currentNode.next;
        previousNode = currentNode.next.prev;
      }

      length--;

      return true;
    }
  };

  // 從鏈表中移除指定項
  this.remove = function (element) {
    var index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 返回元素在鏈表的索引，如果鏈表中沒有該元素則返回-1
  this.indexOf = function (element) {
    var currentNode = head;
    var index = 0;

    while (currentNode) {
      if (currentNode.element === element) {
        return index;
      }

      index++;
      currentNode = currentNode.next;
    }

    return -1;
  };

  // 如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0，返回false
  this.isEmpty = function () {
    return length == 0;
  };

  // 返回鏈表包含的元素個數(shù)，與數(shù)組的length屬性類似
  this.size = function () {
    return length;
  };

  // 獲取鏈表頭部元素
  this.getHead = function () {
    return head.element;
  };

  // 由于鏈表使用了Node類，就需要重寫繼承自JavaScript對象默認的toString()方法，讓其只輸出元素的值
  this.toString = function () {
    var currentNode = head;
    var string = "";

    while (currentNode) {
      
      string += "," + currentNode.element;
      currentNode = currentNode.next;
    }

    return string.slice(1);    
  };

  this.print = function () {
    console.log(this.toString());
  };

創(chuàng)建雙向鏈表實例進行測試：

// 創(chuàng)建雙向鏈表
var doublyLinked = new DoublyLinkedList();
console.log(doublyLinked.isEmpty());              // true
doublyLinked.append("Tom");                       
doublyLinked.append("Peter");
doublyLinked.append("Paul");
doublyLinked.print();                             // "Tom,Peter,Paul"
doublyLinked.insert(0, "Susan");                  
doublyLinked.print();                             // "Susan,Tom,Peter,Paul"
doublyLinked.insert(1, "Jack");                   
doublyLinked.print();                             // "Susan,Jack,Tom,Peter,Paul"
console.log(doublyLinked.getHead());              // "Susan"
console.log(doublyLinked.isEmpty());              // false
console.log(doublyLinked.indexOf("Peter"));       // 3
console.log(doublyLinked.indexOf("Cris"));        // -1
doublyLinked.remove("Tom");                       
doublyLinked.removeAt(2);                         
doublyLinked.print();                             // "Susan,Jack,Paul"

2.3 循環(huán)鏈表

循環(huán)鏈表可以像單向鏈表一樣只有單向引用，也可以像雙向鏈表一樣有雙向引用。循環(huán)鏈表和普通鏈表之間唯一的區(qū)別在于，最后一個元素指向下一個元素的指針（next）不是引用null，而是指向第一個元素（head）。這里就不進行代碼實現(xiàn)了，大家可以結合上面的單向鏈表和雙向鏈表自己實現(xiàn)一個循環(huán)鏈表。

三、結束

本文會同步到我的個人博客，完整代碼可以到我的github倉庫查看，如果對你有幫助的話歡迎點一個Star~~

歡迎關注我的公眾號

云服務器 GPU云服務器鏈表數(shù)據(jù)結構隊列 linux 數(shù)據(jù)結構鏈表 java鏈表數(shù)據(jù)結構 C++數(shù)據(jù)結構鏈表

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

轉載請注明本文地址：http://m.hztianpu.com/yun/96564.html

用 JavaScript 實現(xiàn)鏈表操作 - 04 Insert Nth Node

摘要：給定一個鏈表，一個范圍在內(nèi)的索引號，和一個數(shù)據(jù)，這個函數(shù)會生成一個新的節(jié)點并插入到指定的索引位置，并始終返回鏈表的頭。的返回值一定是個鏈表，我們把它賦值給就行。但這個例子的邊界情況是返回值不同如果，返回新節(jié)點。 TL;DR 插入第 N 個節(jié)點。系列目錄見前言和目錄。需求實現(xiàn)一個 insertNth() 方法，在鏈表的第 N 個索引處插入一個新節(jié)點。 insertNth() 可以...

894974231 2019-08-22 10:50 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區(qū)別...

tain335 2019-08-26 10:28 評論0 收藏0
【Redis5源碼學習】2019-04-17 壓縮列表ziplist

摘要：記錄壓縮列表總共占用的字節(jié)數(shù)，在對壓縮列表進行內(nèi)存重分配時使用個字節(jié)。為十六進制值，標記一個壓縮列表的末尾具體的數(shù)據(jù)存放在中。占用或字節(jié)表示當前存儲數(shù)據(jù)的類型與數(shù)據(jù)的長度。在學習的同時，如果沒有經(jīng)過自己的思考，收效甚微。 baiyan全部視頻：https://segmentfault.com/a/11... 為什么需要ziplist 乍一看標題，我們可能還不知道ziplist是何許人也...

church 2019-08-06 13:45 評論0 收藏0
集合框架知識系列04 LinkedList的源碼分析和使用示例

摘要：一簡介內(nèi)部是通過雙向鏈表存儲的，提供順序訪問。繼承了，實現(xiàn)在迭代器上的隨機訪問。四總結本節(jié)分析了的源碼的用法。實現(xiàn)了接口，內(nèi)部通過鏈表實現(xiàn)，能夠實現(xiàn)鏈表隊列棧和雙端隊列等數(shù)據(jù)結構的功能。一、LinkedList簡介 LinkedList內(nèi)部是通過雙向鏈表存儲的，提供順序訪問。繼承了AbstractSequentialList，實現(xiàn)在迭代器上的隨機訪問。并且，還實現(xiàn)了List、Dequ...

CntChen 2019-08-16 13:35 評論0 收藏0
【Redis5源碼學習】2019-04-19 字典dict

摘要：全部視頻每日學習記錄使用錄像設備記錄每天的學習字典是啥，即字典，也被稱為哈希表。通常情況下，一個長這樣在這個哈希表中，每個存儲單元被稱為一個桶。完成之后，新哈希表就會被置為，為線上提供服務。 baiyan 全部視頻：【每日學習記錄】使用錄像設備記錄每天的學習字典是啥 dict，即字典，也被稱為哈希表hashtable。在redis的五大數(shù)據(jù)結構中，有如下兩種情形會使用dict結構： ...

terasum 2019-08-06 13:45 評論0 收藏0