数组和链表

1. 介绍

数组（Array） 用于存储固定数量的相同类型的元素。元素在内存中是连续存储的，通过索引访问，提供了高效的随机访问能力和简单的实现，适用于需要快速访问且不需要频繁动态调整大小的场景。

链表（Linked List） 每个节点包含数据和指向下一个节点的指针（在双链表中，还包含指向前一个节点的指针）。节点在内存中不一定是连续的，提供了灵活的大小调整和高效的插入删除操作，适用于动态数据集合和需要频繁插入删除的情况，但访问速度较慢且内存开销较大。

1.1 内存结构

数组：内存连续性，数组的元素在内存中是连续存储的，地址计算简单且快速；固定大小，数组的大小在创建时定义，之后无法调整（动态数组可以在运行过程中动态扩容）。
链表：内存分散，链表的节点在内存中可能是非连续的，每个节点包含指向其他节点的指针；动态大小，链表的大小可以动态调整，可以随时增加或删除节点。

1.2 访问时间

数组：随机访问，支持常数时间复杂度 O(1) 的随机访问。可以通过索引直接访问任何元素，效率高。
链表：顺序访问，访问某个元素时需要从头节点开始逐个遍历，时间复杂度为 O(n)。不支持直接随机访问。

1.3 插入和删除

数组：插入，在数组的中间或开头插入元素时，需要移动后续的元素，时间复杂度为 O(n)。在数组末尾插入元素通常为 O(1)，但前提是数组有足够的空间。删除，在数组的中间或开头删除元素时，需要移动后续的元素，时间复杂度为 O(n)。在末尾删除元素通常为 O(1)。
链表：插入，在链表中插入元素时，只需调整指针，时间复杂度为 O(1)（在已知位置的情况下），在链表的末尾插入元素也可以在常数时间内完成（假设已知末尾）。删除，在链表中删除元素时，只需调整指针，时间复杂度为 O(1)（在已知位置的情况下）。

1.4 内存使用

数组：空间效率，数组的内存使用是连续的，额外内存开销较少。每个元素占用固定的内存空间。
链表：空间开销，每个节点需要额外的内存来存储指针（在双链表中，还需要存储前驱指针），因此内存开销较大。

1.5 性能

数组：优点，在随机访问和遍历方面表现优异，因为元素存储在连续内存中，访问速度快。缺点，插入和删除操作效率较低，尤其是在数组中间部分。
链表：优点，插入和删除操作效率较高，尤其在链表的开头或中间部分。大小动态调整灵活。缺点，访问操作较慢，需要顺序遍历节点，额外内存开销较大。

1.6 适用场景

数组：适合需要频繁随机访问的应用，如静态数据集合、缓存数据、固定大小的数据集合。
链表：适合需要频繁插入和删除的应用，如动态数据集合、栈和队列的实现、数据量动态变化的情况。

1.7 数组 vs 链表

特性	数组	链表
存储结构	连续内存空间	不连续的内存空间，每个元素都有指针指向下一个元素
访问速度	支持快速随机访问，时间复杂度为 O(1)	随机访问较慢，时间复杂度为 O(n)
插入和删除	插入和删除操作较慢，时间复杂度为 O(n)	插入和删除操作较快，时间复杂度为 O(1)（在已知位置时）
内存分配	需要在创建时指定大小，大小不可动态调整	动态分配内存，大小可以在运行时调整
空间效率	可能浪费内存（如果未使用的空间较多）	只使用实际存储的数据，没有预留空间
遍历效率	遍历速度快，缓存友好	遍历速度较慢，可能导致缓存不友好
实现复杂性	实现简单	实现复杂，需要管理指针
使用场景	适合需要快速访问和较少插入删除的场景	适合频繁插入和删除的场景

2. 代码案例

2.1 数组实现 (Array)

// ======================数组==========================
class Array {
    private size: number; // 数组的大小
    private array: number[]; // 存储数组元素的容器

    // 构造函数：初始化数组
    constructor(size: number) {
        this.size = size;
        this.array = new Array(size).fill(-1); // 使用 -1 初始化数组
    }

    // 设置数组指定索引位置的值
    set(index: number, value: number): void {
        if (index >= 0 && index < this.size) {
            this.array[index] = value;
        } else {
            throw new Error("索引超出范围");
        }
    }

    // 获取数组指定索引位置的值
    get(index: number): number {
        if (index >= 0 && index < this.size) {
            return this.array[index];
        } else {
            throw new Error("索引超出范围");
        }
    }

    // 删除数组指定索引位置的值
    deleteAt(index: number): void {
        if (index >= 0 && index < this.size) {
            this.array[index] = -1; // 使用 -1 表示删除
        } else {
            throw new Error("索引超出范围");
        }
    }

    // 返回数组的字符串表示
    toString(): string {
        return `[${this.array.join(", ")}]`;
    }
}

2.2 单链表实现 (Singly Linked List)

// ======================单链表==========================
class Node {
    data: number;  // 节点的数据
    next: Node | null; // 指向下一个节点的指针

    constructor(data: number) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    private head: Node | null;  // 链表的头节点

    constructor() {
        this.head = null;
    }

    // 向链表的末尾添加一个新节点
    append(data: number): void {
        const newNode = new Node(data);
        if (this.head === null) {
            this.head = newNode; // 如果链表为空，新节点成为头节点
        } else {
            let last = this.head;
            while (last.next !== null) {
                last = last.next;  // 遍历到链表的最后一个节点
            }
            last.next = newNode;  // 将新节点链接到链表的末尾
        }
    }

