[个人心得]数据结构之双链表

jokester 发布于2019-08-21 17:54 / 1908人阅读

摘要：一般我们都构造双向循环链表。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。单向循环链表双向循环链表单向循环链表是在单链表基础上，将最后一个节点的指针指向链表头。

维基百科

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

又上面可知，双向链表与单链表的区别在于，双向链表的每个节点都有一个指向前一个的指针（previous）。
想了解单链表，可以看看我上一遍写的单链表。

1.先创建节点的类。

class Node {
  constructor (element) {
    this.elememt = element;
    this.previous = null;  // 这个是指向前一个的指针。
    this.next = null;
  }
}

2.再创建双向链表的类。

class DoubleLinkedList {
  constructor () {
    this.head = null;
    this.length = 0;
  }
}

接下来给双向联表添加一些方法（一下方法都是在双向链表类里面写的）。

Append

/**
   * 
   * @param element 用来实例节点的数据,什么数据类型都行. 
   */
  append (element) {
    let node = new Node(element), current;

    if (!this.length) {                 // 长度为0，则是新的链表。
      this.head = node;                 // 链表的头指向新的node。
    } else {
      current = this.head;              // current获得指向第一个节点的指针。

      while (current.next) {           // 当前node.next存在。
        current = current.next;        // 如果当前节点（current）的next不为null，那么current.next这个指针就给了current。
      }                                // current的下一个为null的时候，退出循环。
      current.next = node;             // current.next为null退出循环（即已到了最后一个节点）,那么它的next为node
      node.previous = current;         // 新加入的node的前一个就是current。
    }
    this.length++;                     // 长度加一，别忘咯。
    console.log("Append successfully!");
}

InsertNode

/**
   * @param element
   * @param {Number} position 要插入的某个位置. 
   */
  insertNode (element, position) {
    if (position >= 0 && position <= this.length) {
    
      let node = new Node(element),
        front,
        index = 0,
        current = this.head;

      if (!position) {                 // 如果插入的位置为 0 。
        this.head = node;
        node.next = current;           // node的后一个是之前head所指的，即是current。
      } else {
      
        while (index++ < position) {
          front = current;             // 当前变为前一个。
          current = current.next;      // 下一个就变为当前
        }
        
        front.next = current.previous = node; // 前一个的next 和 当前的previous 是node。
        node.previous = front;         // 插入的node的前一个为front。
        node.next = current;           // 插入的node的后一个是current。
      }
      
      this.length++;
      console.log("Insert successfully!");
    } else {
      throw new Error("插入的位置有误啊!");
    }
}

RemoveNode

/**
   * @param {Number} position 
   */
  removeNode (position) {
    if (position > -1 && position < this.length) {
    
      let current = this.head, front, index = 0;

      if (!position) {                           // 位置为 0 。
        this.head = current.next;
        current.next.previous = this.previous;
      } else {
      
        while (index++ < position) {
          front = current;
          current = current.next;
        }
        
        if (current.next) {                      // 这里判断当前node的下一个是否为 null。（例如要删除最后一个是node.next是null的）
          current.next.previous = front;         // 当前node的下一个的previous为front。（有点绕口）
        }
        
        front.next = current.next;               // 前一个的下一个为current的下一个。 (...绕口)
      }
      this.length--;
      console.log("Remove successfully!");
    } else {
      throw new Error("移除的位置有误啊！");
    }
}

Print

print () {
    let arr = [this.head];
    let node = this.head;
    
    while (node.next) {
      node = node.next;
      arr.push(node);
    }
    
    arr.map( (x, index) => console.log(`第${index + 1}个节点是`, x));
}

附上个人源码

循环链表 ----（维基百科）

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

1.单向循环链表

2.双向循环链表

单向循环链表是在单链表基础上，将最后一个节点的next指针指向链表头（head）。

双向循环链表是在双向链表基础上，将最后一个节点的next指针指向链表头（head）。

就写到这里咯。你问我怎么不实现循环链表？这个就...你们实现吧，程序猿嘛，要多动手，多动手。
谢谢大家。

idc机房托管超融合服务器双链表 php之个人博客数据仓库心得双链

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

转载请注明本文地址：https://www.ucloud.cn/yun/90191.html

实战PHP数据结构基础之双链表

摘要：什么是双链表上一篇实战数据结构基础之单链表说到单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。什么是双链表？上一篇实战PHP数据结构基础之单链表说到单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。而双链表每个节点有两个指针域，分别指向前驱...

Michael_Lin 2019-07-01 10:07 评论0 收藏0
数据结构[双链表的实现，以及双链表和单链表之间的比较，链表和顺序表的优劣]

摘要：它在单链表的基础上优化了很多，例如尾插法等就不用了逐个遍历链表节点，直接就可以找到链表的为节点，实现与添加的新节点连接。文件在文件中实现双向链表的测试，测试双向链表的功能。 ...

xingqiba 2021-09-08 09:36 评论0 收藏0
数据结构 - 收藏集 - 掘金

面试旧敌之红黑树（直白介绍深入理解） - Android - 掘金读完本文你将了解到：什么是红黑树黑色高度红黑树的 5 个特性红黑树的左旋右旋指定节点 x 的左旋右图转成左图指定节点 y 的右旋左图转成右图红黑树的平衡插入二叉查找树的插入插入后调整红黑树结构调整思想插入染红后... java 多线程同步以及线程间通信详解 & 消费者生产者模式 & 死锁 & Thread...

leeon 2019-08-16 10:32 评论0 收藏0
[个人心得]数据结构之单链表

摘要：一个单向链表包含两个值当前节点的值和一个指向下一个节点的链接。为退出循环即已到了最后一个节点那么它的为加入节点后，要把单链表长度加一。第个节点是运行结果个人源码地址单链表就写到这里咯，接下来还会写其他的数据结构本人也在学习当中。维基百科链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。链表中最简单的一种是单向链...

bingchen 2019-08-21 17:53 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0