资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/JavaScript数据结构04 - 链表

JavaScript数据结构04 - 链表

cheukyin / 1050人阅读

摘要：类表示要加入链表的项。循环链表和普通链表之间唯一的区别在于，最后一个元素指向下一个元素的指针不是引用，而是指向第一个元素。这里就不进行代码实现了，大家可以结合上面的单向链表和双向链表自己实现一个循环链表。

一、定义 1.1 概念

前面我们学习了数组这种数据结构。数组（或者也可以称为列表）是一种非常简单的存储数据序列的数据结构。在这一节，我们要学习如何实现和使用链表这种动态的数据结构，这意味着我们可以从中任意添加或移除项，它会按需进行扩容。

要存储多个元素，数组（或列表）可能是最常用的数据结构，它提供了一个便利的[]语法来访问它的元素。然而，这种数据结构有一个缺点：（在大多数强类型语言中）数组的大小是固定的，需要预先分配，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。
（注意：在JavaScript中数组的大小随时可变，不需要预先定义长度）

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。

相对于传统的数组，链表的一个好处在于，添加或删除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。

火车可以当做生活中一个典型的链表的例子。一列火车是由一系列车厢组成的。每节车厢都相互连接。你很容易分离一节车厢，改变它的位置，添加或移除它。

1.2 分类

链表最常用的有三类：

单向链表

双向链表

循环链表

二、链表的实现 2.1 单向链表

创建单向链表类：

</>复制代码 
  1. // SinglyLinkedList
  2. function SinglyLinkedList () {
  3.   function Node (element) {
  4.     this.element = element;
  5.     this.next = null;
  6.   }
  7.   var length = 0;
  8.   var head = null;
  9.   
  10.   this.append = function (element) {};
  11.   this.insert = function (position, element) {};
  12.   this.removeAt = function (position) {};
  13.   this.remove = function (element) {};
  14.   this.indexOf = function (element) {};
  15.   this.isEmpty = function () {};
  16.   this.size = function () {};
  17.   this.getHead = function () {};
  18.   this.toString = function () {};
  19.   this.print = function () {};
  20. }

SinglyLinkedList需要一个辅助类Node。Node类表示要加入链表的项。它包含一个element属性，即要添加到链表的值，以及一个next属性，即指向链表中下一个节点项的指针。

链表里面有一些声明的辅助方法：

append(element)：向链表尾部添加新项

insert(position, element)：向链表的特定位置插入一个新的项

removeAt(position)：从链表的特定位置移除一项

remove(element)：从链表中移除一项

indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1

isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false

size()：返回链表包含的元素个数，与数组的length属性类似

getHead()：返回链表的第一个元素

toString()：由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值

print()：打印链表的所有元素

下面我们来一一实现这些辅助方法：

