5. 链表
定义
- 链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的，它是通过 指针 将 零散的内存块 串连起来的。
- 每个元素由一个存储元素本身的 节点 和一个指向下一个元素的 引用（也称指针或链接）组成。
简单的链接结构图：
其中，data 中保存着数据，next 保存着下一个链表的引用。
上图中，我们说 data2 跟在 data1 后面，而不是说 data2 是链表中的第二个元素。值得注意的是，我们将链表的尾元素指向了 null 节点，表示链接结束的位置。
特点
- 链表是通过指针将零散的内存块串连起来的。
所以链表不支持 随机访问，如果要找特定的项，只能从头开始遍历，直到找到某个项。
所以访问的时间复杂度为 O(n)。
- 高效的插入和删除。
链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的，只需要考虑相邻结点的指针改变。
所以，在链表中插入和删除一个数据是非常快速的，时间复杂度为 O(1)。
三种最常见的链表结构，它们分别是：
- 单链表
- 双向链表
- 循环链表
单链表
定义
由于链表的起始点的确定比较麻烦，因此很多链表的实现都会在链表的最前面添加一个特殊的节点，称为 头节点，表示链表的头部。
经过改造，链表就成了如下的样子：
针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以插入与删除的时间复杂度为 O(1)。
在 d2 节点后面插入 d4 节点：
删除 d4 节点：
实现
- Node 类用来表示节点。
- LinkedList 类提供插入节点、删除节点等一些操作。
单向链表的八种常用操作：
- append(element)：尾部添加元素。
- insert(position, element)：特定位置插入一个新的项。
- removeAt(position)：特定位置移除一项。
- remove(element)：移除一项。
- indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回 -1。
- isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false。
- size()：返回链表包含的元素个数，与数组的 length 属性类似。
- getHead()：返回链表的第一个元素。
- toString()：由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值。
- print()：打印链表的所有元素。
具体代码：
// 单链表 function SinglyLinkedList() { // 节点 function Node(element) { this.element = element; // 当前节点的元素 this.next = null; // 下一个节点指针 } var length = 0; // 链表的长度 var head = null; // 链表的头部节点 // 向链表尾部添加一个新的节点 this.append = function(element) { var node = new Node(element); var currentNode = head; // 判断是否为空链表 if (head === null) { // 是空链表，就把当前节点作为头部节点 head = node; } else { // 从 head 开始一直找到最后一个 node while (currentNode.next) { // 后面还有 node currentNode = currentNode.next; } // 把当前节点的 next 指针 指向 新的节点 currentNode.next = node; } // 链表的长度加 1 length++; }; // 向链表特定位置插入一个新节点 this.insert = function(position, element) { if (position < 0 && position > length) { // 越界 return false; } else { var node = new Node(element); var index = 0; var currentNode = head; var previousNode; // 在最前插入节点 if (position === 0) { node.next = currentNode; head = node; } else { // 循环找到位置 while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } // 把前一个节点的指针指向新节点，新节点的指针指向当前节点，保持连接性 previousNode.next = node; node.next = currentNode; } length++; return true; } }; // 从链表的特定位置移除一项 this.removeAt = function(position) { if ((position < 0 && position >= length) || length === 0) { // 越界 return false; } else { var currentNode = head; var index = 0; var previousNode; if (position === 0) { head = currentNode.next; } else { // 循环找到位置 while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } // 把当前节点的 next 指针 指向 当前节点的 next 指针，即是 删除了当前节点 previousNode.next = currentNode.next; } length--; return true; } }; // 从链表中移除指定项 this.remove = function(element) { var index = this.indexOf(element); return this.removeAt(index); }; // 返回元素在链表的索引，如果链表中没有该元素则返回 -1 this.indexOf = function(element) { var currentNode = head; var index = 0; while (currentNode) { if (currentNode.element === element) { return index; } index++; currentNode = currentNode.next; } return -1; }; // 如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false this.isEmpty = function() { return length === 0; }; // 返回链表包含的元素个数，与数组的 length 属性类似 this.size = function() { return length; }; // 获取链表头部元素 this.getHead = function() { return head.element; }; // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值 this.toString = function() { var currentNode = head; var string = ''; while (currentNode) { string += ',' + currentNode.element; currentNode = currentNode.next; } return string.slice(1); }; // 打印链表数据 this.print = function() { console.log(this.toString()); }; // 获取整个链表 this.list = function() { console.log('head: ', head); return head; }; }
测试：
// 创建单向链表实例 var singlyLinked = new SinglyLinkedList(); console.log(singlyLinked.removeAt(0)); // false console.log(singlyLinked.isEmpty()); // true singlyLinked.append('Tom'); singlyLinked.append('Peter'); singlyLinked.append('Paul'); singlyLinked.print(); // "Tom,Peter,Paul" singlyLinked.insert(0, 'Susan'); singlyLinked.print(); // "Susan,Tom,Peter,Paul" singlyLinked.insert(1, 'Jack'); singlyLinked.print(); // "Susan,Jack,Tom,Peter,Paul" console.log(singlyLinked.getHead()); // "Susan" console.log(singlyLinked.isEmpty()); // false console.log(singlyLinked.indexOf('Peter')); // 3 console.log(singlyLinked.indexOf('Cris')); // -1 singlyLinked.remove('Tom'); singlyLinked.removeAt(2); singlyLinked.print(); // "Susan,Jack,Paul" singlyLinked.list(); // 具体控制台
整个链表数据在 JavaScript 里是怎样的呢 ？
为了看这个数据，特意写了个 list 函数：
// 获取整个链表 this.list = function() { console.log('head: ', head); return head; };
重点上上面的最后一行代码： singlyLinked.list() ，打印的数据如下：
所以，在 JavaScript 中，单链表的真实数据有点类似于对象，实际上是 Node 类生成的实例。
双向链表
单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。
而双向链表，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
单向链表与又向链表比较
- 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。
所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
- 双向链表提供了两种迭代列表的方法：从头到尾，或者从尾到头。
我们可以访问一个特定节点的下一个或前一个元素。
- 在单向链表中，如果迭代链表时错过了要找的元素，就需要回到链表起点，重新开始迭代。
- 在双向链表中，可以从任一节点，向前或向后迭代，这是双向链表的一个优点。
- 所以，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
实现
具体代码：
// 创建双向链表 DoublyLinkedList 类 function DoublyLinkedList() { function Node(element) { this.element = element; //当前节点的元素 this.next = null; //下一个节点指针 this.previous = null; //上一个节点指针 } var length = 0; // 链表长度 var head = null; // 链表头部 var tail = null; // 链表尾部 // 向链表尾部添加一个新的项 this.append = function(element) { var node = new Node(element); var currentNode = tail; // 判断是否为空链表 if (currentNode === null) { // 空链表 head = node; tail = node; } else { currentNode.next = node; node.prev = currentNode; tail = node; } length++; }; // 向链表特定位置插入一个新的项 this.insert = function(position, element) { if (position < 0 && position > length) { // 越界 return false; } else { var node = new Node(element); var index = 0; var currentNode = head; var previousNode; if (position === 0) { if (!head) { head = node; tail = node; } else { node.next = currentNode; currentNode.prev = node; head = node; } } else if (position === length) { this.append(element); } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = node; node.next = currentNode; node.prev = previousNode; currentNode.prev = node; } length++; return true; } }; // 从链表的特定位置移除一项 this.removeAt = function(position) { if ((position < 0 && position >= length) || length === 0) { // 越界 return false; } else { var currentNode = head; var index = 0; var previousNode; if (position === 0) { // 移除第一项 if (length === 1) { head = null; tail = null; } else { head = currentNode.next; head.prev = null; } } else if (position === length - 1) { // 移除最后一项 if (length === 1) { head = null; tail = null; } else { currentNode = tail; tail = currentNode.prev; tail.next = null; } } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; previousNode = currentNode.next.prev; } length--; return true; } }; // 从链表中移除指定项 this.remove = function(element) { var index = this.indexOf(element); return this.removeAt(index); }; // 返回元素在链表的索引，如果链表中没有该元素则返回 -1 this.indexOf = function(element) { var currentNode = head; var index = 0; while (currentNode) { if (currentNode.element === element) { return index; } index++; currentNode = currentNode.next; } return -1; }; // 如果链表中不包含任何元素，返回 true ，如果链表长度大于 0 ，返回 false this.isEmpty = function() { return length == 0; }; // 返回链表包含的元素个数，与数组的 length 属性类似 this.size = function() { return length; }; // 获取链表头部元素 this.getHead = function() { return head.element; }; // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值 this.toString = function() { var currentNode = head; var string = ''; while (currentNode) { string += ',' + currentNode.element; currentNode = currentNode.next; } return string.slice(1); }; this.print = function() { console.log(this.toString()); }; // 获取整个链表 this.list = function() { console.log('head: ', head); return head; }; }
测试：
// 创建双向链表 var doublyLinked = new DoublyLinkedList(); console.log(doublyLinked.isEmpty()); // true doublyLinked.append('Tom'); doublyLinked.append('Peter'); doublyLinked.append('Paul'); doublyLinked.print(); // "Tom,Peter,Paul" doublyLinked.insert(0, 'Susan'); doublyLinked.print(); // "Susan,Tom,Peter,Paul" doublyLinked.insert(1, 'Jack'); doublyLinked.print(); // "Susan,Jack,Tom,Peter,Paul" console.log(doublyLinked.getHead()); // "Susan" console.log(doublyLinked.isEmpty()); // false console.log(doublyLinked.indexOf('Peter')); // 3 console.log(doublyLinked.indexOf('Cris')); // -1 doublyLinked.remove('Tom'); doublyLinked.removeAt(2); doublyLinked.print(); // "Susan,Jack,Paul" doublyLinked.list(); // 请看控制台输出
整个链表数据在 JavaScript 里是怎样的呢 ？
// 获取整个链表 this.list = function() { console.log('head: ', head); return head; };
调用 doublyLinked.list(); .
控制台输出如下：
链表代码实现的关键是弄清楚：前节点与后节点与边界。
循环链表
循环链表是一种特殊的单链表。
循环链表和单链表相似，节点类型都是一样。
唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性指向它本身。
即：
head.next = head;
这种行为会导致链表中每个节点的 next 属性都指向链表的头节点，换句话说，也就是链表的尾节点指向了头节点，形成了一个循环链表。如下图所示：
循环链表：在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。
代码：
// 循环链表 function CircularLinkedList() { // 节点 function Node(element) { this.element = element; // 当前节点的元素 this.next = null; // 下一个节点指针 } var length = 0, head = null; this.append = function(element) { var node = new Node(element), current; if (!head) { head = node; // 头的指针指向自己 node.next = head; } else { current = head; while (current.next !== head) { current = current.next; } current.next = node; // 最后一个节点指向头节点 node.next = head; } length++; return true; }; this.insert = function(position, element) { if (position > -1 && position < length) { var node = new Node(element), index = 0, current = head, previous; if (position === 0) { // 头节点指向自己 node.next = head; head = node; } else { while (index++ < position) { previous = current; current = current.next; } previous.next = node; node.next = current; } length++; return true; } else { return false; } }; this.removeAt = function(position) { if (position > -1 && position < length) { var current = head, previous, index = 0; if (position === 0) { head = current.next; } else { while (index++ < position) { previous = current; current = current.next; } previous.next = current.next; } length--; return current.element; } else { return false; } }; this.remove = function(element) { var current = head, previous, indexCheck = 0; while (current && indexCheck < length) { if (current.element === element) { if (indexCheck == 0) { head = current.next; length--; return true; } else { previous.next = current.next; length--; return true; } } else { previous = current; current = current.next; indexCheck++; } } return false; }; this.remove = function() { if (length === 0) { return false; } var current = head, previous, indexCheck = 0; if (length === 1) { head = null; length--; return current.element; } while (indexCheck++ < length) { previous = current; current = current.next; } previous.next = head; length--; return current.element; }; this.indexOf = function(element) { var current = head, index = 0; while (current && index < length) { if (current.element === element) { return index; } else { index++; current = current.next; } } return -1; }; this.isEmpty = function() { return length === 0; }; this.size = function() { return length; }; // 由于链表使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值 this.toString = function() { var current = head, string = '', indexCheck = 0; while (current && indexCheck < length) { string += ',' + current.element; current = current.next; indexCheck++; } return string.slice(1); }; // 获取链表头部元素 this.getHead = function() { return head.element; }; // 打印链表数据 this.print = function() { console.log(this.toString()); }; // 获取整个链表 this.list = function() { console.log('head: ', head); return head; }; }
测试：
// 创建单向链表实例 var circularLinked = new CircularLinkedList(); console.log(circularLinked.removeAt(0)); // false console.log(circularLinked.isEmpty()); // true circularLinked.append('Tom'); circularLinked.append('Peter'); circularLinked.append('Paul'); circularLinked.print(); // "Tom,Peter,Paul" circularLinked.insert(0, 'Susan'); circularLinked.print(); // "Susan,Tom,Peter,Paul" circularLinked.insert(1, 'Jack'); circularLinked.print(); // "Susan,Jack,Tom,Peter,Paul" console.log(circularLinked.getHead()); // "Susan" console.log(circularLinked.isEmpty()); // false console.log(circularLinked.indexOf('Peter')); // 3 console.log(circularLinked.indexOf('Cris')); // -1 circularLinked.remove('Tom'); circularLinked.removeAt(2); circularLinked.print(); // "Susan,Jack,Paul" circularLinked.list(); // 具体控制台
整个链表数据在 JavaScript 里是怎样的呢 ？
// 获取整个链表 this.list = function() { console.log('head: ', head); return head; };
调用 circularLinked.list() 。
控制台输出如下：
你知道大家发现没有，为什么从 1 - 4 - 1 了，还有 next 节点，而且是还可以一直点 next ，重复的展开下去，这正是 循环 的原因。
链表总结
- 写链表代码是最考验逻辑思维能力的，要熟练链表，只有 多写多练，没有捷径。
- 因为，链表代码到处都是指针的操作、边界条件的处理，稍有不慎就容易产生 Bug。
- 链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。
- 所以，这也是很多面试官喜欢让人手写链表代码的原因。
- 一定要自己写代码实现一下，才有效果。
