JS实现单向链表、双向链表、循环链表

怼烎@ 2021-12-23 16:49 503阅读 0赞

[https://cloud.tencent.com/developer/article/1114246][https_cloud.tencent.com_developer_article_1114246]

[链表][Link 1]存储有序的元素的集合，但是和数组不同的是，链表中的元素在内存中的存储并不是连续的。每一个链表元素都包含了**一个存储元素本身的节点**和**一个指向下一个元素的引用。**看起来就像这样：

![1620][]

相对于传统的数组，链表的一个好处就是增删的时候无需移动其它元素，只要更改指针的指向就可以了。但是缺点就是如果想要访问链表中的元素，需要从头开始循环迭代到你想要的元素。

function LinkedList() { // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针 let Node = function (element) { this.element = element this.next = null } let length = 0 let head = null // 向链表尾部追加元素 this.append = function (element) { let node = new Node(element) let current if (head === null) { // 列表中第一个节点 head = node } else { current = head while (current.next) { current = current.next // 找到最后一项，是null } current.next = node // 给最后一项赋值 } length++ // 更新列表的长度 } // 从链表中移除指定位置元素 this.removeAt = function (position) { if (position > -1 && position < length) { // 值没有越界 let current = head let previous, index = 0 if (position === 0) { // 移除第一项 head = current.next } else { while (index++ < position) { previous = current current = current.next } previous.next = current.next // 将previous与current的下一项连接起来，跳过current，从而移除 } length-- // 更新列表的长度 return current.element } else { return null } } // 在链表任意位置插入一个元素 this.insert = function (position, element) { if (position >= 0 && position <= length) { // 检查越界值 let node = new Node(element), current = head, previous, index = 0 if (position === 0) { // 在第一个位置添加 node.next = current head = node } else { while (index++ < position) { previous = current current = current.next } node.next = current // 在previous与current的下一项之间插入node previous.next = node } length++ return true } else { return false } } // 把链表内的值转换成一个字符串 this.toString = function () { let current = head, string = '' while (current) { string += current.element + ' ' current = current.next } return string } // 在链表中查找元素并返回索引值 this.indexOf = function (element) { let current = head, index = 0 while (current) { if (element === current.element) { return index } index++ current = current.next } return -1 } // 从链表中移除指定元素 this.remove = function (element) { let index = this.indexOf(element) return this.removeAt(index) } this.isEmpty = function () { return length === 0 } this.size = function () { return length } this.getHead = function () { return head } } let list = new LinkedList() list.append(1) list.append(2) console.log(list.toString()) // 1 2 list.insert(0, 'hello') list.insert(1, 'world') console.log(list.toString()) // hello world 1 2 list.remove(1) list.remove(2) console.log(list.toString()) // hello world

单链表有一个变种 - 循环链表，最后一个元素指向下一个元素的指针，不是引用null，而是指向第一个元素，只需要修改下最后的next指向为head即可。

双向链表与单链表的区别在于，在单链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。  
  双向链表提供了两种迭代列表的方法：从头到尾，或则反过来。在单链表中，如果我们在迭代列表中错过了要找的元素，就需要回到列表的起点，重新开始迭代，这是双向列表的优点。  
  双向链表与单向链表的实现类似，需要同时控制next、prev两个指针，同时需要增加尾引用tail。

function DoubleLinkedList() { // Node辅助类，表示要加入列表的项，element是即将添加到列表的值，next是指向列表中下一个节点项的指针 let Node = function (element) { this.element = element this.prev = null // 新增一个向前的指针 this.next = null } let length = 0 let head = null let tail = null // 新增一个尾引用 // 向链表尾部追加元素 this.append = function (element) { let node = new Node(element) let current if (head === null) { // 列表中第一个节点 head = node // head与tail是同一个元素 tail = node } else { current = head while (current.next) { current = current.next // 找到最后一项，是null } current.next = node // 给最后一项赋值 node.prev = current tail = node // 修改尾引用 } length++ // 更新列表的长度 } // 从链表中移除指定位置元素 this.removeAt = function (position) { if (position > -1 && position < length) { // 值没有越界 let current = head let previous, index = 0 if (position === 0) { // 移除第一项 head = current.next if (length === 1) { // 只有一项 tail = null } else { head.prev = null } } else if (position === length - 1) { // 移除最后一项 current = tail tail = current.prev tail.next = null } else { while (index++ < position) { previous = current current = current.next } previous.next = current.next // 将previous与current的下一项连接起来，跳过current，从而移除 current.next.prev = previous } length-- // 更新列表的长度 return current.element } else { return null } } // 在链表任意位置插入一个元素 this.insert = function (position, element) { if (position >= 0 && position <= length) { // 检查越界值 let node = new Node(element), current = head, previous, index = 0 if (position === 0) { // 在第一个位置添加 if (!head) { head = node tail = node }else { node.next = current current.prev = node head = node } node.next = current head = node } else if (position === length) { current = tail current.next = node node.prev = current tail = node } else { while (index++ < position) { previous = current current = current.next } node.next = current // 在previous与current的下一项之间插入node previous.next = node current.prev = node node.prev = previous } length++ return true } else { return false } } // 把链表内的值转换成一个字符串 this.toString = function () { let current = head, string = '' while (current) { string += current.element + ' ' current = current.next } return string } // 在链表中查找元素并返回索引值 this.indexOf = function (element) { let current = head, index = 0 while (current) { if (element === current.element) { return index } index++ current = current.next } return -1 } // 从链表中移除指定元素 this.remove = function (element) { let index = this.indexOf(element) return this.removeAt(index) } this.isEmpty = function () { return length === 0 } this.size = function () { return length } this.getHead = function () { return head } } let list = new DoubleLinkedList() list.append(1) list.append(2) console.log(list.toString()) // 1 2 list.insert(0, 'hello') list.insert(1, 'world') console.log(list.toString()) // hello world 1 2 list.remove(1) list.remove(2) console.log(list.toString()) // hello world

转载于:https://www.cnblogs.com/leftJS/p/11074346.html

[https_cloud.tencent.com_developer_article_1114246]: https://cloud.tencent.com/developer/article/1114246
[Link 1]: https://baike.baidu.com/item/%E9%93%BE%E8%A1%A8/9794473
[1620]: https://ask.qcloudimg.com/http-save/yehe-1578879/yt1zwciv5e.png?imageView2/2/w/1620