JavaScript 链表

链表是一种常见的数据结构，它由一系列节点组成，每个节点存储数据以及指向列表中下一个节点的链接。链表提供了一种灵活的方式来组织和操作数据，尤其适用于需要频繁插入或删除元素的场景。

链表的基本概念

节点(Node)

链表中的每一个元素称为一个节点，每个节点通常包含两部分：数据和指向下一个节点的引用。节点的定义如下：

class Node {
  constructor(data, next = null) {
    this.data = data; // 存储的数据
    this.next = next; // 指向下一个节点的引用
  }
}

链表的类型

链表主要有两种类型：单向链表和双向链表。

单向链表(Singly Linked List)

在单向链表中，每个节点只包含对下一个节点的引用。

双向链表(Doubly Linked List)

在双向链表中，每个节点不仅包含对下一个节点的引用，还包含对前一个节点的引用，这使得双向链表在某些操作上比单向链表更高效。

创建单向链表

为了实现单向链表，我们需要定义一个链表类，并在其中添加方法来管理链表的操作。

链表类定义

首先，我们定义一个LinkedList类，用于初始化链表并添加节点。

// www.javascriptcn.com code example
class LinkedList {
  constructor() {
    this.head = null; // 链表头部
  }

  // 添加新节点到链表尾部
  append(data) {
    const newNode = new Node(data);
    
    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // 在链表头部添加新节点
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }

  // 删除节点
  deleteNode(key) {
    let current = this.head;
    let previous = null;

    if (current !== null && current.data === key) {
      this.head = current.next;
      return;
    }

    while (current !== null && current.data !== key) {
      previous = current;
      current = current.next;
    }

    if (current === null) return;

    previous.next = current.next;
  }

  // 查找节点
  findNode(key) {
    let current = this.head;
    while (current !== null) {
      if (current.data === key) return current;
      current = current.next;
    }
    return null;
  }

  // 打印链表
  printList() {
    let current = this.head;
    let list = [];
    while (current) {
      list.push(current.data);
      current = current.next;
    }
    console.log(list.join(" -> "));
  }
}

链表的应用示例

链表常用于实现一些特殊的数据结构，如栈(stack)、队列(queue)等。

使用链表实现栈

栈是一种后进先出(LIFO)的数据结构，可以使用链表轻松实现。

// www.javascriptcn.com code example
class Stack {
  constructor() {
    this.list = new LinkedList();
  }

  push(item) {
    this.list.prepend(item);
  }

  pop() {
    if (!this.isEmpty()) {
      const topItem = this.list.head.data;
      this.list.deleteNode(this.list.head.data);
      return topItem;
    }
    return null;
  }

  isEmpty() {
    return this.list.head === null;
  }

  peek() {
    return this.list.head ? this.list.head.data : null;
  }

  printStack() {
    this.list.printList();
  }
}

通过上述代码，我们可以看到链表在实际应用中的灵活性和强大功能。链表作为一种基本的数据结构，其理解和掌握对于任何前端开发者来说都是非常重要的。