单向链表简介 链表和数组一样,可以用于存储一系列的元素 ,但是链表和数组的实现机制完全不同 。链表的每个元素由一个存储元素本身的节点 和一个指向下一个元素的引用 (有的语言称为指针或连接)组成。类似于火车头,一节车厢载着乘客(数据),通过节点连接另一节车厢。
head 属性指向链表的第一个节点;
链表中的最后一个节点指向 null;
当链表中一个节点也没有的时候,head 直接指向 null;
数组存在的缺点
数组的创建通常需要申请一段连续的内存空间 (一整块内存),并且大小是固定的。所以当原数组不能满足容量需求 时,需要扩容 (一般情况下是申请一个更大的数组,比如 2 倍,然后将原数组中的元素复制过去)。
在数组的开头或中间位置插入数据的成本很高,需要进行大量元素的位移。
链表的优势
链表中的元素在内存中不必是连续的空间 ,可以充分利用计算机的内存,实现灵活的内存动态管理 。
链表不必在创建时就确定大小 ,并且大小可以无限地延伸 下去。
链表在插入和删除 数据时,时间复杂度 可以达到 O(1),相对数组效率高很多。
链表的缺点:
链表访问任何一个位置的元素时,都需要从头开始访问 (无法跳过第一个元素访问任何一个元素)。
无法通过下标值直接访问元素,需要从头开始一个个访问,直到找到对应的元素。
虽然可以轻松地到达下一个节点 ,但是回到前一个节点 是很难的。
链表中的常见操作
append(element):向链表尾部添加一个新的项;
insert(position,element):向链表的特定位置插入一个新的项;
get(position):获取对应位置的元素;
indexOf(element):返回元素在链表中的索引。如果链表中没有该元素就返回-1;
update(position,element):修改某个位置的元素;
removeAt(position):从链表的特定位置移除一项;
remove(element):从链表中移除一项;
isEmpty():如果链表中不包含任何元素,返回 trun,如果链表长度大于 0 则返回 false;
size():返回链表包含的元素个数,与数组的 length 属性类似;
toString():由于链表项使用了 Node 类,就需要重写继承自 JavaScript 对象默认的 toString 方法,让其只输出元素的值;
首先需要弄清楚:下文中的 position 指的是两个节点之间,并且与 index 的关系如下图所示:
position 的值一般表示 position 所指位置的下一个节点。当 position 的值与 index 的值相等时,比如 position = index = 1,那么它们都表示 Node2。
封装单向链表类 创建单向链表类 先创建单向链表类 Linklist,并添加基本属性,再实现单向链表的常用方法:
代码解析:
封装 LinkedList 的类, 用于表示我们的链表结构. (和 Java 中的链表同名, 不同 Java 中的这个类是一个双向链表, 后面我们会讲解双向链表)
在 LinkedList 类中有一个 Node 类, 用于封装每一个节点上的信息.(和优先级队列的封装一样)
链表中我们保存两个属性, 一个是链表的长度, 一个是链表中第一个节点.
append(element) 向链表尾部追加数据可能有两种情况:
链表本身为空, 新添加的数据时唯一的节点.
链表不为空, 需要向其他节点后面追加节点.
代码实现:
过程详解:
首先需要做的是将 element 传入方法, 并根据 element 创建一个 Node 节点.
场景一: 链表本身是空的,我们只需要让 head 指向新建的 node 节点即可
场景二: 链表中已经有元素了, 需要向最后的节点的 next 中添加节点.首先让 current 指向第一个节点:
通过 while 循环使 current 指向最后一个节点,最后通过 current.next = newNode,让最后一个节点指向新节点 newNode:
测试代码:
1 2 3 4 5 6 7 8 9 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) console .log (list)
测试结果:
toString() 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 LinkList .prototype .toString = () => { let current = this .head let listString = '' while (current) { listString += current.data + ' ' current = current.next } return listString }
方法解读:
该方法比较简单, 主要是获取每一个元素
还是从 head 开头, 因为获取链表的任何元素都必须从第一个节点开头.
循环遍历每一个节点, 并且取出其中的 element, 拼接成字符串.
将最终字符串返回.
测试代码:
1 2 3 4 5 6 7 8 9 10 11 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) console .log (list.toString ())
测试结果:
insert(position,element) 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 LinkList .prototype .insert = (position, data ) => { if (position < 0 || position > this .length ) { return false } let newNode = new Node (data) if (position == 0 ) { newNode.next = this .head this .head = newNode } else { let index = 0 let previous = null let current = this .head while (index++ < position) { previous = current current = current.next } newNode.next = current previous.next = newNode } this .length += 1 return true }
过程详解:
inset 方法实现的过程:根据插入节点位置的不同可分为多种情况:
通过: newNode.next = this.head,建立连接 1;
通过: this.head = newNode,建立连接 2;(不能先建立连接 2,否则 this.head 不再指向 Node1)
首先定义两个变量 previous 和 curent 分别指向需要插入位置 pos = X 的前一个节点和后一个节点;
然后,通过:newNode.next = current,改变指向 3;
最后,通过:previous.next = newNode,改变指向 4;
情况 2 的特殊情形:position = length :
情况 2 也包含了 pos = length 的情况,该情况下 current 和 newNode.next 都指向 null;建立连接 3 和连接 4 的方式与情况 2 相同。
添加到其他位置:
如果是添加到其他位置, 就需要先找到这个节点位置了.
我们通过 while 循环, 一点点向下找. 并且在这个过程中保存上一个节点和下一个节点.
找到正确的位置后, 将新节点的 next 指向下一个节点, 将上一个节点的 next 指向新的节点.
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) list.insert (0 , '在链表最前面插入节点' ) list.insert (2 , '在链表中第二个节点后插入节点' ) list.insert (5 , '在链表最后插入节点' ) alert (list)console .log (list)
get(position) 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 LinkList .prototype .get = (position ) => { if (position < 0 || position >= this .length ) { return null } let current = this .head let index = 0 while (index++ < position) { current = current.next } return current.data }
过程详解:
get 方法的实现过程:以获取 position = 2 为例,如下图所示:
首先使 current 指向第一个节点,此时 index=0;
通过 while 循环使 current 循环指向下一个节点,注意循环终止的条件 index++ < position,即当 index=position 时停止循环,此时循环了 1 次,current 指向第二个节点(Node2),最后通过 current.data 返回 Node2 节点的数据;
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) console .log (list.get (0 ))console .log (list.get (1 ))
测试结果:
indexOf(element) 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LinkList .prototype .indexOf = (data ) => { let current = this .head let index = 0 while (current) { if (current.data == data) { return index } current = current.next index += 1 } return -1 }
代码解析:
代码 1 的位置还是定义需要的变量.
代码 2 的位置, 通过 while 循环获取节点
通过节点获取元素和 element 进行对比, 如果和传入 element 相同, 表示找到, 直接返回 index 即可.
如果没有找到, index++, 并且指向下一个节点.
到最后都没有找到, 说明链表中没有对应的元素, 那么返回-1 即可.
过程详解:
indexOf 方法的实现过程:
使用变量 current 记录当前指向的节点,使用变量 index 记录当前节点的索引值(注意 index = node 数-1)
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) console .log (list.indexOf ('aaa' ))console .log (list.indexOf ('ccc' ))
测试结果:
update(position,element) 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LinkList .prototype .update = (position, newData ) => { if (position < 0 || position >= this .length ) { return false } let current = this .head let index = 0 while (index++ < position) { current = current.next } current.data = newData return true }
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) list.update (0 , '修改第一个节点' ) list.update (1 , '修改第二个节点' ) console .log (list)console .log (list.update (3 , '能修改么' ))
测试结果:
removeAt(position) 代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 LinkList .prototype .removeAt = (position ) => { if (position < 0 || position >= this .length ) { return null } let current = this .head if (position == 0 ) { this .head = this .head .next } else { let index = 0 let previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next } this .length -= 1 return current.data }
过程详解:
removeAt 方法的实现过程:删除节点时存在多种情况:
情况 1:position = 0 ,即移除第一个节点(Node1)。
通过:this.head = this.head.next,改变指向 1 即可;
虽然 Node1 的 next 仍指向 Node2,但是没有引用指向 Node1,则 Node1 会被垃圾回收器自动回收,所以不用处理 Node1 指向 Node2 的引用 next。
情况 2:positon > 0 ,比如 pos = 2 即移除第三个节点(Node3)。
注意: position = length 时 position 后一个节点为 null 不能删除,因此 position != length;
首先,定义两个变量 previous 和 curent 分别指向需要删除位置 pos = x 的前一个节点和后一个节点;
然后,通过:previous.next = current.next,改变指向 1 即可;
随后,没有引用指向 Node3,Node3 就会被自动回收,至此成功删除 Node3 。
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) console .log (list.removeAt (0 ))console .log (list.removeAt (0 ))console .log (list)
测试结果:
其他方法 其他方法包括:remove(element)、isEmpty()、size()
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LinkList .prototype .remove = (data ) => { let position = this .indexOf (data) return this .removeAt (position) } LinkList .prototype .isEmpty = () => { return this .length == 0 } LinkList .prototype .size = () => { return this .length }
测试代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 let list = new LinkList ()list.append ('aaa' ) list.append ('bbb' ) list.append ('ccc' ) console .log (list.remove ('aaa' ))console .log (list)console .log (list.isEmpty ())console .log (list.size ())
测试结果:
完整实现 使用 ES5 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 function LinkList ( ) { function Node (data ) { this .data = data this .next = null } this .head = null this .length = 0 LinkList .prototype .append = (data ) => { let newNode = new Node (data) if (this .length == 0 ) { this .head = newNode } else { let current = this .head while (current.next ) { current = current.next } current.next = newNode } this .length += 1 } LinkList .prototype .toString = () => { let current = this .head let listString = '' while (current) { listString += current.data + ' ' current = current.next } return listString } LinkList .prototype .insert = (position, data ) => { if (position < 0 || position > this .length ) { return false } let newNode = new Node (data) if (position == 0 ) { newNode.next = this .head this .head = newNode } else { let index = 0 let previous = null let current = this .head while (index++ < position) { previous = current current = current.next } newNode.next = current previous.next = newNode } this .length += 1 return true } LinkList .prototype .get = (position ) => { if (position < 0 || position >= this .length ) { return null } let current = this .head let index = 0 while (index++ < position) { current = current.next } return current.data } LinkList .prototype .indexOf = (data ) => { let current = this .head let index = 0 while (current) { if (current.data == data) { return index } current = current.next index += 1 } return -1 } LinkList .prototype .update = (position, newData ) => { if (position < 0 || position >= this .length ) { return false } let current = this .head let index = 0 while (index++ < position) { current = current.next } current.data = newData return true } LinkList .prototype .removeAt = (position ) => { if (position < 0 || position >= this .length ) { return null } let current = this .head if (position == 0 ) { this .head = this .head .next } else { let index = 0 let previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next } this .length -= 1 return current.data } LinkList .prototype .remove = (data ) => { let position = this .indexOf (data) return this .removeAt (position) } LinkList .prototype .isEmpty = () => { return this .length == 0 } LinkList .prototype .size = () => { return this .length } }
使用 ES6 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 export class Node { constructor (element ) { this .element = element this .next = null } } export class LinkedList { constructor ( ) { this .head = null this .length = 0 } append (element ) { const newNode = new Node (element) if (!this .head ) { this .head = newNode } else { let current = this .head while (current.next ) { current = current.next } current.next = newNode } this .length ++ } insert (position, element ) { if (position < 0 || position > this .length - 1 ) return false const newNode = new Node (element) if (position === 0 ) { newNode.next = this .head this .head = newNode } else { let index = 0 let current = this .head let previous = null while (index++ < position) { previous = current current = current.next } previous.next = newNode newNode.next = current } this .length ++ return true } get (position ) { if (position < 0 || position > this .length - 1 ) return null let index = 0 let current = this .head while (index++ < position) { current = current.next } return current.element } indexOf (element ) { let current = this .head let index = 0 while (current) { if (current.element === element) { return index } index++ current = current.next } return -1 } removeAt (position ) { if (position < 0 || position > this .length - 1 ) return null let current = this .head if (position === 0 ) { this .head = current.next } else { let index = 0 let previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next } this .length -- return current.element } update (position, element ) { const result = this .removeAt (position) this .insert (position, element) return result } remove ( ) { const index = this .indexOf (element) if (index === -1 ) return this .removeAt (index) } isEmpty ( ) { return this .length === 0 } size ( ) { return this .length } }