要实现一个双向链表（Doubly Linked List），需要定义一个节点类和一个链表类。
双向链表中的每个节点都有两个指针，一个指向下一个节点（next），一个指向上一个节点（prev）。
链表类则包含了各种操作链表的方法，如添加节点、删除节点、在特定位置插入节点、查找节点和遍历链表。
以下是一个实现双向链表的示例：
1. 节点类（Node Class）
class Node {
constructor(data) {
this.data = data; // 节点存储的数据
this.next = null; // 指向下一个节点的指针
this.prev = null; // 指向上一个节点的指针
}
}
2. 双向链表类（DoublyLinkedList Class）
class DoublyLinkedList {
constructor() {
this.head = null; // 链表的头节点
this.tail = null; // 链表的尾节点
this.size = 0; // 链表的节点数量
}
// 添加节点到链表的末尾
append(data) {
const newNode = new Node(data);
if (this.head === null) {
// 链表为空时，新节点是头节点和尾节点
this.head = newNode;
this.tail = newNode;
} else {
// 链表非空时，更新尾节点的指针
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.size++;
}
// 在特定位置插入节点
insertAt(position, data) {
if (position < 0 || position > this.size) {
throw new Error('Index out of bounds');
}
const newNode = new Node(data);
if (position === 0) {
// 插入到链表的头部
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (position === this.size) {
// 插入到链表的尾部
this.append(data);
} else {
// 插入到链表的中间
let current = this.head;
for (let i = 0; i < position - 1; i++) {
current = current.next;
}
newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;
}
this.size++;
}
// 删除特定位置的节点
removeAt(position) {
if (position < 0 || position >= this.size) {
throw new Error('Index out of bounds');
}
if (position === 0) {
// 删除头节点
if (this.head === this.tail) {
// 只有一个节点
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
} else if (position === this.size - 1) {
// 删除尾节点
this.tail = this.tail.prev;
this.tail.next = null;
} else {
// 删除中间节点
let current = this.head;
for (let i = 0; i < position; i++) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
}
this.size--;
}
// 查找特定节点
find(data) {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null; // 没有找到
}
// 遍历链表并打印节点数据
traverse() {
let current = this.head;
while (current) {
console.log(current.data);
current = current.next;
}
}
// 从尾部开始遍历链表并打印节点数据
traverseReverse() {
let current = this.tail;
while (current) {
console.log(current.data);
current = current.prev;
}
}
}
用法示例
const list = new DoublyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.insertAt(1, 4); // 链表现在是 1 -> 4 -> 2 -> 3
list.traverse(); // 输出: 1, 4, 2, 3
list.removeAt(1); // 链表现在是 1 -> 2 -> 3
list.traverse(); // 输出: 1, 2, 3
console.log(list.find(2)); // 输出: Node { data: 2, next: Node { ... }, prev: Node { ... } }
list.traverseReverse(); // 输出: 3, 2, 1
