链表节点

链表中的节点类型

  1. class Node {
  2.     constructor(data) {
  3.         this.data = data;  // 节点的数据
  4.         this.prev = null;  // 节点的前指针
  5.         this.next = null;  // 节点的下一个指针
  6.     }
  7. }

用prev和next属性是为了实现双向链表。

单向链表

链表 - 图1

单链表的基本操作方法

  1. class SingleList {
  2.   constructor() {
  3.     this.size = 0;  // 单链表的长度
  4.     this.head = new Node('head');  // 表头节点
  5.     this.currNode = '';  // 当前节点的指向
  6.   }
  7.   find(item)  // 在单链表中寻找item元素
  8.   insert(item, element);  // 向单链表中item节点后插入element元素
  9.   remove(item);  // 在单链表中删除一个节点
  10.   append(element);  // 在单链表的尾部添加元素
  11.   findLast();  // 获取单链表的最后一个节点
  12.   isEmpty();  // 判断单链表是否为空
  13.   show();  // 显示当前节点
  14.   getLength();  // 获取单链表的长度
  15.   advance(n, currNode);  // 从当前节点向前移动n个位置
  16.   display();  // 单链表的遍历显示
  17.   clear();  // 清空单链表
  18.   reverseList(); // 翻转链表
  19. }

单链表中寻找item元素

  1. find(item) {
  2.   let currNode = this.head;
  3.   // 判断currNode的element是否等于item
  4.   while (currNode && currNode.element !== item) {
  5.     currNode = currNode.next;
  6.   }
  7.   return currNode;
  8. }

查询最后节点

当前节点的next指针不为空就一直向下遍历，直到当前节点的next为空时即是最后一个节点

  1. findLast() {
  2.   let currNode = this.head;
  3.   while (currNode.next) {
  4.     currNode = currNode.next;
  5.   }
  6.   return currNode;
  7. }

向前移动n位

设置初始节点为head。
当向前移动的位数超过单链表的长度时，总是返回单链表的最后一个节点。

  1. advance(n, currNode = this.head) {
  2.   this.currNode = currNode;
  3.   while (n-- && this.currNode.next) {
  4.     this.currNode = this.currNode.next;
  5.   }
  6.   return this.currNode;
  7. }

向尾部添加元素

在尾部添加元素时使用到了findLast()方法，findLast()方法返回单链表的最后一个元素，因此在单链表的尾部添加元素时，只要将新元素赋值给单链表的最后一个元素的next指针即可。

  1. append(element) {
  2.   // 新建要插入的节点
  3.   let newNode = new Node(element);
  4.   // 查处最后节点
  5.   let currNode = this.findLast();
  6.   // 最后节点的next指向创建的节点
  7.   currNode.next = newNode;
  8.   // 将链表长度+1
  9.   this.size++;
  10. }

向单链表插入数据

  1. insert(item, element) {
  2.   // 先查找插入时的参考元素是否存在
  3.   let itemNode = this.find(item);
  4.   if (!itemNode) {
  5.     // 如果不存在，则不处理
  6.     return;
  7.   }
  8.   let newNode = new Node(element);
  10.   newNode.next = itemNode.next;
  11.   itemNode.next = newNode;
  12.   this.size++;
  13. }

