二、数组：最基础的数据结构

数组是最简单、最常用的数据结构，理解数组是学习其他数据结构的基础。

2.1 数组的本质
数组是在连续内存空间中存储的相同类型元素的集合。这个特性决定了它的优缺点：

✅ 优点：通过索引访问元素是 O(1) 常数时间（直接计算内存地址）

❌ 缺点：插入和删除需要移动大量元素，最坏 O(n)

// 内存布局示意
// 假设每个整数占 4 字节，数组起始地址是 1000
let arr = [10, 20, 30, 40, 50];

// 元素地址计算：
// arr[0] 地址 = 1000
// arr[1] 地址 = 1000 + 1×4 = 1004
// arr[2] 地址 = 1000 + 2×4 = 1008
// arr[i] 地址 = 起始地址 + i × 元素大小

2.2 数组的基本操作及复杂度

// 1. 随机访问 - O(1)
function getElement(arr, index) {
    return arr[index];  // 直接计算地址
}

// 2. 末尾插入 - O(1)（平均）
function append(arr, element) {
    arr[arr.length] = element;  // 或 arr.push(element)
}

// 3. 开头插入 - O(n)
function prepend(arr, element) {
    // 需要将所有元素后移一位
    for (let i = arr.length; i > 0; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = element;
}
// 执行过程：[1,2,3] 开头插入 0
// 第1步：移动3 → [1,2,3,3]
// 第2步：移动2 → [1,2,2,3]
// 第3步：移动1 → [1,1,2,3]
// 第4步：放入0 → [0,1,2,3]

// 4. 指定位置插入 - O(n)
function insertAt(arr, index, element) {
    // 将 index 及之后的元素后移
    for (let i = arr.length; i > index; i--) {
        arr[i] = arr[i - 1];
    }
    arr[index] = element;
}

// 5. 删除末尾元素 - O(1)
function pop(arr) {
    const element = arr[arr.length - 1];
    arr.length = arr.length - 1;  // 或 arr.pop()
    return element;
}

// 6. 删除指定位置 - O(n)
function deleteAt(arr, index) {
    const element = arr[index];
    // 将 index 之后的元素前移
    for (let i = index; i < arr.length - 1; i++) {
        arr[i] = arr[i + 1];
    }
    arr.length = arr.length - 1;
    return element;
}
// 执行过程：[1,2,3,4] 删除索引 1（值为2）
// 第1步：移动3 → [1,3,3,4]
// 第2步：移动4 → [1,3,4,4]
// 第3步：长度减1 → [1,3,4]

2.3 实战案例：数组去重

// 方法1：使用 Set（最简单）
function uniqueWithSet(arr) {
    return [...new Set(arr)];
}
// 时间复杂度：O(n)，空间复杂度：O(n)

// 方法2：双重循环（效率低，但理解原理）
function uniqueWithLoop(arr) {
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        let isDuplicate = false;
        for (let j = 0; j < result.length; j++) {
            if (arr[i] === result[j]) {
                isDuplicate = true;
                break;
            }
        }
        if (!isDuplicate) {
            result.push(arr[i]);
        }
    }
    return result;
}
// 时间复杂度：O(n²)，空间复杂度：O(n)

// 方法3：先排序再去重
function uniqueWithSort(arr) {
    if (arr.length === 0) return [];
    const sorted = [...arr].sort((a, b) => a - b);
    const result = [sorted[0]];
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i] !== sorted[i - 1]) {
            result.push(sorted[i]);
        }
    }
    return result;
}
// 时间复杂度：O(n log n)（排序），空间复杂度：O(n)

// 测试
const testArr = [1, 2, 2, 3, 3, 4, 1, 5];
console.log(uniqueWithSet(testArr));    // [1,2,3,4,5]
console.log(uniqueWithLoop(testArr));   // [1,2,3,4,5]
console.log(uniqueWithSort(testArr));   // [1,2,3,4,5]

2.4 实战案例：两数之和
这是 LeetCode 第一题，也是面试高频题。

// 题目：给定一个整数数组 nums 和一个目标值 target
// 请找出和为目标值的两个整数，返回它们的索引

// 方法1：暴力枚举（O(n²)）
function twoSumBruteForce(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

// 方法2：哈希表（O(n)）- 更优
function twoSumHash(nums, target) {
    const map = new Map();  // 存储 {值: 索引}

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];  // 需要的另一个数

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);  // 将当前数存入哈希表
    }
    return [];
}

// 执行过程示例：
// nums = [2, 7, 11, 15], target = 9
//
// i=0, num=2, complement=7, map={} → 没有7，存入 {2:0}
// i=1, num=7, complement=2, map={2:0} → 找到7！返回 [0,1]

console.log(twoSumHash([2, 7, 11, 15], 9));  // [0, 1]

三、链表：动态的数据结构

链表解决了数组插入/删除需要移动元素的缺点，但牺牲了随机访问的能力。
3.1 链表的本质
链表由一系列节点组成，每个节点包含数据域和指针域（指向下一个节点）。

// 节点定义
class ListNode {
    constructor(val, next = null) {
        this.val = val;      // 存储的数据
        this.next = next;    // 指向下一个节点的指针
    }
}

