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

https://cloud.tencent.com/developer/article/1114246php

 

链表存储有序的元素的集合，可是和数组不一样的是，链表中的元素在内存中的存储并非连续的。每个链表元素都包含了一个存储元素自己的节点和一个指向下一个元素的引用。看起来就像这样：html

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

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 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 worldfunction 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