单链表中删除元素

  • 要删除head节点
  • 删除不存在的节点
  • 删除存在的节点，先查询出item的位置currNode，将currNode.next设置为其后面一个元素即可
    1. remove(item) {
    2. // 元素在链表中不存在「2」
    3. let itemNode = this.find(item);
    4. if (!itemNode) {
    5.   return;
    6. }
    7. // 删除head节点「1」
    8. if (item === "head") {
    9.   if (!this.isEmpty()) {
    10.     // this.head = this.head.next;
    11.     return;
    12.   } else {
    13.     this.head.next = null;
    14.     return;
    15.   }
    16. }
    17. let currNode = this.head; //删除存在的节点「3」
    18. // 当前节点的下一个节点不是要查询的元素，向下继续查询
    19. while (currNode.next.element !== item) {
    20.   if (!currNode.next) {
    21.     // 所有节点下一个节点都不存在，说明删除的节点不存在
    22.     return;
    23.   }
    24.   currNode = currNode.next;
    25. }
    26. // 此时当前节点的下一个节点的element 等于要查询的item，则将currNode的next更新
    27. currNode.next = currNode.next.next;
    28. this.size--;
    29. }

    翻转单链表

    1. reverseList() {
    2.   const reverse = (head) => {
    3.     // 如果是空或者只有一个数据时
    4.     if (head === null || head.next === null) return head;
    5.     // 对head的下一个元素进行递归操作
    6.     let newHead = reverse(head.next);
    7.     // 重新设置head元素，将head.next【第二个元素】的next赋值给head
    8.     head.next.next = head;
    9.     // 将head的next设置为空，这样就进行了两个元素的翻转
    10.     head.next = null;
    11.     return newHead;
    12.   };
    13.   this.head = reverse(this.head);
    14.   return this.head;
    15. }
    16. // 使用while循环，非递归
    17. reverseList1() {
    18.   // 获取原链表的头部数据
    19.   let oldHead = this.head;
    20.   if (oldHead === null || oldHead.next === null) return oldHead;
    21.   let newHead = null;
    22.   while (oldHead !== null) {
    23.     // 先把原来链的head下一个数据暂存起来
    24.     let temp = oldHead.next;
    25.     oldHead.next = newHead;
    26.     newHead = oldHead;
    27.     oldHead = temp;
    28.   }
    29.   this.head = newHead;
    30.   return this.head;
    31. }
    单链表完整代码

    单链表测试

    ```javascript let myList = new SingleList(); let arr = [3, 4, 5, 6, 7, 8, 9];

for (let i = 0; i < arr.length; i++) { myList.append(arr[i]); } myList.display(); // head->3->4->5->6->7->8->9

myList.reverseList(); myList.display(); // 9->8->7->6->5->4->3->head myList.reverseList1(); myList.display(); // head->3->4->5->6->7->8->9

console.log(myList.find(4)); // Node {data: 4, prev: null, next: Node}

myList.insert(9, 9.1); myList.insert(3, 3.1); myList.display(); // head->3->3.1->4->5->6->7->8->9->9.1

myList.remove(9.1); myList.remove(3); myList.display(); // head->3.1->4->5->6->7->8->9

console.log(myList.findLast()); // Node {data: 9, prev: null, next: null}

console.log(myList.advance(4)); // Node {data: 6, prev: null, next: Node}

console.log(myList.getLength()); // 7

myList.clear(); myList.display(); // head

  1. <a name="m9iZy"></a>
  2. ### 判断单链表中是否有环
  3. ![](https://cdn.nlark.com/yuque/0/2022/jpeg/737887/1650972636098-d8a29b1e-44ac-419b-af87-355ceb10a4d0.jpeg)
  5. 类似于上图这样的，是一个有环的单链表
  6. ```javascript
  7. var myList = new SingleList()
  8. var arr = ['A', 'B', 'C', 'D', 'E']
  10. arr.forEach(item => myList.append(item))
  12. var B = myList.find('B')
  13. var E = myList.findLast()
  14. E.next = B

用函数判断链表是否有环

使用快慢指针，如果快指针走到最后为null，说明链表没有环，如果两个指针在某个时刻相等，则说明链表有环。

  1. function isLoop (list) {
  2.   // 使用快慢指针
  3.   var p = list.head
  4.   var q = list.head
  6.   while (q) {
  7.     p = p.next
  8.     if (p.next) {
  9.       q = q.next.next
  10.     }
  11.     if (p === q) {
  12.       console.log('链表是环状链表')
  13.       return
  14.     }
  15.   }
  16.   console.log('不是环状链表')
  17. }
  19. isLoop(myList)

单向循环链表

链表 - 图2

单向循环链表结构

