1 // 链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 2 // 元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展 3 // 示了一个链表的结构： 4
5 6 // 相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然 7 // 而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何 8 // 位置的任何元素，而要想访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到 9 // 所需的元素。 10 11 // 链表应用场景 火车车厢、寻宝游戏
TypeScript方式实现源码
1 class Node { 2 element; 3 next; 4 constructor(element) { 5 this.element = element; 6 this.next = null; 7 } 8 } 9 class LinkedList { 10 private length = 0; 11 head = null; 12 13 constructor() { 14 } 15 /** 16 * 向列表尾部添加一个新的项 17 * @param element 18 */ 19 public append(element) { 20 let node = new Node(element), current; 21 22 if (this.head === null) { 23 this.head = node; 24 } else { 25 current = this.head; 26 27 // 循环列表，知道找到最后一项 28 while (current.next) { 29 current = current.next; 30 } 31 32 // 找到最后一项，将其next赋为node，建立链接 33 current.next = node; 34 } 35 this.length++; // 更新列表长度 36 } 37 /** 38 * 向列表的特定位置插入一个新的项 39 * @param position 40 * @param element 41 */ 42 public insert(position, element) { 43 // 检查越界值 44 if (position >= 0 && position <= length) { 45 let node = new Node(element), 46 current = this.head, 47 previous, 48 index = 0; 49 50 if (position === 0) { // 在第一个位置添加 51 node.next = current; 52 this.head = node; 53 } else { 54 while (index++ < position) { 55 previous = current; 56 current = current.next; 57 } 58 node.next = current; 59 previous.next = node; 60 } 61 this.length++; // 更新列表长度 62 return true; 63 } else { 64 return false; 65 } 66 } 67 /** 68 * 从列表的特定位置移除一项 69 * @param position 70 */ 71 public removeAt(position) { 72 // 检查越界值 73 if (position > -1 && position < this.length) { 74 let current = this.head, 75 previous, 76 index = 0; 77 78 // 移除第一项 79 if (position === 0) { 80 this.head = current.next; 81 } else { 82 while (index++ < position) { 83 previous = current; 84 current = current.next; 85 } 86 // 将previous与current的下一项链接起来：跳过current，从而移除它 87 previous.next = current.next; 88 } 89 this.length--; 90 return current.element; 91 } else { 92 return null; 93 } 94 } 95 /** 96 * 从列表中移除一项 97 * @param element 98 */ 99 public remove(element) { 100 let index = this.indexOf(element); 101 return this.removeAt(index); 102 } 103 /** 104 * ：返回元素在列表中的索引。如果列表中没有该元素则返回-1 105 * @param element 106 */ 107 public indexOf(element) { 108 let current = this.head, 109 index = -1; 110 111 while (current) { 112 if (element === current.element) { 113 return index; 114 } 115 index++; 116 current = current.next; 117 } 118 return -1; 119 } 120 /** 121 * 如果链表中不包含任何元素， 返回true， 如果链表长度大于0则返回false 122 */ 123 public isEmpty() { 124 return this.length === 0; 125 } 126 /** 127 * 返回链表包含的元素个数。与数组的length属性类似 128 */ 129 public size() { 130 return this.length; 131 } 132 /** 133 * 由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值 134 */ 135 public toString() { 136 let current = this.head, 137 string = ''; 138 139 while (current) { 140 string += current.element; 141 current = current.next; 142 } 143 return string; 144 } 145 public getHead() { 146 return this.head; 147 } 148 public print() { 149 console.log(this.toString()); 150 } 151 }
// 代码解读： // 充分利用引用对象特性,将需要管理的数据加入链表的数据结构中, // 完全不依赖系统数组的数据结构,所以避免大量删、增数据数组排序的性能损耗。同时也失去了数组下标取数据的优势。 // 因此优势劣势非常明显,大量改删数据场景选用链表,大量已知下标去更新数据选用数组 // 抽象： // 火车车厢可长可短,随时加入或去掉一节车厢仅仅对操作车厢前后一节有改动,当车厢非常长的时候,这个优势尤为明显, // 这仅仅是一种应用场景也可以通过火车的例子去理解这种数据结构的设计理念 // 总结： // 链表以引用作为媒介,将大量不相干的数据进行一个有序的链接,同时没有复杂的关联关系,仅仅关系操作数据前后关联数据 // 面对大量增加删除的场景,链表将是比数组更好的选择
JavaScript方式实现源码
1 var Node = (function () { 2 function Node(element) { 3 this.element = element; 4 this.next = null; 5 } 6 return Node; 7 }()); 8 var LinkedList = (function () { 9 function LinkedList() { 10 this.length = 0; 11 this.head = null; 12 } 13 /** 14 * 向列表尾部添加一个新的项 15 * @param element 16 */ 17 LinkedList.prototype.append = function (element) { 18 var node = new Node(element), current; 19 if (this.head === null) { 20 this.head = node; 21 } 22 else { 23 current = this.head; 24 // 循环列表，知道找到最后一项 25 while (current.next) { 26 current = current.next; 27 } 28 // 找到最后一项，将其next赋为node，建立链接 29 current.next = node; 30 } 31 this.length++; // 更新列表长度 32 }; 33 /** 34 * 向列表的特定位置插入一个新的项 35 * @param position 36 * @param element 37 */ 38 LinkedList.prototype.insert = function (position, element) { 39 // 检查越界值 40 if (position >= 0 && position <= length) { 41 var node = new Node(element), current = this.head, previous = void 0, index = 0; 42 if (position === 0) { 43 node.next = current; 44 this.head = node; 45 } 46 else { 47 while (index++ < position) { 48 previous = current; 49 current = current.next; 50 } 51 node.next = current; 52 previous.next = node; 53 } 54 this.length++; // 更新列表长度 55 return true; 56 } 57 else { 58 return false; 59 } 60 }; 61 /** 62 * 从列表的特定位置移除一项 63 * @param position 64 */ 65 LinkedList.prototype.removeAt = function (position) { 66 // 检查越界值 67 if (position > -1 && position < this.length) { 68 var current = this.head, previous = void 0, index = 0; 69 // 移除第一项 70 if (position === 0) { 71 this.head = current.next; 72 } 73 else { 74 while (index++ < position) { 75 previous = current; 76 current = current.next; 77 } 78 // 将previous与current的下一项链接起来：跳过current，从而移除它 79 previous.next = current.next; 80 } 81 this.length--; 82 return current.element; 83 } 84 else { 85 return null; 86 } 87 }; 88 /** 89 * 从列表中移除一项 90 * @param element 91 */ 92 LinkedList.prototype.remove = function (element) { 93 var index = this.indexOf(element); 94 return this.removeAt(index); 95 }; 96 /** 97 * ：返回元素在列表中的索引。如果列表中没有该元素则返回-1 98 * @param element 99 */ 100 LinkedList.prototype.indexOf = function (element) { 101 var current = this.head, index = -1; 102 while (current) { 103 if (element === current.element) { 104 return index; 105 } 106 index++; 107 current = current.next; 108 } 109 return -1; 110 }; 111 /** 112 * 如果链表中不包含任何元素， 返回true， 如果链表长度大于0则返回false 113 */ 114 LinkedList.prototype.isEmpty = function () { 115 return this.length === 0; 116 }; 117 /** 118 * 返回链表包含的元素个数。与数组的length属性类似 119 */ 120 LinkedList.prototype.size = function () { 121 return this.length; 122 }; 123 /** 124 * 由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值 125 */ 126 LinkedList.prototype.toString = function () { 127 var current = this.head, string = ''; 128 while (current) { 129 string += current.element; 130 current = current.next; 131 } 132 return string; 133 }; 134 LinkedList.prototype.getHead = function () { 135 return this.head; 136 }; 137 LinkedList.prototype.print = function () { 138 console.log(this.toString()); 139 }; 140 return LinkedList; 141 }());