数据结构之线性表

数据结构之线性表

什么是线性表？

线性表是数据结构中最简单的一种排序方式，在一个线性表中，除了首尾外，其他的数据元素都是首尾呼应的。

线性表的特点

• 存在唯一的表头和表尾
• 除了表头外，表中的每一个元素均只有唯一的直接前驱
• 除了表尾外，表中的每一个元素均只有唯一的直接后继

线性表的存储结构

顺序存储

是用一组地址连续存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。

就比如说 课堂上的位置，1号座位的上面肯定是2号。

• 优点：读取速度快
• 删除和添加速度慢

在线性表的顺序存储结构中，第i个元素的存储位置为：

Loc(ai)=Loc(a1)+(i-1)*L
           

链式存储

• 优点：删除、添加快
• 缺点：查询速度慢

其他链表结构

1. 双向链表：每个结点包含两个指针，指明直接前驱和直接后继元素，可在两个方向上遍历链表。
2. 循环链表：表尾结点的指针指向表中的第一个结点，可在任何位置上开始遍历整个链表。
3. 静态链表：借助数组来描述线性表的链式存储结构。