</>复制代码 
  1.   // 向链表尾部添加一个新的项
  2.   this.append = function (element) {
  3.     var node = new Node(element);
  4.     var currentNode = head;
  5.     // 判断是否为空链表
  6.     if (currentNode === null) {
  7.       // 空链表
  8.       head = node;
  9.     } else {
  10.       // 从head开始一直找到最后一个node
  11.       while (currentNode.next) {
  12.         // 后面还有node
  13.         currentNode = currentNode.next;
  14.       }
  15.       currentNode.next = node;
  16.     }
  17.     length++;
  18.   };
  19.   // 向链表特定位置插入一个新的项
  20.   this.insert = function (position, element) {
  21.     if (position < 0 && position > length) {
  22.       // 越界
  23.       return false;
  24.     } else {
  25.       var node = new Node(element);
  26.       var index = 0;
  27.       var currentNode = head;
  28.       var previousNode;
  29.       if (position === 0) {
  30.         node.next = currentNode;
  31.         head = node;
  32.       } else {
  33.         while (index < position) {
  34.           index++;
  35.           previousNode = currentNode;
  36.           currentNode = currentNode.next; 
  37.         }
  38.   
  39.         previousNode.next = node;
  40.         node.next = currentNode;
  41.       }
  42.       length++;
  43.       return true;
  44.     }
  45.   };
  46.   // 从链表的特定位置移除一项
  47.   this.removeAt = function (position) {
  48.     if (position < 0 && position >= length || length === 0) {
  49.       // 越界
  50.       return false;
  51.     } else {
  52.       var currentNode = head;
  53.       var index = 0;
  54.       var previousNode;
  55.       if (position === 0) {
  56.         head = currentNode.next;
  57.       } else {
  58.         while (index < position) {
  59.           index++;
  60.           previousNode = currentNode;
  61.           currentNode = currentNode.next;
  62.         }
  63.         previousNode.next = currentNode.next;
  64.       }
  65.       length--;
  66.       return true;
  67.     }
  68.   };
  69.   // 从链表的特定位置移除一项
  70.   this.removeAt = function (position) {
  71.     if (position < 0 && position >= length || length === 0) {
  72.       // 越界
  73.       return false;
  74.     } else {
  75.       var currentNode = head;
  76.       var index = 0;
  77.       var previousNode;
  78.       if (position === 0) {
  79.         head = currentNode.next;
  80.       } else {
  81.         while (index < position) {
  82.           index++;
  83.           previousNode = currentNode;
  84.           currentNode = currentNode.next;
  85.         }
  86.         previousNode.next = currentNode.next;
  87.       }
  88.       length--;
  89.       return true;
  90.     }
  91.   };
  92.   // 从链表中移除指定项
  93.   this.remove = function (element) {
  94.     var index = this.indexOf(element);
  95.     return this.removeAt(index);
  96.   };
  97.   // 返回元素在链表的索引，如果链表中没有该元素则返回-1
  98.   this.indexOf = function (element) {
  99.     var currentNode = head;
  100.     var index = 0;
  101.     while (currentNode) {
  102.       if (currentNode.element === element) {
  103.         return index;
  104.       }
  105.       index++;
  106.       currentNode = currentNode.next;
  107.     }
  108.     return -1;
  109.   };
  110.   // 如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false
  111.   this.isEmpty = function () {
  112.     return length == 0;
  113.   };
  114.   // 返回链表包含的元素个数，与数组的length属性类似
  115.   this.size = function () {
  116.     return length;
  117.   };
  118.   // 获取链表头部元素
  119.   this.getHead = function () {
  120.     return head.element;
  121.   };
  122.   // 由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值
  123.   this.toString = function () {
  124.     var currentNode = head;
  125.     var string = "";
  126.     while (currentNode) {
  127.       string += "," + currentNode.element;
  128.       currentNode = currentNode.next;
  129.     }
  130.     return string.slice(1);
  131.   };
  132.   this.print = function () {
  133.     console.log(this.toString());
  134.   };

创建单向链表实例进行测试：

</>复制代码 
  1. // 创建单向链表实例
  2. var singlyLinked = new SinglyLinkedList();
  3. console.log(singlyLinked.removeAt(0));              // true
  4. console.log(singlyLinked.isEmpty());              // true
  5. singlyLinked.append("Tom");                       
  6. singlyLinked.append("Peter");
  7. singlyLinked.append("Paul");
  8. singlyLinked.print();                             // "Tom,Peter,Paul"
  9. singlyLinked.insert(0, "Susan");                  
  10. singlyLinked.print();                             // "Susan,Tom,Peter,Paul"
  11. singlyLinked.insert(1, "Jack");                   
  12. singlyLinked.print();                             // "Susan,Jack,Tom,Peter,Paul"
  13. console.log(singlyLinked.getHead());              // "Susan"
  14. console.log(singlyLinked.isEmpty());              // false
  15. console.log(singlyLinked.indexOf("Peter"));       // 3
  16. console.log(singlyLinked.indexOf("Cris"));        // -1
  17. singlyLinked.remove("Tom");                       
  18. singlyLinked.removeAt(2);                         
  19. singlyLinked.print();                             // "Susan,Jack,Paul"
2.2 双向链表

双向链表和普通链表的区别在于，在普通链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

创建双向链表类：

</>复制代码 
  1. // 创建双向链表DoublyLinkedList类
  2. function DoublyLinkedList () {
  3.   function Node (element) {
  4.     this.element = element;
  5.     this.next = null;
  6.     this.prev = null;        // 新增
  7.   }
  8.   var length = 0;
  9.   var head = null;
  10.   var tail = null;          // 新增
  11. }

可以看到，双向链表在Node类里有prev属性（一个新指针），在DoublyLinkedList类里也有用来保存对列表最后一项的引用的tail属性。

双向链表提供了两种迭代列表的方法：从头到尾，或者从尾到头。我们可以访问一个特定节点的下一个或前一个元素。

