如何用JavaScript实现功能齐全的单链表详解

下面是详细讲解如何用JavaScript实现功能齐全的单链表的攻略。

确定单链表的基本结构

单链表是一种数据结构，它由一个个节点组成。每个节点都包含一个数据域和一个指针域，指针指向下一个节点。在JavaScript中，可以使用对象来表示单链表的节点，其基本结构如下：

// 定义单链表节点对象
function ListNode(val) {
  this.val = val; // 数据域
  this.next = null; // 指针域，指向下一个节点
}

实现单链表的基本功能

有了节点对象，我们就可以按照单链表的定义来实现它的基本功能了。

1. 在单链表末尾添加节点

实现在单链表末尾添加节点的方法：

// 在单链表末尾添加节点
function appendNode(head, val) {
  const newNode = new ListNode(val);
  let p = head;
  while (p.next !== null) {
    p = p.next;
  }
  p.next = newNode;
}

2. 在单链表任意位置插入节点

实现在单链表任意位置插入节点的方法：

// 在单链表任意位置插入节点
function insertNode(head, index, val) {
  const newNode = new ListNode(val);
  let p = head;
  let i = 0;
  while (p !== null && i < index) {
    p = p.next;
    i++;
  }
  if (p === null || i > index) {
    throw new Error('Index out of range');
  }
  newNode.next = p.next;
  p.next = newNode;
}

3. 在单链表任意位置删除节点

实现在单链表任意位置删除节点的方法：

// 在单链表任意位置删除节点
function deleteNode(head, index) {
  let p = head;
  let i = 0;
  while (p !== null && i < index) {
    p = p.next;
    i++;
  }
  if (p === null || p.next === null || i > index) {
    throw new Error('Index out of range');
  }
  p.next = p.next.next;
}

4. 遍历单链表

实现遍历单链表的方法：

// 遍历单链表
function printList(head) {
  let p = head.next;
  const result = [];
  while (p !== null) {
    result.push(p.val);
    p = p.next;
  }
  console.log(result.join('->'));
}

示例说明

假设我们有一个包含5个节点的单链表，其节点的值依次为1、2、3、4、5，那么我们可以先创建一个头节点，其指针域为空：

const head = new ListNode();

然后在这个单链表末尾添加一个值为6的节点：

appendNode(head, 6);

此时单链表的节点值依次为1、2、3、4、5、6。

再在单链表的第3个位置插入一个值为7的节点：

insertNode(head, 2, 7);

此时单链表的节点值依次为1、2、7、3、4、5、6。

最后在单链表的第4个位置删除一个节点：

deleteNode(head, 3);

此时单链表的节点值依次为1、2、7、4、5、6。

最后我们可以遍历整个单链表：

printList(head); // 1->2->7->4->5->6

以上就是用JavaScript实现功能齐全的单链表的攻略。