js 链表结构体

在JavaScript中，链表并不是一种内置的数据结构，但我们可以通过对象和引用来模拟链表的行为。链表是一种基本的数据结构，由一系列节点组成，每个节点包含两部分：数据和指向下一个节点的引用。

链表的基础概念

节点（Node）：链表的基本单元，包含数据和指向下一个节点的指针。

链表（LinkedList）：由节点组成的数据结构，节点之间通过指针相互连接。

头节点（Head）：链表的第一个节点。

尾节点（Tail）：链表的最后一个节点，其指针通常指向null，表示链表的结束。

链表的优势

动态大小：链表的大小可以动态变化，不需要预先分配空间。
插入和删除效率高：在链表中插入或删除节点的时间复杂度为O(1)，前提是已知插入或删除的位置。
内存利用率高：链表只在需要时分配内存，不会浪费空间。

链表的类型

单向链表：每个节点只包含指向下一个节点的指针。
双向链表：每个节点包含指向前一个节点和下一个节点的指针。
循环链表：链表的尾节点指向头节点，形成一个环。

应用场景

实现其他数据结构：如栈、队列、图等。
需要频繁插入和删除操作的场景。

JavaScript中链表的实现示例

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

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

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

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

    // 在指定位置插入节点
    insertAt(data, index) {
        if (index < 0 || index > this.size) {
            return console.log("索引超出范围");
        }
        const node = new Node(data);
        let current = this.head;
        let previous;
        let count = 0;

        if (index === 0) {
            node.next = current;
            this.head = node;
        } else {
            while (count < index) {
                previous = current;
                current = current.next;
                count++;
            }
            node.next = current;
            previous.next = node;
        }
        this.size++;
    }

    // 移除指定位置的节点
    removeAt(index) {
        if (index < 0 || index >= this.size) {
            return console.log("索引超出范围");
        }
        let current = this.head;
        if (index === 0) {
            this.head = current.next;
        } else {
            let previous = null;
            let count = 0;
            while (count < index) {
                previous = current;
                current = current.next;
                count++;
            }
            previous.next = current.next;
        }
        this.size--;
        return current.data;
    }

    // 打印链表
    printList() {
        let current = this.head;
        let str = "";
        while (current) {
            str += current.data + " ";
            current = current.next;
        }
        console.log(str);
    }
}

// 使用示例
const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.insertAt(4, 1);
list.printList(); // 输出: 1 4 2 3
list.removeAt(2);
list.printList(); // 输出: 1 4 3