跳到主要内容

数组与链表

数组和链表是编程中最基础的数据结构之一。它们用于存储和操作数据集合，但在实现方式和性能上有着显著的区别。本文将详细介绍数组和链表的概念、特点、优缺点以及实际应用场景。

1. 什么是数组？​

数组是一种线性数据结构，用于存储相同类型的元素。数组中的元素在内存中是连续存储的，因此可以通过索引快速访问任意元素。

数组的特点：​

  • 固定大小：数组的大小在创建时确定，无法动态调整。
  • 随机访问：通过索引可以在 O(1) 时间复杂度内访问任意元素。
  • 内存连续：元素在内存中是连续存储的。

数组的代码示例​

以下是一个简单的数组示例：

python
# 创建一个包含 5 个元素的数组
arr = [10, 20, 30, 40, 50]

# 访问数组中的元素
print(arr[2])  # 输出：30

# 修改数组中的元素
arr[3] = 100
print(arr)  # 输出：[10, 20, 30, 100, 50]

2. 什么是链表？​

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的元素在内存中不是连续存储的。

链表的特点：​

  • 动态大小：链表的大小可以动态调整。
  • 顺序访问：访问链表中的元素需要从头节点开始遍历，时间复杂度为 O(n)。
  • 内存不连续：元素在内存中是分散存储的。

链表的代码示例​

以下是一个简单的单向链表实现：

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_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 创建一个链表并添加元素
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.print_list()  # 输出：10 -> 20 -> 30 -> None

3. 数组与链表的比较​

特性数组链表
内存分配连续内存非连续内存
大小固定大小动态大小
访问速度O(1)（随机访问）O(n)（顺序访问）
插入/删除O(n)（需要移动元素）O(1)（如果已知插入位置）
适用场景需要频繁访问元素需要频繁插入/删除元素

4. 实际应用场景​

数组的应用​

  • 存储固定大小的数据：例如存储一周的温度数据。
  • 实现矩阵或表格：例如二维数组可以表示棋盘或图像像素。

链表的应用​

  • 实现栈和队列：链表可以方便地实现动态大小的栈和队列。
  • 实现图或树的邻接表：链表适合存储稀疏图或树结构。

5. 总结​

数组和链表是两种基础但重要的数据结构，各有优缺点。数组适合需要快速访问元素的场景，而链表适合需要频繁插入和删除元素的场景。理解它们的区别和应用场景是学习更复杂数据结构的基础。

6. 附加资源与练习​

练习​

  1. 实现一个双向链表。
  2. 编写一个函数，将数组转换为链表。
  3. 比较数组和链表在插入、删除和访问操作中的性能差异。

资源​