js实现链表思路
实现链表的基本思路
在JavaScript中实现链表，需要理解链表的基本结构和操作。链表由节点（Node）组成，每个节点包含数据和指向下一个节点的指针。以下是实现链表的关键步骤。
定义节点类
每个节点需要存储数据和指向下一个节点的引用。可以定义一个Node类来实现这一点。
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}定义链表类
链表类需要管理节点的操作，包括插入、删除、遍历等。以下是链表类的基本结构。
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}插入节点
插入节点分为头部插入和尾部插入。头部插入直接将新节点作为头节点，尾部插入需要遍历到链表末尾。
// 头部插入
addAtHead(data) {
const newNode = new Node(data);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
// 尾部插入
addAtTail(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
this.size++;
}删除节点
删除节点需要找到目标节点并调整指针。删除头节点和中间节点的逻辑略有不同。
// 删除指定数据的节点
deleteNode(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
this.size--;
return;
}
let current = this.head;
while (current.next) {
if (current.next.data === data) {
current.next = current.next.next;
this.size--;
return;
}
current = current.next;
}
}遍历链表
遍历链表可以通过循环从头节点开始，依次访问每个节点。
printList() {
let current = this.head;
let result = [];
while (current) {
result.push(current.data);
current = current.next;
}
console.log(result.join(' -> '));
}查找节点
查找节点可以通过遍历链表，比较节点的数据是否匹配目标值。
findNode(data) {
let current = this.head;
while (current) {
if (current.data === data) {
return current;
}
current = current.next;
}
return null;
}反转链表
反转链表需要调整每个节点的指针方向，使其指向前一个节点。
reverseList() {
let prev = null;
let current = this.head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
}示例用法
以下是一个完整的链表实现示例，展示了如何创建链表并进行操作。
const list = new LinkedList();
list.addAtTail(1);
list.addAtTail(2);
list.addAtTail(3);
list.printList(); // 输出: 1 -> 2 -> 3
list.addAtHead(0);
list.printList(); // 输出: 0 -> 1 -> 2 -> 3
list.deleteNode(2);
list.printList(); // 输出: 0 -> 1 -> 3
list.reverseList();
list.printList(); // 输出: 3 -> 1 -> 0通过以上步骤，可以实现一个功能完整的链表结构，并支持常见的操作。
