实现一个链表结构

问题

链表是一种基础的线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。需要实现一个单向链表，支持以下操作：

• 在链表末尾添加节点
• 在指定位置插入节点
• 删除指定位置的节点
• 查找节点
• 获取链表长度
• 遍历链表

解答

// 链表节点类
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

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

  // 在链表末尾添加节点
  append(value) {
    const newNode = new ListNode(value);
    
    if (!this.head) {
      // 如果链表为空，新节点作为头节点
      this.head = newNode;
    } else {
      // 找到最后一个节点
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    
    this.size++;
    return this;
  }

  // 在指定位置插入节点
  insert(index, value) {
    if (index < 0 || index > this.size) {
      throw new Error('索引越界');
    }

    const newNode = new ListNode(value);

    if (index === 0) {
      // 在头部插入
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // 找到插入位置的前一个节点
      let current = this.head;
      let prev = null;
      let currentIndex = 0;

      while (currentIndex < index) {
        prev = current;
        current = current.next;
        currentIndex++;
      }

      newNode.next = current;
      prev.next = newNode;
    }

    this.size++;
    return this;
  }

  // 删除指定位置的节点
  removeAt(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('索引越界');
    }

    let current = this.head;

    if (index === 0) {
      // 删除头节点
      this.head = current.next;
    } else {
      let prev = null;
      let currentIndex = 0;

      while (currentIndex < index) {
        prev = current;
        current = current.next;
        currentIndex++;
      }

      prev.next = current.next;
    }

    this.size--;
    return current.value;
  }

  // 删除指定值的节点
  remove(value) {
    if (!this.head) return false;

    if (this.head.value === value) {
      this.head = this.head.next;
      this.size--;
      return true;
    }

    let current = this.head;
    let prev = null;

    while (current) {
      if (current.value === value) {
        prev.next = current.next;
        this.size--;
        return true;
      }
      prev = current;
      current = current.next;
    }

    return false;
  }

  // 查找节点索引
  indexOf(value) {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  // 获取指定位置的节点值
  get(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }

    let current = this.head;
    let currentIndex = 0;

    while (currentIndex < index) {
      current = current.next;
      currentIndex++;
    }

    return current.value;
  }

  // 判断链表是否为空
  isEmpty() {
    return this.size === 0;
  }

  // 获取链表长度
  getSize() {
    return this.size;
  }

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

  // 转换为数组
  toArray() {
    const result = [];
    let current = this.head;

    while (current) {
      result.push(current.value);
      current = current.next;
    }

    return result;
  }

  // 打印链表
  print() {
    console.log(this.toArray().join(' -> '));
  }
}

使用示例

// 创建链表
const list = new LinkedList();

// 添加节点
list.append(1).append(2).append(3);
list.print(); // 1 -> 2 -> 3

// 在指定位置插入
list.insert(1, 1.5);
list.print(); // 1 -> 1.5 -> 2 -> 3

// 获取节点值
console.log(list.get(0)); // 1
console.log(list.get(2)); // 2

// 查找节点
console.log(list.indexOf(2)); // 2
console.log(list.indexOf(10)); // -1

// 删除节点
list.removeAt(1);
list.print(); // 1 -> 2 -> 3

list.remove(2);
list.print(); // 1 -> 3

// 获取链表信息
console.log(list.getSize()); // 2
console.log(list.isEmpty()); // false

// 转换为数组
console.log(list.toArray()); // [1, 3]

// 清空链表
list.clear();
console.log(list.isEmpty()); // true

关键点

• 节点设计：使用 ListNode 类封装节点，包含 value 和 next 两个属性
• 头节点管理：通过 head 指针维护链表的起始位置，空链表时 head 为 null
• 遍历操作：大部分操作需要从头节点开始遍历，时间复杂度为 O(n)
• 边界处理：特别注意头节点的插入和删除操作，需要单独处理
• 索引越界检查：在插入和删除操作前要验证索引的合法性
• 链式调用：部分方法返回 this，支持链式调用提升代码可读性
• 长度维护：使用 size 属性实时维护链表长度，避免每次都遍历计算
• 前驱节点：在插入和删除操作中，需要维护 prev 指针指向当前节点的前一个节点