专栏首页前端鼓励师从 0 开始学习 JavaScript 数据结构与算法(七)双向链表

从 0 开始学习 JavaScript 数据结构与算法(七)双向链表

单向链表和双向链表

单向链表

  • 只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。
  • 链表相连的过程是单向的,实现原理是上一个节点中有指向下一个节点的引用。
  • 单向链表有一个比较明显的缺点:可以轻松到达下一个节点,但回到前一个节点很难,在实际开发中, 经常会遇到需要回到上一个节点的情况。

双向链表

  • 既可以从头遍历到尾,也可以从尾遍历到头。
  • 链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用,也有一个向后连接的引用。
  • 双向链表可以有效的解决单向链表存在的问题。
  • 双向链表缺点:
    • 每次在插入或删除某个节点时,都需要处理四个引用,而不是两个,实现起来会困难些。
    • 相对于单向链表,所占内存空间更大一些。
    • 但是,相对于双向链表的便利性而言,这些缺点微不足道。

双向链表结构

image

  • 双向链表不仅有 head 指针指向第一个节点,而且有 tail 指针指向最后一个节点。
  • 每一个节点由三部分组成:item 储存数据、prev 指向前一个节点、next 指向后一个节点。
  • 双向链表的第一个节点的 prev 指向 null。
  • 双向链表的最后一个节点的 next 指向 null。

双向链表常见的操作

  • append(element) 向链表尾部追加一个新元素。
  • insert(position, element) 向链表的指定位置插入一个新元素。
  • getElement(position) 获取指定位置的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
  • update(position, element) 修改指定位置上的元素。
  • removeAt(position) 从链表中的删除指定位置的元素。
  • remove(element) 从链表删除指定的元素。
  • isEmpty() 如果链表中不包含任何元素,返回 trun,如果链表长度大于 0 则返回 false
  • size() 返回链表包含的元素个数,与数组的 length 属性类似。
  • toString() 由于链表项使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString 方法,让其只输出元素的值。
  • forwardString() 返回正向遍历节点字符串形式。
  • backwordString() 返回反向遍历的节点的字符串形式。

双向链表的封装

创建双向链表类 DoublyLinkedList

  • DoublyNode 类继承单向链表的 Node 类,新添加 this.prev 属性,该属性用于指向上一个节点。
  • DoublyLinkedList 类继承 LinkedList 类,新添加 this.tail 属性,该属性指向末尾的节点。
// 双向链表的节点类(继承单向链表的节点类)
class DoublyNode extends Node {
  constructor(element) {
    super(element);
    this.prev = null;
  }
}

// 双向链表类继承单向链表类
class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    this.tail = null;
  }
}

append(element)

// append(element) 往双向链表尾部追加一个新的元素
// 重写 append()
append(element) {

// 1、创建双向链表节点
const newNode = new DoublyNode(element);

// 2、追加元素
if (this.head === null) {
  this.head = newNode;
  this.tail = newNode;
} else {
  // !!跟单向链表不同,不用通过循环找到最后一个节点
  // 巧妙之处
  this.tail.next = newNode;
  newNode.prev = this.tail;
  this.tail = newNode;
}

this.length++;
}

insert(position, element)

// insert(position, data) 插入元素
// 重写 insert()
insert(position, element) {
    // 1、position 越界判断
    if (position < 0 || position > this.length) return false;

    // 2、创建新的双向链表节点
    const newNode = new DoublyNode(element);

    // 3、判断多种插入情况
    if (position === 0) { // 在第 0 个位置插入

      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        //== 巧妙之处:相处腾出 this.head 空间,留个 newNode 来赋值 ==//
        newNode.next = this.head;
        this.head.perv = newNode;
        this.head = newNode;
      }

    } else if (position === this.length) { // 在最后一个位置插入

      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else { // 在 0 ~ this.length 位置中间插入

      let targetIndex = 0;
      let currentNode = this.head;
      let previousNode = null;

      // 找到要插入位置的节点
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 交换节点信息
      previousNode.next = newNode;
      newNode.prev = previousNode;

      newNode.next = currentNode;
      currentNode.prev = newNode;
    }

    this.length++;

    return true;
  }

