顺序表：

在程序中，经常需要将一组（通常为某一个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量来记录 它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样一组序列元素的组织形式，我们可以将其抽象为“线性表” ，一个线性表是某类元素的一个集合体，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用于更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模式：
顺序表：将元素顺序的存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。 （连续存储）

链表：将元素存放在通过链接构造起来的一系列存储块中 （离散存储）

一个顺序表的完整信息包括两个部分，一部分是表中的元素集合，另一部分是为实现正确操作而需要记录的信息，即有关表单整体情况的信息，这部分信息主要包括元素存储区域的容量和当前表中的已有的元素个数两项 

一 、 顺序表的基础结构概念

图a为一体式结构，存储表信息的单元与元素储存区的以连续的方式安排在一块储存区里，两部分的数据（表头+数据）整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。但是由于数据元素存储域是表对象的一部分，顺序表被创建后，元素存储区就固定了。

图b为分离式结构，表对里面只保存了与整个表有关的信息（容量+元素个数），实际数据元素放在另一个独立的元素存储区域里，通过链接与基本表对象关联。

顺序表的替换

一体式结构：由于顺序表信息区和数据区是连续存储一起的，所以若要想换数据区，则只能整体搬迁，即整体顺序表对象都改变（指的是存储顺序表数据结构信息的区域）

分离式结构：若想更换数据区，只需要将数据区的数据链接地址更新即可，而该顺序表的结构不变。

元素存储区的扩充

分离式结构的顺序表，若将数据区更换为存储区更大的区域，则可以在不改变    对象的前提下对其数据存储区进行扩充，所有使用这个表的结构就不会因为满了而导致操作无法进行。人们把这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化

两种策略：

1、 每次扩充需要增加的固定数目的存储位置（比如每次扩充都只是增加10个元素位置），这种策略叫线性增长。

特点：操作频繁，重复操作次数多，但是节省空间。

2、每次扩充容量加倍（以倍数增长）

特点：减少了扩充的执行次数，但是可能会浪费存储空间资源。（就是以空间换时间的方式）

---

二、顺序表的操作

增加元素，共以下三种方式

A、尾端加入元素，时间复杂度O（1）

B、非保序的插入元素（不常见，会打乱数据顺序），时间复杂度O（1）

C、保序的元素插入。时间复杂度O（n）

---

A、删除尾端元素时，时间复杂度为O（1）

B、非保序的删除操作，时间复杂度为O（1）

C、保序的删除操作， 时间复杂度为O（n）

---

三、Python的顺序表

Python中的list 和 tuple 两种的数据类型采用了顺序表的实现技术，具有前面所描述的所有性质。

tuple是不可变数据类型，即为不可变顺序表，因此不支持改变其内部结构的任何操作，而其他方面，则与list的性质类似（一体式结构顺序表）。

list是可变数据类型，也是一种元素个数可变的线性表，可以加入和删除元素，并在各种操作中维持已有的顺序（保序的动态顺序表），而且list还具有以下特征：

1、基于下标（位置  ） 索引的高效元素访问和更新，时间复杂度O（1），为满足该特征，应该采用顺序表技术，表中元素保存在一块连续的存储区域中。

2、允许任意元素加入，而且在不断加入元素的过程中，表对象的标识（函数id所得到的值）不变。为满足该特征，就必须能更换元素存储区，并且为保证更换存储区时，list对象的标识id不变，只能用分离结构实现技术

在Python的官方实现中，list就是一种采用分离式技术实现的动态顺序表。这就是为什么用list.append（x）或list.insect(len(list),x)的尾部插入元素方法比指定位置插入元素的效率高。

list采用如下的策略：在创建空表（或很小容量的数据表）时，系统会分配一块能容纳8个元素的存储区，在执行插入操作（list.insert()或list.append()）时，如果元素存储区满就换一块大4倍的存储区。但是，如果此时表已经很大（目前最大容量阈值为50000个元素的时候），则会改变策略，采用只增长1倍存储空间的方法。引用这种改变策略的方法，就是为了避免出现过多空闲的存储位置浪费系统资源。