在单向链表中，如果迭代链表时错过了要找的元素，就需要回到链表起点，重新开始迭代。在双向链表中，可以从任一节点，向前或向后迭代，这是双向链表的一个优点。

实现双向链表的辅助方法：

</>复制代码 
  1.   // 向链表尾部添加一个新的项
  2.   this.append = function (element) {
  3.     var node = new Node(element);
  4.     var currentNode = tail;
  5.     // 判断是否为空链表
  6.     if (currentNode === null) {
  7.       // 空链表
  8.       head = node;
  9.       tail = node;
  10.     } else {
  11.       currentNode.next = node;
  12.       node.prev = currentNode;
  13.       tail = node; 
  14.     }
  15.     length++;
  16.   };
  17.   // 向链表特定位置插入一个新的项
  18.   this.insert = function (position, element) {
  19.     if (position < 0 && position > length) {
  20.       // 越界
  21.       return false;
  22.     } else {
  23.       var node = new Node(element);
  24.       var index = 0;
  25.       var currentNode = head;
  26.       var previousNode;
  27.       if (position === 0) {
  28.         if (!head) {
  29.           head = node;
  30.           tail = node;
  31.         } else {
  32.           node.next = currentNode;
  33.           currentNode.prev = node;
  34.           head = node;
  35.         }
  36.       } else if (position === length) {
  37.         this.append(element);
  38.       } else {
  39.         while (index < position) {
  40.           index++;
  41.           previousNode = currentNode;
  42.           currentNode = currentNode.next; 
  43.         }
  44.   
  45.         previousNode.next = node;
  46.         node.next = currentNode;
  47.         node.prev = previousNode;
  48.         currentNode.prev = node;
  49.       }
  50.       length++;
  51.       return true;
  52.     }
  53.   };
  54.   // 从链表的特定位置移除一项
  55.   this.removeAt = function (position) {
  56.     if (position < 0 && position >= length || length === 0) {
  57.       // 越界
  58.       return false;
  59.     } else {
  60.       var currentNode = head;
  61.       var index = 0;
  62.       var previousNode;
  63.       if (position === 0) {
  64.         // 移除第一项
  65.         if (length === 1) {
  66.           head = null;
  67.           tail = null;
  68.         } else {
  69.           head = currentNode.next;
  70.           head.prev = null;
  71.         }
  72.       } else if (position === length - 1) {
  73.         // 移除最后一项
  74.         if (length === 1) {
  75.           head = null;
  76.           tail = null;
  77.         } else {
  78.           currentNode = tail;
  79.           tail = currentNode.prev;
  80.           tail.next = null;
  81.         }
  82.       } else {
  83.         while (index < position) {
  84.           index++;
  85.           previousNode = currentNode;
  86.           currentNode = currentNode.next;
  87.         }
  88.         previousNode.next = currentNode.next;
  89.         previousNode = currentNode.next.prev;
  90.       }
  91.       length--;
  92.       return true;
  93.     }
  94.   };
  95.   // 从链表中移除指定项
  96.   this.remove = function (element) {
  97.     var index = this.indexOf(element);
  98.     return this.removeAt(index);
  99.   };
  100.   // 返回元素在链表的索引，如果链表中没有该元素则返回-1
  101.   this.indexOf = function (element) {
  102.     var currentNode = head;
  103.     var index = 0;
  104.     while (currentNode) {
  105.       if (currentNode.element === element) {
  106.         return index;
  107.       }
  108.       index++;
  109.       currentNode = currentNode.next;
  110.     }
  111.     return -1;
  112.   };
  113.   // 如果链表中不包含任何元素，返回true，如果链表长度大于0，返回false
  114.   this.isEmpty = function () {
  115.     return length == 0;
  116.   };
  117.   // 返回链表包含的元素个数，与数组的length属性类似
  118.   this.size = function () {
  119.     return length;
  120.   };
  121.   // 获取链表头部元素
  122.   this.getHead = function () {
  123.     return head.element;
  124.   };
  125.   // 由于链表使用了Node类，就需要重写继承自JavaScript对象默认的toString()方法，让其只输出元素的值
  126.   this.toString = function () {
  127.     var currentNode = head;
  128.     var string = "";
  129.     while (currentNode) {
  130.       
  131.       string += "," + currentNode.element;
  132.       currentNode = currentNode.next;
  133.     }
  134.     return string.slice(1);    
  135.   };
  136.   this.print = function () {
  137.     console.log(this.toString());
  138.   };