insert(position, element)

// insert(position, data) 插入元素
// 重写 insert()
  insert(position, element) {
    // 1、position 越界判断
    if (position < 0 || position > this.length) return false;

    // 2、创建新的双向链表节点
    const newNode = new DoublyNode(element);

    // 3、判断多种插入情况
    if (position === 0) { // 在第 0 个位置插入

      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        //== 巧妙之处:相处腾出 this.head 空间,留个 newNode 来赋值 ==//
        newNode.next = this.head;
        this.head.perv = newNode;
        this.head = newNode;
      }

    } else if (position === this.length) { // 在最后一个位置插入

      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else { // 在 0 ~ this.length 位置中间插入

      let targetIndex = 0;
      let currentNode = this.head;
      let previousNode = null;

      // 找到要插入位置的节点
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 交换节点信息
      previousNode.next = newNode;
      newNode.prev = previousNode;

      newNode.next = currentNode;
      currentNode.prev = newNode;
    }

    this.length++;

    return true;
  }

removeAt(position)

  // removeAt() 删除指定位置的节点
  // 重写 removeAt()
  removeAt(position) {
    // 1、position 越界判断
    if (position < 0 || position > this.length - 1) return null;

    // 2、根据不同情况删除元素
    let currentNode = this.head;
    if (position === 0) { // 删除第一个节点的情况

      if (this.length === 1) { // 链表内只有一个节点的情况
        this.head = null;
        this.tail = null;
      } else { // 链表内有多个节点的情况
        this.head = this.head.next;
        this.head.prev = null;
      }

    } else if (position === this.length - 1) { // 删除最后一个节点的情况

      currentNode = this.tail;
      this.tail.prev.next = null;
      this.tail = this.tail.prev;

    } else { // 删除 0 ~ this.length - 1 里面节点的情况

      let targetIndex = 0;
      let previousNode = null;
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      previousNode.next = currentNode.next;
      currentNode.next.perv = previousNode;

    }

    this.length--;
    return currentNode.data;
  }

update(position, data)

  // update(position, data) 修改指定位置的节点
  // 重写 update()
  update(position, data) {
    // 1、删除 position 位置的节点
    const result = this.removeAt(position);

    // 2、在 position 位置插入元素
    this.insert(position, data);
    return result;
  }

forwardToString()

// forwardToString() 链表数据从前往后以字符串形式返回
  forwardToString() {
    let currentNode = this.head;
    let result = '';

    // 遍历所有的节点,拼接为字符串,直到节点为 null
    while (currentNode) {
      result += currentNode.data + '--';
      currentNode = currentNode.next;
    }

    return result;
  }

backwardString()

// backwardString() 链表数据从后往前以字符串形式返回
  backwardString() {
    let currentNode = this.tail;
    let result = '';

    // 遍历所有的节点,拼接为字符串,直到节点为 null
    while (currentNode) {
      result += currentNode.data + '--';
      currentNode = currentNode.prev;
    }

    return result;
  }

其他方法的实现

双向链表的其他方法通过继承单向链表来实现。

完整实现

