javascript數據結構與算法（一）單向鏈表與雙向鏈表

William_Sang 發布于2019-08-26 10:48 / 2126人閱讀

摘要：創建雙向鏈表創建節點繼承添加前繼指針初始化雙向鏈表對鏈表最后一個元素進行引用插入操作尾插法任意位置添加元素刪除操作刪除特定位置的元素查詢操作查詢元素的位置查詢尾部元素修改操作清空雙向鏈表雙向鏈表對象轉為字符串

線性表（List）：零個或者多個數據元素的有限序列。線性表是一個序列，具有一對一的關系，而不能具備一對多的關系。線性表要求有限性，數據類型也要相同。
本文參考的主要是大話數據結構的原理進行理解，用Javascript實現線性表的相關操作。

創建單向鏈表：

//創建節點
class Node{
    constructor(element){
        this.element = element;//數據域
        this.next = undefined;//指針域
    }
};
//判斷傳入的對象與鏈表的元素是否相等，待會實現indexOf()要用到，在這里先寫上
function(a,b){
    return a == b;
}; 
//創建鏈表
class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn;
    this.count = 0;
    this.head = undefined;
    }
};

查詢操作 判斷單向表是否為空

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

計算單向鏈表的長度

size() {
    return this.count;
  }

查詢鏈表的某個元素的位置

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;
  }

獲取第一個元素

getHead() {
    return this.head;
  }

獲得元素操作

getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node;
    }
    return undefined;
  }

插入操作 尾插法

push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      // catches null && undefined
      this.head = node;
    } else {
      current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = node;
    }
    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;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

刪除操作 刪除特定位置的元素

removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

直接刪除鏈表的某個元素

remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

修改操作 單向鏈表轉為字符串

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;
  }
}

清空單向鏈表

clear() {
    this.head = undefined;
    this.count = 0;
  }

以上就是單向鏈表的常見操作。

由于單向鏈表只能從頭到尾的遍歷，如果查詢得是下一節點，單向表時間復雜度為O（1），但是要查詢的是上一節點的話，那么時間復雜度就是O(n)。如果鏈表也可以正反遍歷的話，那么查詢操作的時間復雜度就都是O（1）啦，這時我們的前輩就提出了雙向鏈表這一神奇的鏈表。由于雙向鏈表是單向鏈表的拓展，只是多了一個指針，對于查詢操作并沒有幫助，所以實現方法還是跟單向鏈表一樣，這里就不多加闡述。

創建雙向鏈表

//創建節點
class DoublyNode extends Node {
  constructor(element, next, prev) {
    super(element, next);//繼承
    this.prev = prev;//添加前繼指針
  }
};
//初始化雙向鏈表
class DoublyLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
    this.tail = undefined;//對鏈表最后一個元素進行引用
  }

插入操作 尾插法

push(element) {
    const node = new DoublyNode(element);
    if (this.head == null) {
      this.head = node;
      this.tail = node; // NEW
    } else {
      // attach to the tail node // NEW
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.count++;
  }

任意位置添加元素

insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element);
      let current = this.head;
      if (index === 0) {
        if (this.head == null) { // NEW
          this.head = node;
          this.tail = node; // NEW
        } else {
          node.next = this.head;
          this.head.prev = node; // NEW
          this.head = node;
        }
      } else if (index === this.count) { // last item NEW
        current = this.tail;
        current.next = node;
        node.prev = current;
        this.tail = node;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        node.next = current;
        previous.next = node;
        current.prev = node; // NEW
        node.prev = previous; // NEW
      }
      this.count++;
      return true;
    }
    return false;
  }

刪除操作 刪除特定位置的元素

removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = this.head.next;
        // if there is only one item, then we update tail as well //NEW
        if (this.count === 1) {
          // {2}
          this.tail = undefined;
        } else {
          this.head.prev = undefined;
        }
      } else if (index === this.count - 1) {
        // last item //NEW
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        current = this.getElementAt(index);
        const previous = current.prev;
        // link previous with current"s next - skip it to remove
        previous.next = current.next;
        current.next.prev = previous; // NEW
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

查詢操作 查詢元素的位置

indexOf(element) {
    let current = this.head;
    let index = 0;
    while (current != null) {
      if (this.equalsFn(element, current.element)) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }

查詢尾部元素

getTail() {
    return this.tail;
  }

修改操作 清空雙向鏈表

clear() {
    super.clear();
    this.tail = undefined;
  }

雙向鏈表對象轉為字符串

inverseToString() {
    if (this.tail == null) {
      return "";
    }
    let objString = `${this.tail.element}`;
    let previous = this.tail.prev;
    while (previous != null) {
      objString = `${objString},${previous.element}`;
      previous = previous.prev;
    }
    return objString;
  }
}

GPU云服務器云服務器單向鏈表詳解雙向鏈表 java雙向鏈表單向鏈表的操作c語言

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

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

學習JavaScript數據結構與算法（二）：鏈表

摘要：實現移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數據結構與算法二鏈表本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第四篇文章：學習JavaScript數據結構與...

lolomaco 2019-08-22 11:00 評論0 收藏0
Javascript數據結構與算法（二）循環鏈表與有序鏈表

摘要：循環鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。以下就以如何創建棧數據結構為例。循環鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。性能上也跟雙向鏈表差不多，如果position大于length/2，那就可以從尾部開始迭代，可以減少迭代的元素。唯一的區別在于最后一個元素指向下一個元素的指針(tail.next)不是undefine，而是第一個元素（head）。接下來來看一...

YacaToy 2019-08-26 10:49 評論0 收藏0
JavaScript的數據結構與算法（四） —— 雙向鏈表

摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或...

Youngdze 2019-08-21 17:13 評論0 收藏0
【譯】JavaScript數據結構（3）：單向鏈表與雙向鏈表

摘要：計算機科學中最常見的兩種數據結構是單鏈表和雙鏈表。雙向鏈表雙向鏈表具有單鏈表的所有功能，并將其擴展為在鏈表中可以進行雙向遍歷。雙向鏈表的操作我們的鏈表將包括兩個構造函數和。與單鏈表不同，雙向鏈表包含對鏈表開頭和結尾節點的引用。翻譯：瘋狂的技術宅英文：https://code.tutsplus.com/art...說明：本文翻譯自系列文章《Data Structures With Ja...

Chiclaim 2019-08-20 18:20 評論0 收藏0
JavaScript 數據結構與算法之美 - 線性表（數組、棧、隊列、鏈表）

摘要：每個線性表上的數據最多只有前和后兩個方向。數組鏈表隊列棧等就是線性表結構。非線性表數據之間并不是簡單的前后關系。不包含任何元素的棧稱為空棧。移除棧頂的元素，同時返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言基礎知識就像是一座大樓的地基，它決定了我們的技術高度。我們應該多掌握一些可移值的...

kaka 2019-08-23 18:25 評論0 收藏0