// 创建一个简单的链表：1 → 2 → 3 → null
const node3 = new ListNode(3);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);

内存布局：节点在内存中不连续，通过指针连接。

内存地址:     0x1000        0x2000        0x3000
         ┌──────────┐   ┌──────────┐   ┌──────────┐
         │ val: 1   │   │ val: 2   │   │ val: 3   │
         │ next:0x2000│ → │ next:0x3000│ → │ next:null│
         └──────────┘   └──────────┘   └──────────┘

3.2 链表的优缺点

3.3 链表的完整实现

class LinkedList {
    constructor() {
        this.head = null;   // 头节点
        this.tail = null;   // 尾节点（可选，优化尾部操作）
        this.length = 0;    // 链表长度
    }

    // 尾部添加 - O(1)
    append(val) {
        const newNode = new ListNode(val);

        if (this.head === null) {
            // 空链表
            this.head = newNode;
            this.tail = newNode;
        } else {
            // 当前尾节点的 next 指向新节点
            this.tail.next = newNode;
            // 更新尾节点
            this.tail = newNode;
        }

        this.length++;
        return this;
    }

    // 头部添加 - O(1)
    prepend(val) {
        const newNode = new ListNode(val);

        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }

        this.length++;
        return this;
    }

    // 删除指定值的节点
    delete(val) {
        if (this.head === null) return null;

        // 如果删除的是头节点
        if (this.head.val === val) {
            this.head = this.head.next;
            // 如果链表只有一个节点，尾节点也需要处理
            if (this.head === null) {
                this.tail = null;
            }
            this.length--;
            return true;
        }

        // 遍历找到要删除的节点
        let current = this.head;
        while (current.next !== null) {
            if (current.next.val === val) {
                // 跳过要删除的节点
                current.next = current.next.next;
                // 如果删除的是尾节点，更新 tail
                if (current.next === null) {
                    this.tail = current;
                }
                this.length--;
                return true;
            }
            current = current.next;
        }

        return false;  // 未找到
    }

    // 查找指定值的节点
    find(val) {
        let current = this.head;
        let index = 0;

        while (current !== null) {
            if (current.val === val) {
                return { node: current, index };
            }
            current = current.next;
            index++;
        }

        return null;
    }

    // 反转链表（经典面试题）
    reverse() {
        let prev = null;
        let current = this.head;

        while (current !== null) {
            const nextTemp = current.next;  // 保存下一个节点
            current.next = prev;             // 反转指针
            prev = current;                  // 移动 prev
            current = nextTemp;              // 移动 current
        }

        // 交换 head 和 tail
        this.tail = this.head;
        this.head = prev;

        return this;
    }

    // 打印链表
    print() {
        const values = [];
        let current = this.head;

        while (current !== null) {
            values.push(current.val);
            current = current.next;
        }

        console.log(values.join(' → '));
    }
}

// 使用示例
const list = new LinkedList();
list.append(1).append(2).append(3).prepend(0);
list.print();  // 0 → 1 → 2 → 3

list.reverse();
list.print();  // 3 → 2 → 1 → 0

console.log(list.find(2));  // { node: ListNode { val: 2, next: ... }, index: 1 }

3.4 反转链表的详细图解
反转链表是面试最高频的链表题目，我们详细拆解执行过程：

// 输入：1 → 2 → 3 → null
// 目标：null ← 1 ← 2 ← 3

// 初始化
let prev = null;
let current = head;  // current 指向节点1

// 迭代1：处理节点1
// 保存 next = current.next = 节点2
// current.next = prev → 1 → null
// prev = current = 节点1
// current = next = 节点2
// 状态：null ← 1    2 → 3 → null

// 迭代2：处理节点2
// next = current.next = 节点3
// current.next = prev → 2 → 1
// prev = current = 节点2
// current = next = 节点3
// 状态：null ← 1 ← 2    3 → null

// 迭代3：处理节点3
// next = current.next = null
// current.next = prev → 3 → 2
// prev = current = 节点3
// current = next = null
// 状态：null ← 1 ← 2 ← 3

// 循环结束，head = prev = 节点3
// 最终：3 → 2 → 1 → null

3.5 环形链表检测（Floyd 判圈算法）

// 判断链表是否有环
function hasCycle(head) {
    if (head === null || head.next === null) {
        return false;
    }

    // 快慢指针：快指针每次走两步，慢指针每次走一步
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;       // 慢指针走1步
        fast = fast.next.next;  // 快指针走2步

        if (slow === fast) {
            return true;  // 相遇，说明有环
        }
    }

    return false;  // 快指针到达末尾，无环
}

// 创建有环的链表
function createCycleList() {
    const node1 = new ListNode(1);
    const node2 = new ListNode(2);
    const node3 = new ListNode(3);
    const node4 = new ListNode(4);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node2;  // 形成环：4 → 2

    return node1;
}

console.log(hasCycle(createCycleList()));  // true

原理：想象两个人在圆形跑道上跑步，一个快一个慢，他们一定会相遇。
来源：
https://xcfsr.cn/