JavaScript数据结构_链表与双向链表-js教程-PHP中文网

JavaScript数据结构_链表与双向链表

betcha

发布： 2025-11-21 14:49:53

原创

461人浏览过

链表是一种通过节点存储数据的非连续内存结构，每个节点包含数据域和指针域，通过指针连接实现高效插入删除。单向链表由头节点开始，next指向下一节点，末节点指向null；基本操作包括头部/尾部插入、删除指定值节点、查找与遍历。双向链表增加prev指针，支持前后双向遍历，提升操作灵活性。相比数组，链表适合频繁修改场景，但访问需从头遍历，时间复杂度O(n)。常用于实现栈队列、浏览器历史、播放列表等动态集合。

javascript数据结构_链表与双向链表

链表是一种常见的数据结构，它通过节点（node）来存储数据，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中不是连续存储的，而是通过指针连接各个节点。这使得插入和删除操作更高效，尤其在频繁修改数据时。

链表的基本结构

一个最简单的链表节点通常包含两个部分：数据域和指针域。

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

登录后复制

链表本身由一个头节点（head）开始，通过 next 指针依次连接后续节点，直到最后一个节点的 next 为 null，表示链表结束。

基本操作包括：

立即学习“Java免费学习笔记（深入）”；

插入节点：可以在头部、尾部或指定位置插入新节点
删除节点：根据值或位置找到并移除节点
查找节点：遍历链表寻找特定值
遍历链表：从头到尾访问每个节点

实现单向链表

下面是一个简单的单向链表实现：

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

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

  prepend(data) {
    const newNode = new ListNode(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  remove(data) {
    if (!this.head) return;

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

    let current = this.head;
    while (current.next && current.next.data !== data) {
      current = current.next;
    }

    if (current.next) {
      current.next = current.next.next;
      this.size--;
    }
  }

  display() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    return result;
  }
}

登录后复制

使用示例：

const list = new LinkedList();
list.append(10);
list.append(20);
list.prepend(5);
console.log(list.display()); // [5, 10, 20]
list.remove(10);
console.log(list.display()); // [5, 20]

登录后复制

双向链表的特点与实现

双向链表在单向链表的基础上增加了前驱指针（prev），每个节点既能指向下一个节点，也能指向前一个节点。这种结构支持从任意方向遍历，提高了某些操作的效率。

落笔AI

AI写作，AI写网文、AI写长篇小说、短篇小说

查看详情

节点定义如下：

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

登录后复制

双向链表的插入和删除操作需要同时维护 next 和 prev 指针。

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

  append(data) {
    const newNode = new DoublyListNode(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  remove(data) {
    let current = this.head;
    while (current && current.data !== data) {
      current = current.next;
    }

    if (!current) return;

    if (current.prev) {
      current.prev.next = current.next;
    } else {
      this.head = current.next;
    }

    if (current.next) {
      current.next.prev = current.prev;
    } else {
      this.tail = current.prev;
    }

    this.size--;
  }

  display() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    return result;
  }

  displayReverse() {
    const result = [];
    let current = this.tail;
    while (current) {
      result.push(current.data);
      current = current.prev;
    }
    return result;
  }
}

登录后复制

优势体现在可以从尾部快速插入/删除，也可以反向遍历。