JavaScript 数据结构——链表的实现与应用

在计算机科学中，数据结构是组织和存储数据的方式，不同的数据结构适用于不同的应用场景。链表（Linked List）作为一种重要的数据结构，在很多场景中发挥着关键作用。与数组不同，链表的元素在内存中不是连续存储的，而是通过指针（引用）将各个节点连接起来。本文将详细介绍链表的基本概念、实现方式以及常见应用，并使用 JavaScript 语言进行代码示例。

目录#

  1. 链表的基本概念
  2. 链表的实现
    • 单向链表
    • 双向链表
  3. 链表的常见操作
    • 插入元素
    • 删除元素
    • 查找元素
  4. 链表的应用场景
  5. 总结与参考

1. 链表的基本概念#

链表是由一系列节点组成的数据结构，每个节点包含两个部分：数据和指向下一个节点的指针（引用）。链表可以分为单向链表和双向链表。

单向链表#

单向链表的每个节点只有一个指向下一个节点的指针，因此只能从链表的头部开始，依次访问每个节点。单向链表的最后一个节点的指针指向 null，表示链表的结束。

双向链表#

双向链表的每个节点除了有一个指向下一个节点的指针外，还有一个指向前一个节点的指针。这使得双向链表可以从链表的头部或尾部开始访问节点，增加了链表的灵活性。

2. 链表的实现#

单向链表的实现#

以下是使用 JavaScript 实现单向链表的代码示例：

// 定义链表节点类
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
 
// 定义单向链表类
class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
 
    // 在链表尾部添加节点
    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.length++;
    }
 
    // 打印链表元素
    print() {
        let current = this.head;
        const result = [];
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        console.log(result.join(' -> '));
    }
}
 
// 使用示例
const list = new SinglyLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.print(); // 输出: 1 -> 2 -> 3

双向链表的实现#

以下是使用 JavaScript 实现双向链表的代码示例：

// 定义双向链表节点类
class DoublyNode {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}
 
// 定义双向链表类
class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
 
    // 在链表尾部添加节点
    append(data) {
        const newNode = new DoublyNode(data);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.prev = this.tail;
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++;
    }
 
    // 打印链表元素
    print() {
        let current = this.head;
        const result = [];
        while (current) {
            result.push(current.data);
            current = current.next;
        }
        console.log(result.join(' <-> '));
    }
}
 
// 使用示例
const doublyList = new DoublyLinkedList();
doublyList.append(1);
doublyList.append(2);
doublyList.append(3);
doublyList.print(); // 输出: 1 <-> 2 <-> 3

3. 链表的常见操作#

插入元素#

在链表中插入元素通常有两种情况：在链表头部插入和在指定位置插入。

// 在单向链表头部插入元素
SinglyLinkedList.prototype.prepend = function(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
};
 
// 在单向链表指定位置插入元素
SinglyLinkedList.prototype.insertAt = function(position, data) {
    if (position < 0 || position > this.length) {
        return false;
    }
    const newNode = new Node(data);
    if (position === 0) {
        newNode.next = this.head;
        this.head = newNode;
    } else {
        let current = this.head;
        let previous = null;
        let index = 0;
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        newNode.next = current;
        previous.next = newNode;
    }
    this.length++;
    return true;
};

删除元素#

在链表中删除元素通常也有两种情况：删除链表头部元素和删除指定位置元素。

// 删除单向链表头部元素
SinglyLinkedList.prototype.removeHead = function() {
    if (!this.head) {
        return null;
    }
    const removed = this.head;
    this.head = this.head.next;
    this.length--;
    return removed.data;
};
 
// 删除单向链表指定位置元素
SinglyLinkedList.prototype.removeAt = function(position) {
    if (position < 0 || position >= this.length) {
        return null;
    }
    let current = this.head;
    if (position === 0) {
        this.head = current.next;
    } else {
        let previous = null;
        let index = 0;
        while (index < position) {
            previous = current;
            current = current.next;
            index++;
        }
        previous.next = current.next;
    }
    this.length--;
    return current.data;
};

查找元素#

在链表中查找元素通常是遍历链表，直到找到目标元素或遍历到链表末尾。

// 在单向链表中查找元素
SinglyLinkedList.prototype.search = function(data) {
    let current = this.head;
    while (current) {
        if (current.data === data) {
            return true;
        }
        current = current.next;
    }
    return false;
};

4. 链表的应用场景#

链表在很多场景中都有广泛的应用，以下是一些常见的应用场景：

实现栈和队列#

链表可以用来实现栈和队列。栈是一种后进先出（LIFO）的数据结构，队列是一种先进先出（FIFO）的数据结构。使用链表实现栈和队列可以避免数组在插入和删除元素时的性能问题。

内存管理#

在操作系统中，链表可以用来管理内存。当程序需要分配内存时，可以从链表中找到合适的空闲内存块；当程序释放内存时，可以将释放的内存块插入到链表中。

哈希表的冲突处理#

在哈希表中，当多个键映射到同一个哈希值时，会发生冲突。链表可以用来解决哈希表的冲突问题，将所有映射到同一个哈希值的键值对存储在一个链表中。

5. 总结#

链表是一种重要的数据结构，具有插入和删除元素效率高的优点，适用于需要频繁插入和删除元素的场景。本文介绍了链表的基本概念、实现方式、常见操作以及应用场景，并使用 JavaScript 语言进行了代码示例。通过学习链表，我们可以更好地理解数据结构的原理和应用，提高编程能力。

参考#

  • 《数据结构与算法分析——C 语言描述》
  • MDN Web Docs - JavaScript
  • GeeksforGeeks - Linked List Data Structure

希望本文对你理解链表的实现与应用有所帮助！如果你有任何疑问或建议，欢迎留言讨论。

2026-05