class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    this.tail = null;
  }

  // ------------ 链表的常见操作 ------------ //
  // append(element) 往双向链表尾部追加一个新的元素
  // 重写 append()
  append(element) {
    // 1、创建双向链表节点
    const newNode = new DoublyNode(element);

    // 2、追加元素
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // !!跟单向链表不同,不用通过循环找到最后一个节点
      // 巧妙之处
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    this.length++;
  }

  // insert(position, data) 插入元素
  // 重写 insert()
  insert(position, element) {
    // 1、position 越界判断
    if (position < 0 || position > this.length) return false;

    // 2、创建新的双向链表节点
    const newNode = new DoublyNode(element);

    // 3、判断多种插入情况
    if (position === 0) {
      // 在第 0 个位置插入

      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        //== 巧妙之处:相处腾出 this.head 空间,留个 newNode 来赋值 ==//
        newNode.next = this.head;
        this.head.perv = newNode;
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 在最后一个位置插入

      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else {
      // 在 0 ~ this.length 位置中间插入

      let targetIndex = 0;
      let currentNode = this.head;
      let previousNode = null;

      // 找到要插入位置的节点
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      // 交换节点信息
      previousNode.next = newNode;
      newNode.prev = previousNode;

      newNode.next = currentNode;
      currentNode.prev = newNode;
    }

    this.length++;

    return true;
  }

  // getData() 继承单向链表
  getData(position) {
    return super.getData(position);
  }

  // indexOf() 继承单向链表
  indexOf(data) {
    return super.indexOf(data);
  }

  // removeAt() 删除指定位置的节点
  // 重写 removeAt()
  removeAt(position) {
    // 1、position 越界判断
    if (position < 0 || position > this.length - 1) return null;

    // 2、根据不同情况删除元素
    let currentNode = this.head;
    if (position === 0) {
      // 删除第一个节点的情况

      if (this.length === 1) {
        // 链表内只有一个节点的情况
        this.head = null;
        this.tail = null;
      } else {
        // 链表内有多个节点的情况
        this.head = this.head.next;
        this.head.prev = null;
      }
    } else if (position === this.length - 1) {
      // 删除最后一个节点的情况

      currentNode = this.tail;
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    } else {
      // 删除 0 ~ this.length - 1 里面节点的情况

      let targetIndex = 0;
      let previousNode = null;
      while (targetIndex++ < position) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }

      previousNode.next = currentNode.next;
      currentNode.next.perv = previousNode;
    }

    this.length--;
    return currentNode.data;
  }

  // update(position, data) 修改指定位置的节点
  // 重写 update()
  update(position, data) {
    // 1、删除 position 位置的节点
    const result = this.removeAt(position);

    // 2、在 position 位置插入元素
    this.insert(position, data);
    return result;
  }

  // remove(data) 删除指定 data 所在的节点(继承单向链表)
  remove(data) {
    return super.remove(data);
  }

  // isEmpty() 判断链表是否为空
  isEmpty() {
    return super.isEmpty();
  }

  // size() 获取链表的长度
  size() {
    return super.size();
  }

  // forwardToString() 链表数据从前往后以字符串形式返回
  forwardToString() {
    let currentNode = this.head;
    let result = "";

    // 遍历所有的节点,拼接为字符串,直到节点为 null
    while (currentNode) {
      result += currentNode.data + "--";
      currentNode = currentNode.next;
    }

    return result;
  }

  // backwardString() 链表数据从后往前以字符串形式返回
  backwardString() {
    let currentNode = this.tail;
    let result = "";

    // 遍历所有的节点,拼接为字符串,直到节点为 null
    while (currentNode) {
      result += currentNode.data + "--";
      currentNode = currentNode.prev;
    }

    return result;
  }
}

代码测试

const doublyLinkedList = new DoublyLinkedList();

// append() 测试
doublyLinkedList.append("ZZ");
doublyLinkedList.append("XX");
doublyLinkedList.append("CC");
console.log(doublyLinkedList);

// insert() 测试
doublyLinkedList.insert(0, "00");
doublyLinkedList.insert(2, "22");
console.log(doublyLinkedList);

// getData() 测试
console.log(doublyLinkedList.getData(1)); //--> ZZ

// indexOf() 测试
console.log(doublyLinkedList.indexOf("XX")); //--> 3
console.log(doublyLinkedList);

// removeAt() 测试
doublyLinkedList.removeAt(0);
doublyLinkedList.removeAt(1);
console.log(doublyLinkedList);

// update() 测试
doublyLinkedList.update(0, "111111");
console.log(doublyLinkedList);

// remove() 测试
console.log(doublyLinkedList.remove("111111"));
console.log(doublyLinkedList.remove("22222"));
console.log(doublyLinkedList);

// forwardToString() 测试
console.log(doublyLinkedList.forwardToString());

// backwardString() 测试
console.log(doublyLinkedList.backwardString());

本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

参考资料

[1]

GitHub 仓库: https://github.com/XPoet/js-data-structures-and-algorithms

