电脑编程基础17：深入理解数据结构——数组与链表211

大家好，欢迎来到“电脑编程基础”系列教程的第十七讲！在之前的课程中，我们学习了编程的基础语法、控制流程以及一些基本的算法。从本节课开始，我们将深入探讨数据结构，这是编程中至关重要的一部分，它直接影响着程序的效率和可维护性。本节课我们将重点讲解两种最基础、也是最常用的数据结构：数组和链表。

一、数组 (Array)

数组是一种线性数据结构，它使用连续的内存空间来存储相同类型的数据元素。每个元素可以通过其索引（通常从0开始）来访问。数组的特点是：访问速度快，因为元素在内存中是连续存储的，可以直接通过地址计算访问；但是，插入和删除元素的效率较低，因为需要移动其他元素来腾出或填补空间。数组的大小通常在创建时就固定了，如果需要存储更多元素，则需要重新分配更大的内存空间。

数组的优点：
随机访问： 可以通过索引直接访问任意元素，时间复杂度为O(1)。
内存连续： 元素在内存中连续存储，有利于缓存利用，提高访问效率。
实现简单： 数组的实现相对简单，容易理解和使用。

数组的缺点：
大小固定： 在创建时需要指定大小，如果大小不够，需要重新分配内存，效率较低。
插入和删除效率低： 插入或删除元素需要移动其他元素，时间复杂度为O(n)。
内存浪费： 如果数组没有完全使用，会造成内存浪费。

示例代码 (Python):
my_array = [10, 20, 30, 40, 50]
print(my_array[0]) # 输出 10
(60) # 在数组末尾添加元素
print(my_array) # 输出 [10, 20, 30, 40, 50, 60]
(2, 25) # 在索引2处插入元素25
print(my_array) # 输出 [10, 20, 25, 30, 40, 50, 60]
del my_array[1] # 删除索引1处的元素
print(my_array) # 输出 [10, 25, 30, 40, 50, 60]

二、链表 (Linked List)

链表是一种线性数据结构，它不像数组那样使用连续的内存空间存储元素，而是每个元素都存储了指向下一个元素的指针。链表可以分为单链表、双向链表和循环链表等几种类型。

单链表：每个节点包含数据域和指向下一个节点的指针域。链表的第一个节点称为头节点，最后一个节点的指针域为NULL。

双向链表：每个节点包含数据域、指向下一个节点的指针域和指向前一个节点的指针域，可以双向遍历。

循环链表：链表的最后一个节点的指针域指向头节点，形成一个环。

链表的优点：
动态大小： 链表的大小可以动态调整，无需预先指定大小。
插入和删除效率高： 插入或删除元素只需要修改指针，时间复杂度为O(1)，但需要找到插入或删除的位置。
内存利用率高： 不会造成内存浪费。

链表的缺点：
随机访问效率低： 无法通过索引直接访问元素，需要从头节点开始遍历，时间复杂度为O(n)。
内存消耗： 每个节点都需要额外的内存空间存储指针。
实现复杂： 链表的实现比数组更复杂。

示例代码 (Python - 单链表，简化版):
class Node:
def __init__(self, data):
= data
= None
class LinkedList:
def __init__(self):
= None
def append(self, data):
new_node = Node(data)
if not :
= new_node
return
current =
while :
current =
= new_node
my_list = LinkedList()
(10)
(20)
(30)
current =
while current:
print()
current =