数组与链表[编辑 | 编辑源代码]

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

基本概念[编辑 | 编辑源代码]

数组（Array）[编辑 | 编辑源代码]

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

特点：

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

链表（Linked List）[编辑 | 编辑源代码]

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

特点：

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

详细比较[编辑 | 编辑源代码]

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

代码实现示例[编辑 | 编辑源代码]

数组示例[编辑 | 编辑源代码]

# 创建数组
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]

链表示例[编辑 | 编辑源代码]

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