链表

链表（Linked List）是一种常见的数据结构，用于存储一系列的元素。与数组不同，链表中的元素并不在内存中连续存储，而是通过节点（Node）相互连接而成。每个节点包含两部分：数据（存储实际的元素值）和指针（指向下一个节点）。这种通过指针相互连接的方式使得链表可以动态地增加或删除元素，而不需要像数组一样进行元素的移动。

链表有多种类型，其中最常见的是单向链表和双向链表。

1. 单向链表（Singly Linked List）：每个节点包含一个指针，指向下一个节点。

2. 双向链表（Doubly Linked List）：每个节点包含两个指针，分别指向前一个节点和后一个节点。

链表的优点包括：

• 动态内存分配：链表可以动态地增加或删除节点，不需要预先分配固定大小的内存空间。

• 插入和删除效率高：在链表中插入或删除元素的时间复杂度为 O(1)，只需改变指针的指向，不需要移动其他元素。

• 灵活性：链表可以轻松地处理不同大小的数据，且不受内存大小限制。

但链表也有一些缺点：

• 随机访问效率低：链表的节点不是连续存储的，因此无法像数组那样通过下标直接访问元素，需要从头开始遍历到目标节点。

• 需要额外空间存储指针：每个节点都需要额外的指针来存储下一个（以及可能是前一个）节点的位置信息，因此占用的空间比数组更大。

总的来说，链表适用于需要频繁插入、删除操作而不需要频繁随机访问的场景。

js形式实现链表

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

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

    // 在链表尾部添加一个新节点
    add(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.size++;
    }

    // 在指定位置插入一个新节点
    insertAt(data, index) {
        if (index < 0 || index > this.size) {
            return false;
        }
        const newNode = new Node(data);
        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let current = this.head;
            let prev = null;
            let i = 0;
            while (i < index) {
                prev = current;
                current = current.next;
                i++;
            }
            newNode.next = current;
            prev.next = newNode;
        }
        this.size++;
        return true;
    }

    // 移除指定位置的节点
    removeFrom(index) {
        if (index < 0 || index >= this.size) {
            return null;
        }
        let current = this.head;
        let prev = null;
        let i = 0;
        if (index === 0) {
            this.head = current.next;
        } else {
            while (i < index) {
                prev = current;
                current = current.next;
                i++;
            }
            prev.next = current.next;
        }
        this.size--;
        return current.data;
    }

    // 根据值移除节点
    removeElement(data) {
        let current = this.head;
        let prev = null;
        while (current !== null) {
            if (current.data === data) {
                if (prev === null) {
                    this.head = current.next;
                } else {
                    prev.next = current.next;
                }
                this.size--;
                return current.data;
            }
            prev = current;
            current = current.next;
        }
        return null;
    }

    // 返回链表的长度
    sizeOfList() {
        return this.size;
    }

    // 打印链表中的所有节点
    printList() {
        let current = this.head;
        let str = '';
        while (current) {
            str += current.data + ' ';
            current = current.next;
        }
        console.log(str);
    }
}

// 使用示例
const ll = new LinkedList();
ll.add(1);
ll.add(2);
ll.add(3);
ll.insertAt(4, 2);
ll.printList(); // 输出: 1 2 4 3
console.log("Size of list:", ll.sizeOfList()); // 输出: Size of list: 4
ll.removeFrom(2);
ll.printList(); // 输出: 1 2 3
console.log("Size of list:", ll.sizeOfList()); // 输出: Size of list: 3
ll.removeElement(2);
ll.printList(); // 输出: 1 3
console.log("Size of list:", ll.sizeOfList()); // 输出: Size of list: 2