登录
首页 >  文章 >  前端

链表与双向链表结构详解

时间：2026-03-19 23:03:35 252浏览 收藏

本文深入解析了链表与双向链表这两种基础而强大的动态数据结构，清晰阐述了它们通过节点与指针构建非连续内存布局的核心思想，对比了单向链表的简洁性与双向链表支持前后遍历、高效尾部操作的灵活性，并辅以直观的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;
  }
}

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

链表 vs 数组

链表适合频繁插入和删除的场景，因为不需要移动大量元素。但访问某个位置的元素时，必须从头开始遍历，时间复杂度为 O(n)，而数组可以通过索引直接访问。

常见应用场景：

  • 实现栈和队列
  • 浏览器历史记录（前进/后退）
  • 音乐播放列表的上一首/下一首
  • 需要动态增删的数据集合

基本上就这些。链表理解起来不难，关键在于指针操作的细节处理，尤其是边界情况，比如头尾节点的更新。双向链表虽然逻辑稍复杂，但提供了更大的灵活性。实际开发中，虽然 JavaScript 内置了数组，但在特定算法题或自定义数据结构中，链表仍然非常有用。

到这里，我们也就讲完了《链表与双向链表结构详解》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！

资料下载
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>