    // 删除链表中第一个匹配指定数据的节点
    deleteNode(data: number): void {
        let current = this.head;
        if (current === null) return;

        // 如果要删除的是头节点
        if (current.data === data) {
            this.head = current.next;
            return;
        }

        let prev: Node | null = null;
        while (current !== null && current.data !== data) {
            prev = current;
            current = current.next;
        }

        // 如果找到要删除的节点
        if (current !== null) {
            if (prev !== null) {
                prev.next = current.next;  // 跳过要删除的节点
            }
        }
    }

    // 查找链表中第一个匹配指定数据的节点，并返回节点数据
    get(data: number): number | null {
        let current = this.head;
        while (current !== null) {
            if (current.data === data) {
                return current.data;
            }
            current = current.next;
        }
        return null;  // 未找到数据
    }

    // 打印链表的所有节点
    printList(): void {
        let current = this.head;
        if (current === null) {
            console.log("链表为空");
            return;
        }

        while (current !== null) {
            process.stdout.write(current.data + " -> ");
            current = current.next;
        }
        console.log("None");
    }
}

2.3 双向链表实现 (Doubly Linked List)

// ======================双链表==========================
class DoublyNode {
    data: number;         // 节点的数据
    next: DoublyNode | null;  // 指向下一个节点的指针
    prev: DoublyNode | null;  // 指向前一个节点的指针

    constructor(data: number) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    private head: DoublyNode | null; // 链表的头节点

    constructor() {
        this.head = null;
    }

    // 向双向链表的末尾添加一个新节点
    append(data: number): void {
        const newNode = new DoublyNode(data);
        if (this.head === null) {
            this.head = newNode;
            this.head.next = this.head;
            this.head.prev = this.head;
        } else {
            const last = this.head.prev;
            last!.next = newNode;
            newNode.prev = last;
            newNode.next = this.head;
            this.head.prev = newNode;
        }
    }

    // 删除双向链表中第一个匹配指定数据的节点
    deleteNode(data: number): void {
        if (this.head === null) return;

        let current = this.head;
        do {
            if (current.data === data) {
                if (current === this.head) {
                    if (current.next === current) {
                        this.head = null;
                    } else {
                        this.head = current.next;
                        this.head.prev = current.prev;
                        current.prev!.next = this.head;
                    }
                } else {
                    current.prev!.next = current.next;
                    current.next!.prev = current.prev;
                }
                return;
            }
            current = current.next!;
        } while (current !== this.head);
    }

    // 查找双向链表中第一个匹配指定数据的节点，并返回节点数据
    get(data: number): number | null {
        if (this.head === null) return null;

        let current = this.head;
        do {
            if (current.data === data) {
                return current.data;
            }
            current = current.next!;
        } while (current !== this.head);

        return null;
    }

    // 打印双向链表的所有节点
    printList(): void {
        if (this.head === null) {
            console.log("链表为空");
            return;
        }

        let current = this.head;
        do {
            process.stdout.write(current.data + " <-> ");
            current = current.next!;
        } while (current !== this.head);
        console.log("(head)");
    }
}

2.4 动态数组实现 (Dynamic Array)

// ======================动态数组==========================
class DynamicArray {
    private array: number[]; // 存储数组元素的容器

    constructor() {
        this.array = [];
    }

    // 向动态数组的末尾添加一个新元素
    append(value: number): void {
        this.array.push(value);
    }

    // 获取动态数组指定索引位置的值
    get(index: number): number {
        if (index >= 0 && index < this.array.length) {
            return this.array[index];
        } else {
            throw new Error("索引超出范围");
        }
    }

    // 删除动态数组指定索引位置的元素
    deleteAt(index: number): void {
        if (index >= 0 && index < this.array.length) {
            this.array.splice(index, 1);
        } else {
            throw new Error("索引超出范围");
        }
    }

    // 返回动态数组的字符串表示
    toString(): string {
        return `[${this.array.join(", ")}]`;
    }
}

2.5 示例使用 (Main Function)

// 示例使用
const main = () => {
    // 数组示例
    const arr = new Array(5); // 创建一个大小为 5 的数组
    arr.set(0, 10);
    arr.set(1, 20);
    console.log("数组:", arr.toString());
    console.log("索引 1 处的值:", arr.get(1));
    arr.deleteAt(1);
    console.log("删除后的数组:", arr.toString());

    // 单链表示例
    const sll = new SinglyLinkedList();
    sll.append(1);
    sll.append(2);
    sll.append(3);
    console.log("单链表:");
    sll.printList();
    console.log("查找值为 2 的节点:", sll.get(2));
    sll.deleteNode(2);
    console.log("删除后的单链表:");
    sll.printList();

    // 双向链表示例
    const dcll = new DoublyLinkedList();
    dcll.append(10);
    dcll.append(20);
    dcll.append(30);
    console.log("双向链表:");
    dcll.printList();
    console.log("查找值为 20 的节点:", dcll.get(20));
    dcll.deleteNode(20);
    console.log("删除后的双向链表:");
    dcll.printList();

    // 动态数组示例
    const da = new DynamicArray();
    da.append(5);
    da.append(15);
    da.append(25);
    console.log("动态数组:", da.toString());
    console.log("索引 1 处的值:", da.get(1));
    da.deleteAt(1);
    console.log("删除后的动态数组:", da.toString());
};

main();

解释：

数组 (Array)：用 Array 类型表示数组，提供 set，get，deleteAt 方法。
单链表 (SinglyLinkedList)：使用 Node 类实现单链表，提供 append、deleteNode、get 和 printList 方法。
双向链表 (DoublyLinkedList)：使用 DoublyNode 类实现双向链表，提供 append、deleteNode、get 和 printList 方法。
动态数组 (DynamicArray)：用 JavaScript 内建的 Array 类模拟动态数组，提供 append，get，deleteAt 和 toString 方法。