数组与链表

数组（Array）

特点

• 连续存储 - 内存中连续存放
• 随机访问 - 通过索引 O(1) 访问
• 固定大小 - 扩容需要重新分配

基本操作

// Java
int[] arr = new int[10];
int[] nums = {1, 2, 3, 4, 5};

// 访问 - O(1)
int x = nums[2];  // 3

// 插入 - O(n)
// 需要移动后续元素

// 删除 - O(n)
// 需要移动后续元素

经典题目

• 两数之和
• 三数之和
• 滑动窗口最大值
• 接雨水

链表（Linked List）

单链表

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

操作

// 遍历
ListNode cur = head;
while (cur != null) {
    System.out.println(cur.val);
    cur = cur.next;
}

// 反转
ListNode prev = null, cur = head;
while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

经典题目

• 反转链表
• 合并两个有序链表
• 环形链表检测
• LRU 缓存实现

数组 vs 链表

操作	数组	链表
访问	O(1)	O(n)
插入/删除	O(n)	O(1)
内存	连续	分散
缓存友好	好	差