单向循环链表继承于单向链表；

  1. class CirSingleList extends SingleList {
  2.   constructor() {
  3.     super();
  4.   }
  6.   // 在单循环链表中寻找最后一个节点
  7.   findLast() {}
  9.   // 在单循环链表中寻找数据
  10.   find(item) {}
  12.   // 在数据为item的节点后面插入数据为element元素的节点
  13.   insert(item, element) {}
  15.   remove(item) {}
  17.   display() {}
  19.   //在尾部添加数据
  20.   append(element) {}
  21. }

寻找单向循环链表的最后一个节点

使用count来标记已经寻找过的节点数目，如果count与单向循环链表长度相等时，说明找到了最后一个节点

  1. findLast() {
  2.   let currNode = this.head;
  3.   let count = 0;
  4.   // 判断链表长度
  5.   while(count++ !== this.size){
  6.     currNode = currNode.next;
  7.   }
  9.   return currNode;
  10. }

查询单向循环链表的一个元素

find()方法，和单链表中的find()方法不同。
由于是环状链表，如果查询不出元素，并且已经到了链表末尾，再继续查找就会无限循环。所以需要加判断查询的是不是最后一个节点。如果是最后一个节点，还未找到，则跳出循环。

  1. find(item) {
  2.   let currNode = this.head;
  3.   let lastNode = this.findLast();
  4.   while (currNode.element !== item) {
  5.     // 判断查找的节点是不是最后一个节点，如果是最后一个节点，则停止循环。
  6.     // 不添加判断 会进入无限循环
  7.     if (currNode === lastNode) {
  8.       currNode = null;
  9.       return;
  10.     }
  11.     currNode = currNode.next;
  12.   }
  13.   return currNode;
  14. }

插入元素

  • 如果单向循环链表是空，直接将新的节点插入到head节点后面，再让新的节点指向自身
  • 要插入的位置处于单向循环链表中间的位置，n节点是新的要插入的节点，只需要将E节点的next指针指向C节点，再将B节点的next指针指向新的E节点就可以

链表 - 图3

  • 要插入的位置处于单向循环链表表头结点后面，新插入D

链表 - 图4

  1. 将D节点的next指针指向头结点后面的第一个节点A。
  2. 第二步将头结点的next指针指向D节点。

  3. 最后将这个单向循环链表的最后一个节点C的next指针指向D节点。

    1. insert(item, element) {
    2. let itemNode = this.find(item);
    3. let newNode = new Node(element);
    5. if (!itemNode) {
    6.  // 如果item在单循环链表中不存在
    7.  return;
    8. }
    10. // 插入的位置处于头结点之后，第一个节点之前
    11. if (item === "head") {
    12.  if (this.size === 0) {
    13.    // 当单循环链表为空时
    14.    this.head.next = newNode;
    15.    newNode.next = this.head.next;
    16.  } else {
    17.    // 当单循环链表不空时
    18.    let lastNode = this.findLast();
    19.    newNode.next = this.head.next;
    20.    this.head.next = newNode;
    21.    lastNode.next = newNode;
    22.  }
    24.  this.size++;
    25.  return;
    26. }
    28. // 处于链表中间位置时
    29. newNode.next = itemNode.next;
    30. itemNode.next = newNode;
    32. this.size++;
    33. }

    节点的删除操作

    remove()方法，先用写好的find()方法找到要删除的节点，再用写好的findLast()方法找到最后一个节点。找到要删除的节点后，再次从头结点开始遍历，直到找到要删除节点的前一个节点。

  • 当待删除的节点是第一个节点时，如果此时单向循环链表只有一个节点，直接将此单向循环链表置空即可。
  • 当待删除的节点是第一个节点时，且此时单向循环链表不仅只有一个节点时，此时将头结点的next指针指向待删除节点的下一个节点，并将最后一个节点指向待删除节点的下一个节点。

