javascript数据结构与算法（一）单向链表与双向链表

William_Sang 发布于2019-08-26 10:48 / 1946人阅读

摘要：创建双向链表创建节点继承添加前继指针初始化双向链表对链表最后一个元素进行引用插入操作尾插法任意位置添加元素删除操作删除特定位置的元素查询操作查询元素的位置查询尾部元素修改操作清空双向链表双向链表对象转为字符串

线性表（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;
  }
}

私有云服务器托管单向链表详解双向链表 java双向链表单向链表的操作c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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