js如何实现链表

链表基础概念

链表是一种线性数据结构，由节点（Node）组成，每个节点包含数据域和指针域。指针域存储下一个节点的地址，最后一个节点的指针指向null。

实现单链表

单链表是最简单的链表形式，每个节点只有一个指向下一个节点的指针。

定义节点类

class Node {
  constructor(data) {
    this.data = data; // 数据域
    this.next = null; // 指针域
  }
}

链表类实现

class LinkedList {
  constructor() {
    this.head = null; // 链表头节点
    this.length = 0;  // 链表长度
  }

  // 添加节点到链表末尾
  append(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.length++;
  }

  // 插入节点到指定位置
  insert(position, data) {
    if (position < 0 || position > this.length) return false;
    const newNode = new Node(data);
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let current = this.head;
      let index = 0;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      newNode.next = current;
      previous.next = newNode;
    }
    this.length++;
    return true;
  }

  // 删除指定位置的节点
  removeAt(position) {
    if (position < 0 || position >= this.length) return null;
    let current = this.head;
    if (position === 0) {
      this.head = current.next;
    } else {
      let index = 0;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }
    this.length--;
    return current.data;
  }

  // 查找节点位置
  indexOf(data) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

  // 链表转字符串
  toString() {
    let current = this.head;
    let str = '';
    while (current) {
      str += current.data + (current.next ? ' -> ' : '');
      current = current.next;
    }
    return str;
  }
}

使用示例

const list = new LinkedList();
list.append(10);
list.append(20);
list.insert(1, 15);
console.log(list.toString()); // 输出: "10 -> 15 -> 20"
list.removeAt(1);
console.log(list.toString()); // 输出: "10 -> 20"

双向链表实现

双向链表的节点包含前驱和后继指针，实现方式类似单链表，但需额外处理prev指针。

双向链表节点类

class DoublyNode extends Node {
  constructor(data) {
    super(data);
    this.prev = null; // 前驱指针
  }
}

双向链表类实现 需在单链表基础上重写append、insert、removeAt等方法，处理prev指针的指向逻辑。