js实现链表

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中不是连续存储的，插入和删除操作更高效，但访问元素需要遍历。

链表的实现

定义节点类

链表的基础是节点，每个节点包含数据（value）和指向下一个节点的指针（next）。

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

链表类的基本结构

链表类需要管理节点的增删改查，通常包含头节点（head）和尾节点（tail）的引用。

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

添加节点到尾部

通过判断链表是否为空，分别处理头节点和尾节点的更新。

append(value) {
  const newNode = new ListNode(value);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.length++;
}

添加节点到头部

更新头节点，并处理空链表的特殊情况。

prepend(value) {
  const newNode = new ListNode(value);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.next = this.head;
    this.head = newNode;
  }
  this.length++;
}

删除头节点

通过将头节点指向下一个节点实现删除，注意处理链表长度为1的情况。

deleteHead() {
  if (!this.head) return null;
  const deletedHead = this.head;
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
  } else {
    this.head = this.head.next;
  }
  this.length--;
  return deletedHead.value;
}

删除尾节点

需要遍历链表找到倒数第二个节点，更新其next指针。

deleteTail() {
  if (!this.head) return null;
  let current = this.head;
  let deletedTail = this.tail;
  if (this.head === this.tail) {
    this.head = null;
    this.tail = null;
  } else {
    while (current.next !== this.tail) {
      current = current.next;
    }
    current.next = null;
    this.tail = current;
  }
  this.length--;
  return deletedTail.value;
}

查找节点

遍历链表，比较节点的值是否与目标值匹配。

find(value) {
  let current = this.head;
  while (current) {
    if (current.value === value) {
      return current;
    }
    current = current.next;
  }
  return null;
}

插入节点到指定位置

通过遍历找到指定位置的节点，调整指针完成插入。

insert(index, value) {
  if (index < 0 || index > this.length) return false;
  if (index === 0) {
    this.prepend(value);
    return true;
  }
  if (index === this.length) {
    this.append(value);
    return true;
  }
  const newNode = new ListNode(value);
  let current = this.head;
  for (let i = 0; i < index - 1; i++) {
    current = current.next;
  }
  newNode.next = current.next;
  current.next = newNode;
  this.length++;
  return true;
}

链表反转

反转链表需要调整每个节点的next指针方向。

reverse() {
  let prev = null;
  let current = this.head;
  this.tail = this.head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  this.head = prev;
}

链表的遍历

可以通过循环或递归的方式遍历链表的所有节点。

traverse(callback) {
  let current = this.head;
  while (current) {
    callback(current.value);
    current = current.next;
  }
}

复杂度分析

• 插入/删除头部：O(1)
• 插入/删除尾部：O(1)（有尾指针时）
• 查找：O(n)
• 访问元素：O(n)

应用场景

链表适合频繁插入和删除的场景，如实现队列、栈或哈希表的冲突解决。其动态内存分配特性避免了数组的扩容开销。