当前位置：首页 > 文章列表 > 文章 > 前端 > 链表与双向链表结构详解

链表与双向链表结构详解

2026-03-19 23:03:35 0浏览收藏

本文深入解析了链表与双向链表这两种基础而强大的动态数据结构，清晰阐述了它们通过节点与指针构建非连续内存布局的核心思想，对比了单向链表的简洁性与双向链表支持前后遍历、高效尾部操作的灵活性，并辅以直观的JavaScript代码实现和典型应用场景（如浏览器历史、播放列表、栈队列），帮助读者不仅理解“是什么”和“怎么写”，更掌握“为何用”——在频繁增删、无需随机访问的动态数据管理中，链表远比数组更高效实用。

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

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

链表的基本结构

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

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

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

基本操作包括：

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

实现单向链表

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

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），每个节点既能指向下一个节点，也能指向前一个节点。这种结构支持从任意方向遍历，提高了某些操作的效率。

节点定义如下：

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;
  }
}

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