链表 - 图5

  • 除了前面的两种情况之外，只要将待删除节点的前一个节点next指针指向待删除节点的后一个节点即可

    1. remove(item) {
    2. let curNode = this.find(item); // 找到待删除节点
    3. let lastNode = this.findLast(); // 找到最后一个节点
    4. let preCurNode = this.head;
    6. // 找到待删除节点的前一个节点
    7. while (preCurNode.next !== curNode) {
    8.   preCurNode = preCurNode.next;
    9. }
    11. if (curNode == this.head.next) {
    12.   // 如果当前节点是第一个节点
    13.   //头节点的后一个节点
    14.   if (this.size == 1) {
    15.     //只剩最后一个节点
    16.     this.head.next = null;
    17.   } else {
    18.     //还有其他节点
    19.     this.head.next = curNode.next;
    20.     lastNode.next = curNode.next;
    21.   }
    22. } else {
    23.   // 其他情况
    24.   preCurNode.next = curNode.next;
    25. }
    27. this.size--;
    28. }

    显示所有节点

    遍历展示此链表，到达链表末尾，停止遍历

    1. display() {
    2. let description = "head";
    3. let currNode = this.head;
    4. let lastNode = this.findLast();
    5. // 判断节点是否到了尾节点
    6. while (currNode !== lastNode) {
    7.   currNode = currNode.next;
    8.   description += `->${currNode.element}`;
    9. }
    11. console.log(description);
    12. }

    在链表最后追加元素

    单向循环链表的尾部添加数据。

    1. append(element) {
    2. let lastNode = this.findLast();
    3. let newNode = new Node(element);
    5. lastNode.next = newNode;
    6. newNode.next = this.head.next;
    8. this.size++;
    9. }

    完整的单向循环链表代码

    单向循环链表解决的实际问题

    魔术师牌的排序

    魔术师手中有A、2、3……J、Q、K十三张黑桃扑克牌。在表演魔术前，魔术师已经将他们依照一定的顺序叠放好（有花色的一面朝下）。 魔术表演过程为：一开始，魔术师数1，然后把最上面的那张牌翻过来，是黑桃A；然后将其放到桌面上； 第二次,魔术师数1、2；将第一张牌放到这些牌的最以下，将第二张牌翻转过来，正好是黑桃2； 第三次，魔术师数1、2、3；将第1、2张牌依次放到这些牌的最以下，将第三张牌翻过来正好是黑桃3； 以此类推，直到将全部的牌都翻出来为止。问原来牌的顺序是怎样

  1. // 魔术师发牌问题
  3. const { CirSingleList } = require("../CirSingleList");
  4. let magicList = new CirSingleList();
  6. function magician() {
  7.   let arr = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"];
  9.   for (let i = 0; i < 13; i++) {
  10.     magicList.append(""); // 单向循环链表的每项节点值为空
  11.   }
  13.   let n = 1;
  14.   let toColor = undefined;
  16.   while (n <= 13) {
  17.     let forward = n; // 记录此次循环需要的次数
  19.     while (forward != 0) {
  20.       toColor = magicList.advance(1, toColor); // 前进一个节点
  22.       if (!toColor.element) {
  23.         forward--; // 在节点值为空的时候forward减1，就可以继续前进一步
  24.       }
  25.     }
  27.     toColor.element = arr[n - 1];
  28.     n++;
  29.   }
  31.   magicList.display();
  32. }
  34. magician();

约瑟夫环，避免被杀死

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。 于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后接着下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 

  1. // n个人围成一圈，杀死第m个人，直到剩下s个人为止
  2. // 输出存活的人的序号
  3. const { CirSingleList } = require("../CirSingleList");
  4. let myList = new CirSingleList();
  6. function killPerson(n, m, s) {
  7.   for (let i = 1; i <= n; i++) {
  8.     myList.append(i);
  9.   }
  11.   let currNode = undefined;
  12.   let toKill = null;
  14.   while (myList.size > s) {
  15.     // 直到剩下s个节点为止
  16.     toKill = myList.advance(m, currNode); // 从currNode开始，前进m个节点
  17.     currNode = toKill; // 保存要删除的节点作为下一次循环的参数
  18.     myList.remove(toKill.element); // 删除第m个节点
  19.   }
  21.   myList.display();
  22. }
  24. killPerson(41, 3, 2);  // head->16->31  16和31是避免被杀死的人
  25. // killPerson(5, 4, 1); // head->1

