线性表

背景

上一篇文章说过，数据的结构分为线性结构和非线性结构，而线性结构表示结构中所有数据元素都按某种次序排列在一个序列中。根据对线性结构中数据元素存取方法的不同，可分为直接存取结构、顺序存取结构和字典结构。

比如：数组、文件
对于直接存取结构，可以直接存取某一指定项而不须先访问其前驱，就像数组、文件，可以根据下标直接存取某一数组元素，可以按记录号直接检索记录集合或文件中的某一记录。

比如：单链表
对于顺序存取结构，只能从序列中第一个数据元素起，按序列组个访问知道指定的元素（如栈、队列、优先级队列等）。

比如：字典
而字典结构就是通过关键码（Key）进行索引，例如我们要查询学生记录，可以设定学生的学号为关键码，用它来识别是哪一位学生的记录。

顺序存储方式

既可以从表的第一个表项开始组个访问表项，也可以按照表项的下标直接访问；逻辑顺序与物理顺序一致。
优点：
1、无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率高；
2、可以方便地随机存取表中的任一结点，存取速度快；
缺点：
1、在表中插入新元素或者删除无用元素时，为了保持其他元素的相对次序不变，平均需要移动一半元素，运行效率很低；
2、由于顺序表要求占用连续的空间，如果预先进行存储分配（静态分配），则当表长度变化较大时，难以确定合适的存储空间大小，如果数据没有填满就浪费了宝贵的内存，如果超过预先分配的空间就会造成溢出的情况。

链表存储方式

为了克服顺序表的缺点，可以采用链接方式来存储线性表，通常将链接方式存储的线性表成为链表。链表适用于插入或删除频繁，存储空间需求不定的情形。

1、单链表
其存储结点有数据和指针，该指针指向下一个结点的存储地址；为了让增删改查的算法更为通用，我们通常还会在单链表前面增加一个附加头结点；

2、循环链表
它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的指针指向地址不是NULL，而是存放了一个指向链表开始结点的指针。这样只要知道表中任何一个结点的地址，就能便利表中的其他任何一结点。它也可以拥有一个附加头结点。

3、双链表
使用双链表是为了解决在链表中访问直接前驱和直接后继的问题

4、静态链表
用我们的话来说，数组存储的数据类型是一个对象，对象包含两个变量data和link，这里的link存储的是下个一个元素的下标。其也可以拥有附加头结点。