SorryToPerson logo
返回
算法2026-04-15·7 分钟

算法知识库：链表实现

单向链表、双向链表及常见链表操作的 JavaScript/TypeScript 实现。

链表实现

1. 单向链表节点定义

ts
class ListNode<T = number> {
  value: T;
  next: ListNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

2. 单向链表基本操作

ts
class SinglyLinkedList<T = number> {
  head: ListNode<T> | null = null;

  // 时间复杂度: O(n)，空间复杂度: O(1)
  append(value: T) {
    const node = new ListNode(value);
    if (!this.head) {
      this.head = node;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = node;
  }

  // 时间复杂度: O(n)，空间复杂度: O(1)
  find(value: T): ListNode<T> | null {
    let current = this.head;
    while (current) {
      if (current.value === value) return current;
      current = current.next;
    }
    return null;
  }

  // 时间复杂度: O(n)，空间复杂度: O(1)
  delete(value: T) {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next && current.next.value !== value) {
      current = current.next;
    }
    if (current.next) {
      current.next = current.next.next;
    }
  }
}

3. 双向链表实现

ts
class DoublyListNode<T = number> {
  value: T;
  prev: DoublyListNode<T> | null = null;
  next: DoublyListNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

class DoublyLinkedList<T = number> {
  head: DoublyListNode<T> | null = null;
  tail: DoublyListNode<T> | null = null;

  // 时间复杂度: O(1)，空间复杂度: O(1)
  append(value: T) {
    const node = new DoublyListNode(value);
    if (!this.tail) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
  }
}

4. 链表常见题型

  • 反转链表。
  • 快慢指针寻找中间节点。
  • 检测环形链表。
  • 合并两个有序链表。

5. 实现要点

  • 链表不支持随机访问，需要顺序遍历。
  • 要注意节点引用的更新，避免丢失后续节点。
  • 双向链表增加了 prev 指针，可实现 O(1) 删除操作。
算法链表JavaScript