链表是一个天然的线性结构,也是一个天然的递归结构。可以很方便的插入和删除节点。但是无法像数组一样使用index进行查找。只能通过遍历的方式。 #### 实现: ````javascript
class Node {
constructor(value, next) {
this.value = value
this.next = next
}
}
class ListNode {
constructor() {
this.size = 0
this.header = new Node(null, null)
}
insertNode(previousNode, value) {
let nextNode = previousNode.next
let currentNode = new Node(value, nextNode)
previousNode.next = currentNode
this.size++ // 链表长度+1
return currentNode
}
getNode(targetValue) {
if (!targetValue) return
let node = this.header
const traversal = node => {
if (node.value === targetValue) {
return node
}
if (node.next) {
return traversal(node.next)
}
}
}
removeNode(value) {
const findPreviousNode = (value) => {
let currentNode = this.header
while (currentNode.next) {
if (value === currentNode.next.value) {
return currentNode
}
currentNode = currentNode.next
}
}
let previousNode = findPrevious(value)
let nextNode = previousNode.next.next()
this.size-- // 链表长度-1
previousNode.next = nextNode
}
} ````