共计 1105 个字符，预计需要花费 3 分钟才能阅读完成。
线性表学习笔记，python 语言描述 -2019-1-14
1、线性表简介
在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。
对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。
这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。
根据线性表的实际存储方式，分为两种实现模型：
顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。链表，将元素存放在通过链接构造起来的一系列存储块中。
2、顺序表
2.1、顺序表的基本形式图 a 表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址 Loc (e0) 加上逻辑地址（第 i 个元素）与存储单元大小（c）的乘积计算而得，即：
Loc(ei) = Loc(e0) + c*i
故，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为 O(1)。
如果元素的大小不统一，则须采用图 b 的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图 b 中的 c 不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。
图 b 这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。
2.2、顺序表的基本实现顺序表的基本实现方式：表中元素顺序存放在一片足够大的连续存储区里，首元素存入存储区的开始位置，其余元素依次顺序存放。元素之间的逻辑顺序关系通过元素在存储区的物理地址表示。
顺序表最常见的一种基本实现方式是一个表里保存的元素类型相同，因此存储每个表元素所需的存储量相同，可以在表里等距安排相同大小的存储位置。如下图，一个顺序表，存放的元素是整型的数据类型，整型在 32 位的操作系统中，一个整型数字占用内存的空间大小是 4Byte, 因此，内存中连续存放几个整型数字，每个存放元素的空间的地址值之间是等距。其中 Li 变量指向的通常是顺序表的表头元素的地址值，也就是 0x23。
3、链表之单链表