创建双向链表实例进行测试：

</>复制代码 
  1. // 创建双向链表
  2. var doublyLinked = new DoublyLinkedList();
  3. console.log(doublyLinked.isEmpty());              // true
  4. doublyLinked.append("Tom");                       
  5. doublyLinked.append("Peter");
  6. doublyLinked.append("Paul");
  7. doublyLinked.print();                             // "Tom,Peter,Paul"
  8. doublyLinked.insert(0, "Susan");                  
  9. doublyLinked.print();                             // "Susan,Tom,Peter,Paul"
  10. doublyLinked.insert(1, "Jack");                   
  11. doublyLinked.print();                             // "Susan,Jack,Tom,Peter,Paul"
  12. console.log(doublyLinked.getHead());              // "Susan"
  13. console.log(doublyLinked.isEmpty());              // false
  14. console.log(doublyLinked.indexOf("Peter"));       // 3
  15. console.log(doublyLinked.indexOf("Cris"));        // -1
  16. doublyLinked.remove("Tom");                       
  17. doublyLinked.removeAt(2);                         
  18. doublyLinked.print();                             // "Susan,Jack,Paul"
2.3 循环链表

循环链表可以像单向链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和普通链表之间唯一的区别在于，最后一个元素指向下一个元素的指针（next）不是引用null，而是指向第一个元素（head）。这里就不进行代码实现了，大家可以结合上面的单向链表和双向链表自己实现一个循环链表。

三、结束

本文会同步到我的个人博客，完整代码可以到我的github仓库查看，如果对你有帮助的话欢迎点一个Star~~

欢迎关注我的公众号

云服务器 GPU云服务器 链表数据结构队列 linux 数据结构 链表 java链表数据结构 C++数据结构链表

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

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

相关文章

  • 用 JavaScript 实现链表操作 - 04 Insert Nth Node

    摘要：给定一个链表，一个范围在内的索引号，和一个数据，这个函数会生成一个新的节点并插入到指定的索引位置，并始终返回链表的头。的返回值一定是个链表，我们把它赋值给就行。但这个例子的边界情况是返回值不同如果，返回新节点。 TL;DR 插入第 N 个节点。系列目录见 前言和目录 。 需求 实现一个 insertNth() 方法，在链表的第 N 个索引处插入一个新节点。 insertNth() 可以...

    894974231 评论0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

    摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。 一 目录 不折腾的前端，和咸鱼有什么区别...

    tain335 评论0 收藏0

  • 【Redis5源码学习】2019-04-17 压缩列表ziplist

    摘要：记录压缩列表总共占用的字节数，在对压缩列表进行内存重分配时使用个字节。为十六进制值，标记一个压缩列表的末尾具体的数据存放在中。占用或字节表示当前存储数据的类型与数据的长度。在学习的同时，如果没有经过自己的思考，收效甚微。 baiyan全部视频：https://segmentfault.com/a/11... 为什么需要ziplist 乍一看标题，我们可能还不知道ziplist是何许人也...

    church 评论0 收藏0

  • 集合框架知识系列04 LinkedList的源码分析和使用示例

    摘要：一简介内部是通过双向链表存储的，提供顺序访问。继承了，实现在迭代器上的随机访问。四总结本节分析了的源码的用法。实现了接口，内部通过链表实现，能够实现链表队列栈和双端队列等数据结构的功能。 一、LinkedList简介 LinkedList内部是通过双向链表存储的，提供顺序访问。继承了AbstractSequentialList，实现在迭代器上的随机访问。并且，还实现了List、Dequ...

    CntChen 评论0 收藏0

  • 【Redis5源码学习】2019-04-19 字典dict

    摘要：全部视频每日学习记录使用录像设备记录每天的学习字典是啥，即字典，也被称为哈希表。通常情况下，一个长这样在这个哈希表中，每个存储单元被称为一个桶。完成之后，新哈希表就会被置为，为线上提供服务。 baiyan 全部视频：【每日学习记录】使用录像设备记录每天的学习 字典是啥 dict，即字典，也被称为哈希表hashtable。在redis的五大数据结构中，有如下两种情形会使用dict结构： ...

    terasum 评论0 收藏0

发表评论

登陆后可评论

0条评论

cheukyin

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<