单链表的操作核心有:
push(value) - 在链表的末尾/头部添加一个节点
pop() - 从链表的末尾/头部删除一个节点
get(index) - 返回指定索引处的节点
delete(index) - 删除指定索引处的节点
isEmpty() - 根据列表长度返回true或false
print() - 返回链表的可见表示
实现如下:
class Node {
constructor(data) {
this.data = data
this.next = null
}
}
class LinkedList {
constructor() {
this.head = null
this.tail = null
this.length = 0
}
push (data) {
const node = new Node(data) // 创建一个新节点
if (this.head === null) { // 检查头部是否为空
this.head = node
this.tail = node
}
this.tail.next = node
this.tail = node
this.length++
}
pop () {
if (this.isEmpty()) {
return null
}
if (this.head === this.tail) {
this.head = null
this.tail = null
this.length--
return this.tail
}
let node = this.tail
let currentNode = this.head
let penultimate
while (currentNode) {
if (currentNode.next === this.tail) {
penultimate = currentNode
break
}
currentNode = currentNode.next
}
penultimate.next = null
this.tail = penultimate
this.length--
return node
}
get (index) { // 处理边界条件
if (index === 0) {
return this.head
}
if (index < 0 || index > this.length) {
return null
}
let currentNode = this.head
let i = 0
while (i < index) {
i++
currentNode = currentNode.next
}
return currentNode
}
delete (index) {
let currentNode = this.head
if (index === 0) {
let deleteNode
currentNode.next = this.head
deleteNode = currentNode
this.length--
return deleteNode
}
if (index < 0 || index > length) {
return null
}
let i = 0
let previous
while (i < index) {
i++
previous = currentNode
currentNode = currentNode.next
}
previous.next = currentNode.next
this.length--
return currentNode
}
isEmpty () {
return this.length === 0
}
print () {
const list = []
let currentNode = this.head
while (currentNode) {
list.push(currentNode.data)
currentNode = currentNode.next
}
return list.join('=>')
}
}
// test
const l = new LinkedList()
const valuesB = ['A', 'B', 'C', 'D', 'E']
valuesB.forEach(value => l.push(value))