双向链表

image.png

双向链表结构

双向链表继承单向循环链表，双向链表多了一个向前的指针。

  1. //双向链表
  2.  class DbList extends CirSingleList {
  3.     constructor() {
  4.         super();
  5.     }
  6.     // 在item后添加newElement
  7.     insert(item， newElement) {
  9.     }
  11.     // 从双向链表中移除item节点
  12.     remove(item) {
  14.     }
  16.     // 反向遍历
  17.     reverseDisplay() {
  19.     }
  21.     // 在尾部添加数据
  22.     append(element) {
  24.     }
  25. }

双向链表的插入方法

插入的位置在中间和结尾，可以通过当前节点的next指针是否为空来区分

  • 插入节点的位置在中间时：如下图所示，第一步将n节点的next指针指向B节点，再将B节点的prev指针指向n节点。第二步将A节点的next指针指向n节点，再将n节点的prev指针指向A节点就可以

链表 - 图7

  • 插入节点的位置在末尾时比较简单，只要将最后一个节点的next指针指向新的节点，再将新节点的prev指针指向之前的最后一个节点

链表 - 图8

  1. insert(item, newElement) {
  2.   let newNode = new Node(newElement);
  3.   let itemNode = this.find(item);
  4.   // 如果itemNode.next有值，则说明是往中间插入值
  5.   if (itemNode.next) {
  6.     newNode.next = itemNode.next;
  7.     itemNode.next.prev = newNode;
  8.     itemNode.next = newNode;
  9.     newNode.prev = itemNode;
  10.   } else {
  11.     itemNode.next = newNode;
  12.     newNode.prev = itemNode;
  13.   }
  14.   this.size++;
  15. }

双向链表移除元素

删除节点时，也可以分为几种情况

  • 当传入的参数item为head时，约定将此链表清空
  • 当节点值为item的节点存在于该链表中时，如果此时要删除的节点恰好是最后一个节点，只要直接将最后一个节点删除
  • 当节点值为item的节点存在，且处于链表中间位置。B表示待删除的节点。此时只需要将A的next指针指向C节点。然后再将C的prev指针指向A节点即可。在代码的实现过程中，待删除节点B起到了“承前启后”的作用，通过B向后可以找到C，向前可以找到A

链表 - 图9

  1. remove(item) {
  2.   let curNode = this.find(item);
  3.   // 删除头节点
  4.   if (item === "head") {
  5.     this.head.next = null;
  6.     this.head.prev = null;
  7.     this.size = 0;
  8.     return;
  9.   }
  10.   if (curNode) {
  11.     // 没有next节点，说明是尾节点
  12.     if (!curNode.next) {
  13.       curNode.prev.next = null;
  14.     } else {
  15.       curNode.next.prev = curNode.prev;
  16.       curNode.prev.next = curNode.next;
  17.     }
  18.     curNode = null;
  19.     this.size--;
  20.   }
  21. }

向链表尾部添加元素

  1. append(element) {
  2.   let lastNode = this.findLast();
  3.   let newNode = new Node(element);
  4.   lastNode.next = newNode;
  5.   newNode.prev = lastNode;
  6.   this.size++;
  7. }

反向遍历展示

  1. reverseDisplay() {
  2.   let description = "";
  3.   let currNode = this.findLast();
  4.   while (currNode.element !== "head") {
  5.     description += `${currNode.element}<->`;
  6.     currNode = currNode.prev;
  7.   }
  8.   description += 'head';
  9.   console.log(description);
  10. }

双向链表操作测试

  1. let test = new DbList();
  3. let arr = [1, 2, 3, 4, 5, 6, 7];
  5. for(let i=0; i<arr.length; i++){
  6.     test.append(arr[i]);
  7. }
  9. test.display();  // head->1->2->3->4->5->6->7
  11. test.insert(7, 8);
  12. test.display();  // head->1->2->3->4->5->6->7->8
  14. test.insert(`head`, 0.5);
  15. test.display();  // head->0.5->1->2->3->4->5->6->7->8
  17. test.reverseDisplay();  // 8->7->6->5->4->3->2->1->0.5->head
  19. test.remove(0.5);  // head->1->2->3->4->5->6->7->8
  20. test.display();
  22. test.remove(8);  
  23. test.display();  // head->1->2->3->4->5->6->7