专辑:

从 0 开始学习 JavaScript 数据结构与算法(一)前言

从 0 开始学习 JavaScript 数据结构与算法(二)数组结构

从 0 开始学习 JavaScript 数据结构与算法(三)栈

从 0 开始学习 JavaScript 数据结构与算法(四)队列

从 0 开始学习 JavaScript 数据结构与算法(五)优先队列

从 0 开始学习 JavaScript 数据结构与算法(六)单向链表

本文分享自微信公众号 - 前端鼓励师(FE-Cheerleaders),作者:XPoet

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从 0 开始学习 JavaScript 数据结构与算法(六)单向链表

    单向链表类似于火车,有一个火车头,火车头会连接一个节点,节点上有乘客,并且这个节点会连接下一个节点,以此类推。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十)哈希表

    哈希表是一种非常重要的数据结构,几乎所有的编程语言都直接或者间接应用这种数据结构。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(三)栈

    数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。但是有时候,我们为了实现某些功能,必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十一)树

    如图,树结构的组成方式类似于链表,都是由一个个节点连接构成。不过,根据每个父节点子节点数量的不同,每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引...

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十二)图

    在计算机程序设计中,图也是一种非常常见的数据结构,图论其实是一个非常大的话题,在数学上起源于哥尼斯堡七桥问题。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(八)集合

    几乎每种编程语言中,都有集合结构。集合比较常见的实现方式是哈希表,这里使用 JavaScript 的 Object 进行封装。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(九)字典

    本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(四)队列

    队列(Queue)是一种运算受限的线性表,特点:先进先出。(FIFO:First In First Out)

    XPoet
  • 数据结构与算法----双向链表

    PS:前面已经说过线性表的两种表现形式,一种是顺序,另一种是链式,链式的一种普通表现形式就是加入一个指针,前一个的指针指向后一个结点的地址,那么还有一种形式就是...

    cMusketeer
  • 数据结构与算法-双向链表

    cwl_java
  • 从 0 开始学习 JavaScript 数据结构与算法(五)优先队列

    XPoet
  • python算法与数据结构-双向链表(40)

      一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最...

    Se7eN_HOU
  • python算法与数据结构-双向链表(40)

      一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最...

    Se7eN_HOU
  • 数据结构与算法(五)-线性表之双向链表与双向循环链表

    前言:前面介绍了循环链表,虽然循环链表可以解决单链表每次遍历只能从头结点开始,但是对于查询某一节点的上一节点,还是颇为复杂繁琐,所以可以在结点中加入前一个节点的...

  • 20120918-双向链表类定义《数据结构与算法分析》

    将新的节点插入双向链表的时候: iterator insert(iterator itr,const Object & x)//向双向链表中插入一个x节点 { ...

    用户1154259
  • 从0开始的Python学习012数据结构&对象与类

    在Python中三种内建的数据结构--列表、元组和字典。学会了使用它们会使编程变得的简单。

    Happy、Liu
  • 数据结构与算法学习笔记之先进先出的队列 数据结构与算法学习笔记之写链表代码的正确姿势(下)数据结构与算法学习笔记之 提高读取性能的链表(上)数据结构与算法学习笔记之 从0编号的数组数据结构与算法学

      队列是一种非常实用的数据结构,类似于生活中发排队,可应用于生活,开发中各个方面,比如共享打印机(先请求先打印),消息队列。你想知道他们是怎么工作的么。那就来...

    Dawnzhang
  • 从Go语言开始,彻底学懂数据结构与算法 -- 线性表

    用一个定长数组data[]存储数据,最大空间为Maxsize,用length记录实际的元素个数,即数组的长度。

    宇宙之一粟
  • 【数据结构与算法】详解什么是双向链表,并用代码手动实现一个双向链表

    上一篇文章讲解了链表的相关知识,并用代码实现了一个链表结构。那么本文将介绍一下另一种特殊的链表结构,叫做 双向链表。 顾名思义,普通的链表都是从 head 开始...

    @零一

扫码关注云+社区

领取腾讯云代金券