要存储多个元素，数组（或列表）可能是最常用的数据结构。但这种数据结构有一个缺点：（在大多数语言中）数据的大小是固定的，从数组的起点或中间插入或移除项的成本很高。 链表存储有序的集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。 相对于传统的数组，链表的一个好处是，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，需要从起点（表头）开始迭代列表直到找到所需的元素。 举个例子，我们玩寻宝游戏，你有一条线索，这条线索是指向寻找下一条线索的地点的指针。你沿着这条链接去下一个地点，得到另一条指向再下一处的线索。得到列表中间的线索的唯一办法，就是从起点（第一条线索）顺着列表去寻找。 让我们用JS实现最简单的单链表:
1function LinkedList() { 2 3 // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针 4 let Node = function (element) { 5 this.element = element 6 this.next = null 7 } 8 9 let length = 0 10 let head = null 11 12 // 向链表尾部追加元素 13 this.append = function (element) { 14 let node = new Node(element) 15 let current 16 if (head === null) { // 列表中第一个节点 17 head = node 18 } else { 19 current = head 20 while (current.next) { 21 current = current.next // 找到最后一项，是null 22 } 23 current.next = node // 给最后一项赋值 24 } 25 length++ // 更新列表的长度 26 } 27 28 // 从链表中移除指定位置元素 29 this.removeAt = function (position) { 30 if (position > -1 && position < length) { // 值没有越界 31 let current = head 32 let previous, index = 0 33 if (position === 0) { // 移除第一项 34 head = current.next 35 } else { 36 while (index++ < position) { 37 previous = current 38 current = current.next 39 } 40 previous.next = current.next // 将previous与current的下一项连接起来，跳过current，从而移除 41 } 42 length-- // 更新列表的长度 43 return current.element 44 } else { 45 return null 46 } 47 } 48 49 // 在链表任意位置插入一个元素 50 this.insert = function (position, element) { 51 if (position >= 0 && position <= length) { // 检查越界值 52 let node = new Node(element), 53 current = head, 54 previous, 55 index = 0 56 if (position === 0) { // 在第一个位置添加 57 node.next = current 58 head = node 59 } else { 60 while (index++ < position) { 61 previous = current 62 current = current.next 63 } 64 node.next = current // 在previous与current的下一项之间插入node 65 previous.next = node 66 } 67 length++ 68 return true 69 } else { 70 return false 71 } 72 } 73 74 // 把链表内的值转换成一个字符串 75 this.toString = function () { 76 let current = head, 77 string = '' 78 while (current) { 79 string += current.element + ' ' 80 current = current.next 81 } 82 return string 83 } 84 85 // 在链表中查找元素并返回索引值 86 this.indexOf = function (element) { 87 let current = head, 88 index = 0 89 while (current) { 90 if (element === current.element) { 91 return index 92 } 93 index++ 94 current = current.next 95 } 96 return -1 97 } 98 99 // 从链表中移除指定元素 100 this.remove = function (element) { 101 let index = this.indexOf(element) 102 return this.removeAt(index) 103 } 104 105 this.isEmpty = function () { 106 return length === 0 107 } 108 109 this.size = function () { 110 return length 111 } 112 113 this.getHead = function () { 114 return head 115 } 116} 117let list = new LinkedList() 118list.append(1) 119list.append(2) 120console.log(list.toString()) // 1 2 121list.insert(0, 'hello') 122list.insert(1, 'world') 123console.log(list.toString()) // hello world 1 2 124list.remove(1) 125list.remove(2) 126console.log(list.toString()) // hello world
单链表有一个变种 - 循环链表，最后一个元素指向下一个元素的指针，不是引用null，而是指向第一个元素，只需要修改下最后的next指向为head即可。