跳到主要内容

数组与链表

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


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. 比较数组和链表在插入、删除和访问操作中的性能差异。

资源