当前位置：首页 > article >正文

深入理解数据结构：数组、链表与列表

article 2024/12/25 21:38:39

概述：在编程的世界里，数据结构如同构建高楼大厦的基石，其中数组、链表和列表是最为常见且基础的数据结构。本文将深入探讨这三种数据结构的定义、基本概念、常用操作、常见类型、优点和局限性以及它们在实际编程中的应用。通过详细的解释和 Python 代码示例，帮助读者更好地理解和掌握这些重要的数据结构。

一、数组

定义与基本概念

数组是一种线性数据结构，它由一系列相同类型的元素组成，并按照一定的顺序存储在连续的内存空间中。可以通过索引快速访问数组中的元素，索引从 0 开始。
常用操作
访问元素

目录

一、数组

定义与基本概念

常用操作

访问元素

修改元素

插入元素

删除元素

常见类型

优点

局限性

应用

二、链表

定义与基本概念

常用操作

初始化及实现

访问元素

修改元素

插入元素

删除元素

常见类型

优点

局限性

应用

三、列表

定义与基本概念

常用操作

访问元素

修改元素

插入元素

删除元素

常见类型

优点

局限性

应用

数组VS链表VS列表

总结

结束语
通过索引可以在常数时间内访问数组中的特定元素。

# 创建一个整数数组
arr = [1, 2, 3, 4, 5]
# 访问索引为 2 的元素
print(arr[2])  # 输出 3

修改元素

可以直接通过索引修改数组中的元素值。

arr = [1, 2, 3, 4, 5]
# 修改索引为 2 的元素为 6
arr[2] = 6
print(arr)  # 输出 [1, 2, 6, 4, 5]

插入元素

在数组中插入元素可能需要移动其他元素以腾出空间，时间复杂度取决于插入的位置。

arr = [1, 2, 3, 4, 5]
# 在索引为 2 的位置插入元素 7
arr.insert(2, 7)
print(arr)  # 输出 [1, 2, 7, 3, 4, 5]

删除元素

删除元素也可能需要移动其他元素来填补空缺，时间复杂度同样取决于删除的位置。

arr = [1, 2, 3, 4, 5]
# 删除索引为 2 的元素
del arr[2]
print(arr)  # 输出 [1, 2, 4, 5]

常见类型

一维数组：存储一系列相同类型的元素，是最基本的数组类型。
多维数组：例如二维数组可以表示矩阵等结构。

优点

随机访问速度快，可以在常数时间内通过索引访问元素;
存储效率高，因为元素在内存中是连续存储的;
缓存局部性

局限性

大小固定，在创建数组时需要预先指定大小，一旦确定后难以更改。
插入和删除元素可能需要移动大量元素，时间复杂度较高。
插入与删除效率低
长度不可变
空间浪费

应用

随机访问
排序和搜索
查找表
机器学习--神经网络
数据结构实现--可通过组合实现其他数据结构

二、链表

定义与基本概念

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

常用操作

初始化及实现

可以通过定义节点类来实现链表。每个节点包含数据和指向下一个节点的指针。链表的初始化通常是创建一个空链表，即头节点为 None。
插入节点时，根据插入的位置，修改相应节点的指针，使其指向新节点，新节点再指向下一个节点。
删除节点时，找到要删除的节点，将其前一个节点的指针指向其后一个节点，从而将该节点从链表中移除。

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

# 创建链表
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3

访问元素

需要从头节点开始遍历链表，直到找到目标节点，时间复杂度为 O (n)。

# 访问元素
current = node1
while current:
    print(current.value)
    current = current.next

修改元素

找到目标节点后可以直接修改其数据值。

current = node1
while current.value!= 2:
    current = current.next
current.value = 6

插入元素

可以在链表的任意位置插入新节点，只需修改相应节点的指针，时间复杂度为 O (1)（在已知插入位置的情况下）。

new_node = ListNode(4)
new_node.next = node2
node1.next = new_node

删除元素

删除节点也只需修改相应节点的指针，时间复杂度为 O (1)（在已知删除位置的情况下）。

current = node1
while current.next.value!= 6:
    current = current.next
current.next = current.next.next

常见类型

单链表：每个节点只有一个指向下一个节点的指针。
双向链表：每个节点有两个指针，分别指向前一个节点和下一个节点。
循环链表：最后一个节点的指针指向头节点，形成一个循环。

优点

灵活扩展,，动态大小，可以根据需要随时添加或删除节点。
分散存储
插入和删除元素的时间复杂度低，不需要移动大量元素。

局限性

随机访问速度慢，需要遍历链表才能访问特定元素。
占用额外的内存空间来存储指针。

应用

实现栈和队列。
用于处理动态数据集合，如文件系统中的目录结构。

三、列表

定义与基本概念

在 Python 中，列表是一种可变序列数据类型，可以存储任意类型的元素。
列表内部实现可以是数组或链表，具体取决于实现方式和操作的特点。

常用操作

访问元素

可以通过索引快速访问列表中的元素。

lst = [1, 'two', 3.0] # 初始化
# 访问索引为 1 的元素
print(lst[1])  # 输出 'two'

修改元素

可以直接通过索引修改列表中的元素值。

lst = [1, 'two', 3.0]
# 修改索引为 1 的元素
lst[1] = 'two changed'
print(lst)  # 输出 [1, 'two changed', 3.0]

插入元素

可以在列表的任意位置插入元素，时间复杂度取决于插入的位置和列表的实现方式。

lst = [1, 'two', 3.0]
# 在索引为 1 的位置插入元素 'inserted'
lst.insert(1, 'inserted')
print(lst)  # 输出 [1, 'inserted', 'two', 3.0]

删除元素

可以删除列表中的特定元素，时间复杂度同样取决于删除的位置和实现方式。

lst = [1, 'two', 3.0]
# 删除元素 'two'
lst.remove('two')
print(lst)  # 输出 [1, 3.0]

常见类型

普通列表：可以存储任意类型的元素。
嵌套列表：列表中可以包含其他列表。

优点

灵活多变，可以存储不同类型的元素。
提供了丰富的内置方法，方便进行各种操作。

局限性

对于大量数据的操作，性能可能不如专门的数据结构。
存储不同类型的元素可能导致类型检查和处理的复杂性增加。

应用

存储和处理各种类型的数据集合。
作为函数的参数和返回值，传递一组数据。

数组VS链表VS列表

数据结构	初始化方式	随机访问	插入 / 删除（特定位置）	动态大小	存储方式
数组	指定大小创建	快（O (1)）	慢（可能需要移动大量元素）	固定大小	连续内存空间
链表	创建头节点为 None 的链表	慢（O (n)）	快（O (1)，已知位置）	动态大小	非连续内存空间，通过指针连接
列表	直接使用方括号创建	较快（取决于实现方式）	较快（取决于实现方式）	动态大小	内部实现可能是数组或链表

总结

数组、链表和列表是编程中非常基础且重要的数据结构。数组适合需要快速随机访问的场景，但大小固定且插入删除操作成本较高。链表则在动态大小和高效的插入删除操作方面具有优势，但随机访问速度较慢。列表在 Python 中提供了极大的灵活性，可以存储不同类型的元素，但在性能上可能有所牺牲。了解这些数据结构的特点和应用场景，能够帮助我们在编程中选择合适的数据结构来解决问题，提高程序的效率和性能。