JS 链表|极客笔记

JS 链表

在计算机科学中，链表是一种常见的数据结构，它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以用来表示有序的元素集合，具有动态插入和删除操作的优点。在本文中，我们将详细讨论在 JavaScript 中实现链表的方法。

什么是链表

链表是一种常见的数据结构，它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。这种结构类似于火车车厢的排列方式，每个车厢（节点）都连接着下一个车厢。

链表有两种常见类型：单向链表和双向链表。单向链表中，每个节点只有一个指向下一个节点的指针；而双向链表中，每个节点有两个指针，分别指向前一个节点和后一个节点。在本文中，我们将重点讨论单向链表的实现。

实现链表

在 JavaScript 中，可以通过对象来实现链表，下面是一个简单的链表类的实现：

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  // 在链表头部插入新节点
  insertFirst(data) {
    this.head = new Node(data, this.head);
  }

  // 删除头部节点
  deleteFirst() {
    if (this.head !== null) {
      this.head = this.head.next;
    }
  }

  // 清空链表
  clear() {
    this.head = null;
  }

  // 打印链表内容
  printList() {
    let current = this.head;
    while (current !== null) {
      console.log(current.data);
      current = current.next;
    }
  }
}

// 创建一个链表实例
const ll = new LinkedList();
ll.insertFirst(1);
ll.insertFirst(2);
ll.insertFirst(3);

ll.printList(); // 输出：3 2 1

在上面的代码中，我们首先定义了一个 Node 类来表示链表中的节点，每个节点包含两个属性：data 存储数据元素，next 指向下一个节点。然后定义了 LinkedList 类来表示整个链表，包括插入节点、删除节点、清空链表和打印链表内容等操作。

链表操作

插入节点

链表的插入节点操作有两种情况：在链表头部插入节点和在指定位置插入节点。我们已经在上面的代码中实现了在链表头部插入节点的方法 insertFirst，下面我们来实现在指定位置插入节点的方法 insertAt：

// 在指定位置插入节点
insertAt(index, data) {
  if (index < 0) {
    throw new Error('Index out of range');
  }

  if (index === 0) {
    this.insertFirst(data);
    return;
  }

  let current = this.head;
  let count = 0;
  while (current !== null && count < index - 1) {
    current = current.next;
    count++;
  }

  if (current === null) {
    throw new Error('Index out of range');
  }

  current.next = new Node(data, current.next);
}

删除节点

链表的删除节点操作也有两种情况：删除头部节点和删除指定位置节点。我们已经在上面的代码中实现了删除头部节点的方法 deleteFirst，下面我们来实现删除指定位置节点的方法 deleteAt：

// 删除指定位置节点
deleteAt(index) {
  if (index < 0) {
    throw new Error('Index out of range');
  }

  if (index === 0) {
    this.deleteFirst();
    return;
  }

  let current = this.head;
  let previous = null;
  let count = 0;
  while (current !== null && count < index) {
    previous = current;
    current = current.next;
    count++;
  }

  if (current === null) {
    throw new Error('Index out of range');
  }

  previous.next = current.next;
}

获取节点

获取节点操作可以获取链表中指定位置的节点数据，我们可以实现一个 getAt 方法来实现这个功能：

// 获取指定位置节点数据
getAt(index) {
  if (index < 0) {
    throw new Error('Index out of range');
  }

  let current = this.head;
  let count = 0;
  while (current !== null && count < index) {
    current = current.next;
    count++;
  }

  if (current === null) {
    throw new Error('Index out of range');
  }

  return current.data;
}

链表示例

下面是一个完整的链表示例，演示了如何使用上面实现的链表类来操作链表：

// 创建一个链表实例
const ll = new LinkedList();

ll.insertFirst(3);
ll.insertFirst(2);
ll.insertFirst(1);

ll.printList(); // 输出：1 2 3

ll.insertAt(1, 4);
ll.printList(); // 输出：1 4 2 3

ll.deleteAt(2);
ll.printList(); // 输出：1 4 3

console.log(ll.getAt(1)); // 输出：4

以上是关于在 JavaScript 中实现链表的详细内容，我们可以通过上面的示例看到，我们成功地实现了链表的插入、删除和获取节点的操作。链表作为一种常见的数据结构，在实际开发中也有着广泛的应用，特别是在需要频繁插入和删除操作的场景下。