数组与链表的本质区别

一、数组(Array)

1.1 定义与特性

数组是连续内存空间存储的相同类型数据集合。

int[] arr = new int[5];  // 分配连续5个int大小的内存

1.2 内存布局

索引:  [0]   [1]   [2]   [3]   [4]
      +----+----+----+----+----+
      | 10 | 20 | 30 | 40 | 50 |
      +----+----+----+----+----+
地址: 1000 1004 1008 1012 1016

通过基地址 + 偏移量直接计算元素位置：
[ \text{address}(i) = \text{base} + i \times \text{size} ]

1.3 时间复杂度

操作	时间复杂度	说明
随机访问	( O(1) )	通过索引直接计算地址
尾部插入	( O(1) )	已知长度时
中间插入	( O(n) )	需要移动后续元素
删除	( O(n) )	需要移动后续元素
查找	( O(n) )	无序数组

1.4 Java实现细节

// ArrayList底层是数组
transient Object[] elementData;

// 扩容机制：默认1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

二、链表(Linked List)

2.1 定义与特性

链表是非连续内存空间通过指针连接的数据结构。

2.2 节点结构

class ListNode {
    int val;           // 数据域
    ListNode next;     // 指针域
    
    ListNode(int val) {
        this.val = val;
    }
}

2.3 内存布局

节点A        节点B        节点C        节点D
+----+     +----+     +----+     +----+
| 10 | --> | 20 | --> | 30 | --> | 40 | --> null
|next|     |next|     |next|     |next|
+----+     +----+     +----+ +----+
  ↑
 head

节点分散存储，通过next指针串联。

2.4 时间复杂度

操作	时间复杂度	说明
随机访问	( O(n) )	必须从头遍历
头部插入/删除	( O(1) )	修改head指针
尾部插入	( O(n) )	单链表需遍历
给定节点删除	( O(1) )	已知前驱或后继
查找	( O(n) )	顺序遍历

2.5 常见链表类型

单链表

class SinglyLinkedList {
    ListNode head;
    // 只能单向遍历
}

双向链表

class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
}
// Java LinkedList底层实现

循环链表

// 尾节点指向头节点
last.next = head;

三、核心对比

维度	数组	链表
内存分配	连续，静态/动态	离散，动态
随机访问	( O(1) )	( O(n) )
插入删除	( O(n) )	( O(1) )
缓存友好性	高（局部性原理）	低（指针跳转）
内存占用	仅数据	数据 + 指针
扩容成本	高（需要搬迁）	低（只需改指针）
适用场景	频繁查询、索引访问	频繁增删、未知数量

四、实际应用选择

4.1 选择数组的场景

• 数据量固定或变化不大
• 需要频繁按索引访问
• 对内存局部性有要求（如数值计算）
• 实现简单，无指针开销

4.2 选择链表的场景

• 频繁在头部/中间插入删除
• 数据量动态变化大
• 实现队列、栈等数据结构
• 不需要随机访问

4.3 Java中的选择

// 频繁查询 → ArrayList
List<Integer> list = new ArrayList<>();

// 频繁增删 → LinkedList
List<Integer> list = new LinkedList<>();

// 但要注意：LinkedList实际 cache miss 高，小数据量不一定更快

五、经典面试题

5.1 反转链表

public ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

5.2 检测环

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

5.3 找中点

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

六、总结

数组和链表代表了两种基本的内存组织哲学：连续 vs 离散。数组用空间连续性换取 ( O(1) ) 访问，链表用指针灵活性换取 ( O(1) ) 增删。理解它们的本质区别，是掌握更复杂数据结构的基础。