完整代码

双向循环链表

image.png

代码结构

  1. //双向循环链表
  2. class CirDbList extends DbList {
  3.     constructor() {
  4.         super();
  5.         this.head.next = this.head;
  6.         this.head.prev = this.head;
  7.     }
  9.     // 向双向循环链表中插入数据
  10.     insert(element, item) {
  12.     }
  14.     // 从双向循环链表中删除数据
  15.     remove(item) {
  17.     }
  19.     // 在尾部添加数据
  20.     append(element) {
  22.     }
  23. }

继承于双向链表的方法

  1. // 在链表中寻找最后一个节点
  2. findLast() {
  3.   let currNode = this.head;
  4.   let count = 0;
  6.   while(count++ !== this.size){
  7.     currNode = currNode.next;
  8.   }
  10.   return currNode;
  11. }
  12. // 遍历链表
  13. display() {
  14.   let result = 'head';
  15.   let currNode = this.head;
  16.   let lastNode = this.findLast();
  18.   while(currNode !== lastNode) {
  19.     currNode = currNode.next;
  20.     result += `->${currNode.data}`;
  21.   }
  23.   console.log(result);
  24. }
  26. // 在链表中寻找数据
  27. find(item) {
  28.   let currNode = this.head;
  29.   let lastNode = this.findLast();
  31.   while(currNode.data !== item) {
  32.     // 判断当前节点是不是最后一个节点
  33.     if(currNode === lastNode) {  
  34.       currNode = null;
  35.       break;
  36.     }
  37.     currNode = currNode.next;
  38.   }
  40.   return currNode;
  41. }
  43. // 反向遍历
  44. reverseDisplay() {
  45.   let result = '';
  46.   let currNode = this.findLast();
  48.   while (currNode.data !== 'head') {
  49.     result += `${currNode.data}->`;
  50.     currNode = currNode.prev;
  51.   }
  53.   result += `head`;
  54.   console.log(result);
  55. }

双向循环链表的插入方法

  1. insert(item, element) {
  2.   let itemNode = this.find(item);
  3.   let newNode = new Node(element);
  5.   // 双向循环链表中插入是双向链表中间插入值的实现
  6.   newNode.next = itemNode.next;
  7.   itemNode.next.prev = newNode;
  8.   itemNode.next = newNode;
  9.   newNode.prev = itemNode;
  10.   this.size++;
  11. }

双向循环链表的删除方法

  1. remove(item) {
  2.   // 删除头节点
  3.   if (item === "head") {
  4.     this.head.next = this.head;
  5.     this.head.prev = this.head;
  6.     this.size = 0;
  7.     return;
  8.   }
  9.   let currNode = this.find(item);
  10.   if (currNode) {
  11.     currNode.next.prev = currNode.prev;
  12.     currNode.prev.next = currNode.next;
  13.     this.size--;
  14.   }
  15. }

双向循环链表从尾部添加节点

  • 首先找到当前链表的最后一个节点
  • 将新节点new的next指针指向head节点
  • 将head节点的prev节点指向新节点new
  • 将last节点的next指针指向新节点new，新节点new的prev指针指向last节点

链表 - 图11

  1. append(element) {
  2.   let lastNode = this.findLast();
  3.   let newNode = new Node(element);
  4.   // lastNode.next指向head，head.prev重新被赋值为newNode
  5.   lastNode.next = newNode;
  6.   newNode.prev = lastNode;
  7.   newNode.next = lastNode.next;
  8.   lastNode.next.prev = newNode;
  10.   this.size++;
  11. }

双向循环链表代码

简书：JavaScript实现数据结构
知乎：JavaScript描述数据结构