JavaScript实现单链表过程解析

什么是单链表？

单链表是一种常见的数据结构，它由若干个节点组成，每个节点包含两个部分：数据域和指针域。数据域用来存储节点的数据，指针域则用来存储下一个节点的地址。由于每个节点只包含一个指针域，所以它们被称为单链表。

实现单链表的关键操作

1.创建节点

创建节点的过程就是一个简单的对象创建过程，我们可以使用对象字面量来表示节点。

const node = {
  data: 1,  // 存储数据
  next: null  // 指向下一个节点的指针，初始值为null
};

2.添加节点

添加节点通常有两种方法，一种是在链表的头部添加节点，另一种是在链表的尾部添加节点。

2.1 在头部添加节点

在头部添加节点可以通过改变头节点的指针域来实现。新创建的节点将成为新的头节点，其指针域指向旧的头节点。

const node1 = { data: 1, next: null };
const node2 = { data: 2, next: node1 };
const head = { data: 0, next: node2 };

// 添加节点
const node0 = { data: 0, next: head };
head.next = node0;

2.2 在尾部添加节点

在尾部添加节点需要遍历整个链表，找到尾节点，然后将新节点添加到尾节点的后面。

const node1 = { data: 1, next: null };
const node2 = { data: 2, next: node1 };
const head = { data: 0, next: node2 };

// 添加节点
const node3 = { data: 3, next: null };
let p = head;
while (p.next !== null) {
  p = p.next;  // 找到尾节点
}
p.next = node3;  // 添加节点

3.删除节点

删除节点通常有两种方法，一种是删除某个特定节点，另一种是删除链表的头节点。

3.1 删除特定节点

删除特定节点需要遍历整个链表，找到要删除的节点，然后改变此节点前一个节点的指针域指向此节点的下一个节点。

const node1 = { data: 1, next: null };
const node2 = { data: 2, next: node1 };
const head = { data: 0, next: node2 };

// 删除节点
let p = head;
while (p.next !== null) {
  if (p.next.data === 2) {  // 找到要删除的节点
    p.next = p.next.next;  // 删除节点
    break;
  }
  p = p.next;
}

3.2 删除头节点

删除头节点可以通过将头节点的指针域指向下一个节点来实现。

const node1 = { data: 1, next: null };
const node2 = { data: 2, next: node1 };
const head = { data: 0, next: node2 };

// 删除头节点
head.next = node2.next;

示例说明

示例一：创建一个单链表

const node1 = { data: 1, next: null };
const node2 = { data: 2, next: node1 };
const head = { data: 0, next: node2 };

示例二：删除链表中的节点

const node1 = { data: 1, next: null };
const node2 = { data: 2, next: node1 };
const head = { data: 0, next: node2 };

let p = head;
while (p.next !== null) {
  if (p.next.data === 2) {  // 找到要删除的节点
    p.next = p.next.next;  // 删除节点
    break;
  }
  p = p.next;
}