当前位置：首页 > JavaScript

链表的实现js

2026-04-04 13:46:34JavaScript

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表分为单向链表、双向链表和循环链表等类型。

单向链表的实现

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

定义节点类

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

定义链表类

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

  // 在链表末尾添加节点
  add(data) {
    const node = new ListNode(data);
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    this.size++;
  }

  // 在指定位置插入节点
  insertAt(data, index) {
    if (index < 0 || index > this.size) return false;
    const node = new ListNode(data);
    if (index === 0) {
      node.next = this.head;
      this.head = node;
    } else {
      let current = this.head;
      let prev = null;
      let i = 0;
      while (i < index) {
        prev = current;
        current = current.next;
        i++;
      }
      node.next = current;
      prev.next = node;
    }
    this.size++;
    return true;
  }

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

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

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

  // 打印链表内容
  print() {
    let current = this.head;
    let str = "";
    while (current) {
      str += current.data + " -> ";
      current = current.next;
    }
    str += "null";
    console.log(str);
  }
}

双向链表的实现

双向链表的每个节点有两个指针，分别指向前一个节点和后一个节点。

定义节点类

class DoublyListNode {
  constructor(data) {
    this.data = data;
    this.prev = null;
    this.next = null;
  }
}

定义双向链表类

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 在链表末尾添加节点
  add(data) {
    const node = new DoublyListNode(data);
    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
  }

  // 其他方法与单向链表类似，需要考虑prev指针的维护
}

循环链表的实现

循环链表的最后一个节点指向第一个节点，形成一个环。

定义循环链表类

链表的实现js

class CircularLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  add(data) {
    const node = new ListNode(data);
    if (!this.head) {
      this.head = node;
      node.next = this.head;
    } else {
      let current = this.head;
      while (current.next !== this.head) {
        current = current.next;
      }
      current.next = node;
      node.next = this.head;
    }
    this.size++;
  }
}