Python中顺序表是什么数据结构？

本文共计2944个文字，预计阅读时间需要12分钟。

1、顺序表介绍顺序表是线性表的一种，是最简单的一种线性结构。逻辑上相邻的数据元素在物理上也相邻，元素之间的关系由它们的存储位置来表示，因此可以快速定位元素的位置。顺序表中不允许有空位，因此插入、删除操作时可能需要移动大量元素。

1、顺序表介绍

顺序表是最简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。顺序表可以分配一段连续的存储空间Maxsize，用elem记录基地址，用length记录实际的元素个数，即顺序表的长度

上图1表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：Loc(element i) = Loc(e0) + c*i

所以，访问指定元素时无需从头遍历，通过计算便可获得对应地址，其时间复杂度为O(1)。

如果元素的大小不统一，则须采用图2的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图2中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

图2这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。