第三章数组和链表

type

status

date

slug

summary

1. 数组 array

1.1 概念

数组是一种最常见的线性数据结构，其将相同类型的元素存储在连续的内存空间中。我们将元素在数组中的位置称为该元素的索引（index）。准确来说Python中是没有数组类型的

1.2 相关操作(略)

可参照列表相关操作来自定义一个数组类，实现初始化、元素访问、元素插入、元素删除、元素查找、数组遍历及数组扩容。

在复杂的系统环境中，程序难以保证数组之后的内存空间是可用的，从而无法安全地扩展数组容量。因此在大多数编程语言中，数组的长度是不可变的。如果我们希望扩容数组，则需重新建立一个更大的数组，然后把原数组元素依次复制到新数组。这是一个𝑂(𝑛) 的操作，在数组很大的情况下非常耗时。

1.3 优缺点

优点：

空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
支持随机访问：数组允许在 𝑂(1) 时间内访问任何元素。
缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。

缺点：

插入和删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素
长度不可变：数组在初始化后长度就是固定的了，扩容数组需要将所有数组复制到新数组，开销很大
空间浪费：如果数组分配的大小超过实际需要，那么多余的空间就被浪费掉了

1.4 典型应用

数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。

随机访问：如果我们想随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实现随机抽样。

排序和搜索：数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数组上进行。

查找表：当需要快速查找一个元素或其对应关系时，可以使用数组作为查找表。假如我们想实现字符到ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存放在数组中的对应位置。

机器学习：神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式构建的。数组是神经网络编程中最常使用的数据结构。

数据结构实现：数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实际上是一个二维数组。

2. 链表 linked list

2.1 概念

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer). 所以链表结构不需要一块连续的内存空间, 它通过”指针”将一组零散的内存块串联起来使用。

链表的组成单位为节点（node），每个节点包含节点的“值”和一或两个用来指向上一个/或下一个节点的位置的”引用“。如下图所示：

2.2 相关方法

is_empty() 链表是否为空

length() 链表长度

items() 获取链表数据迭代器

add(item) 链表头部添加元素

append(item) 链表尾部添加元素

insert(index, item) 指定位置添加元素

remove(item) 删除节点

find(item) 查找节点是否存在

2.3 链表分类及实现

常见的链表类型包括三种：

单向链表：链表中最简单的形式，它的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 None 。

环形链表：一种特殊的单链表。它跟单链表唯一的区别就在尾结点，其中：单链表的尾结点指针next指向空地址，表示这就是最后的结点了，而环形链表的尾结点指针next是指向链表的头结点

双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点类定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

下面，大样将通过Python一一实现这三种链表。

2.3.1 单向链表实现

self.head是指向第一个结点的标识符, 表示链表的头部, 没有实际意义.

Node对象为一个结点, Node对象有一个属性存储数据date, 另一个属性next存储指向下一个Node对象的指引

self.head始终指向第一个结点, cur_node首先指向第一个结点, 然后依据要求, 通过cur_node = cur_node.next 将cur_node指向下一个结点

最后一个结点的next属性为None

2.3.2 环形链表实现

2.3.3 双向链表实现

2.4 数组 vs 链表

ㅤ	数组	链表
存储方式	连续内存空间	分散内存空间
容量扩展	长度不可变	可灵活扩展
内存效率	元素占用内存少、但可能浪费空间	元素占用内存多
元素类型	相同	可以不同
访问元素	O(1)	O(n)
增删元素	O(n)	O(1)

注：数组元素必须是相同类型的，这样才能通过计算偏移量来获取对应元素位置；链表由节点组成，节点之间通过引用（指针）连接，各个节点可以存储不同类型的数据

2.5 链表典型应用

单向链表：常用于实现栈、队列、哈希表和图等数据结构

栈与队列：当插入和删除操作都在链表的一端进行时，它表现出先进后出的特性，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性，对应队列
哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中
图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点

双向链表：常用于需要快速查找前一个和后一个元素的场景。

高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。

环形链表：常用于需要周期性操作的场景，比如操作系统的资源调度。

时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。

3. 列表概述

列表list是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用这考虑限制的问题。列表可以基于链表或数组实现。

链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容

数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表

当使用数组使用列表时，长度不可变的性质会导致列表的实用性降低。为解决此问题，我们可以使用动态数组（dynamic array）来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的，例如Python中的list、Java中的ArrayList、C++中的vector和C#中的List等。