编辑“︁数组与链表”︁

= 数组与链表 =

'''数组'''和'''链表'''是计算机科学中最基础且最重要的两种数据结构，它们用于存储和组织数据，但在实现方式、性能特性和适用场景上有显著差异。理解它们的区别对编程和算法设计至关重要。

== 基本概念 ==

=== 数组（Array） ===
数组是一种'''线性数据结构'''，由一组'''连续的内存空间'''组成，用于存储相同类型的元素。数组的元素可以通过'''索引'''（通常从0开始）直接访问。

'''特点：'''
* 固定大小（静态数组）或可变大小（动态数组）
* 内存连续分配
* 随机访问时间复杂度：O(1)
* 插入/删除时间复杂度：O(n)（最坏情况）

=== 链表（Linked List） ===
链表是一种'''线性数据结构'''，由一系列'''节点'''组成，每个节点包含数据和指向下一个节点的指针。链表的内存分配是'''非连续'''的。

'''特点：'''
* 动态大小
* 内存非连续分配
* 随机访问时间复杂度：O(n)
* 插入/删除时间复杂度：O(1)（已知位置时）

== 详细比较 ==

{| class="wikitable"
|+ 数组与链表对比
! 特性 !! 数组 !! 链表
|-
| '''内存分配''' || 连续 || 非连续
|-
| '''大小灵活性''' || 固定（静态数组）<br>可变（动态数组） || 动态增长
|-
| '''访问方式''' || 随机访问（O(1)） || 顺序访问（O(n)）
|-
| '''插入/删除效率''' || O(n)（需要移动元素） || O(1)（已知位置）
|-
| '''缓存友好性''' || 好（空间局部性） || 差
|-
| '''内存开销''' || 仅存储数据 || 额外存储指针
|}

== 代码实现示例 ==

=== 数组示例 ===
<syntaxhighlight lang="python">
# 创建数组
arr = [10, 20, 30, 40, 50]

# 访问元素
print(arr[2])  # 输出: 30

# 修改元素
arr[1] = 25
print(arr)  # 输出: [10, 25, 30, 40, 50]

# 插入元素（需要移动后续元素）
arr.insert(2, 35)
print(arr)  # 输出: [10, 25, 35, 30, 40, 50]

# 删除元素（需要移动后续元素）
arr.pop(3)
print(arr)  # 输出: [10, 25, 35, 40, 50]
</syntaxhighlight>

=== 链表示例 ===
<syntaxhighlight lang="python">
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
    
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 使用链表
llist = LinkedList()
llist.append(10)
llist.append(20)
llist.append(30)
llist.display()  # 输出: 10 -> 20 -> 30 -> None

# 在中间插入节点
new_node = Node(25)
new_node.next = llist.head.next
llist.head.next = new_node
llist.display()  # 输出: 10 -> 25 -> 20 -> 30 -> None

# 删除节点
llist.head.next = llist.head.next.next
llist.display()  # 输出: 10 -> 20 -> 30 -> None
</syntaxhighlight>

== 内存结构可视化 ==

<mermaid>
graph LR
    subgraph 数组
    A[0: 10] --> B[1: 20] --> C[2: 30] --> D[3: 40] --> E[4: 50]
    end

    subgraph 链表
    F[10|next] --> G[20|next] --> H[30|next] --> I[None]
    end
</mermaid>

== 数学分析 ==

对于长度为<math>n</math>的数组和链表：

* '''访问操作'''：
** 数组：<math>T(n) = 1</math>（常数时间）
** 链表：<math>T(n) = n/2 \approx O(n)</math>（平均情况）

* '''插入操作'''：
** 数组：<math>T(n) = n</math>（最坏情况）
** 链表：<math>T(n) = 1</math>（已知位置）

== 实际应用场景 ==

'''数组适用场景：'''
* 需要频繁随机访问元素
* 数据量已知且固定
* 需要缓存友好的数据结构
* 数值计算、图像处理等高性能场景

'''链表适用场景：'''
* 需要频繁插入/删除操作
* 数据量动态变化
* 实现栈、队列、哈希表等高级数据结构
* 内存分配不确定的情况

=== 典型案例 ===
1. '''数组应用'''：图像处理中像素矩阵的存储
2. '''链表应用'''：浏览器历史记录（前进/后退功能实现）
3. '''混合应用'''：Java的ArrayList（动态数组）和LinkedList

== 高级话题 ==

=== 动态数组 ===
动态数组（如Python的list）在底层使用数组实现，但能自动扩容。当空间不足时，会分配更大的数组（通常1.5-2倍）并复制原有数据。

=== 双向链表 ===
双向链表每个节点包含指向前驱和后继的指针，支持双向遍历：

<mermaid>
graph LR
    A[prev|10|next] <--> B[prev|20|next] <--> C[prev|30|next]
</mermaid>

=== 循环链表 ===
链表尾节点指向头节点，形成循环结构，适用于轮询调度等场景。

== 常见面试问题 ==

1. 如何实现一个动态数组？
2. 反转单链表的算法是什么？
3. 检测链表是否有环的方法？
4. 合并两个有序链表的最优方法？
5. 数组和链表在内存管理上的差异？

== 总结 ==

数组和链表各有优劣，选择哪种数据结构取决于具体应用场景：
* '''数组'''适合读多写少、需要快速随机访问的场景
* '''链表'''适合频繁插入删除、数据量变化大的场景

理解它们的底层实现和性能特征，能帮助开发者做出更合理的设计决策。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:数据结构基础]]