第三章 线性表——时间与空间的相互转化

线性表：零个或多个数据元素的有限序列。

线性表.png

顺序存储结构

优点：
1.无须为逻辑关系增加额外存储开销
2.快速存取表中元素
缺点：
1.插入删除需要步骤过多
2.存储空间死板，不灵活。易造成内存浪费。

单链表结构

优点：
1.存储空间灵活，节省内存。
2.找到插入（删除）位置后，操作简单。
缺点：
1.需为逻辑关系增加存储开销

静态链表（没有指针的情况）

优点：
1.插入删除步骤简单（只需修改游标）
缺点：
1.需为逻辑关系增加存储开销。
2.存储空间死板。
3.失去顺序存储结构随机存取特性。

循环链表：头尾相接的单链表（单循环链表）。

增设链表的尾指针有助于两链表的合并。

双向链表：在单链表的每个节点中添加一个指向前驱结点的指针域的链表。

其他：
随机存取结构：存取时间性能为O(1)的存储结构。