线性表基本概念

线性表定义

线性表是：①具有相同数据类型的$n(n\ge 0)$个数据元素 ②有限 ③序列。

1. 特别地，当数据元素个数$n=0$时，线性表是空表；
2. 非空线性表中位序表示第$i$个数据元素，从1开始；
3. 相同数据类型→每个元素占用相同大小的存储空间；
4. 序列→逻辑上具有顺序，除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继；
5. 循环链表是否是线性表？是的。具体来说，循环链表是存储结构，线性表是逻辑结构，线性与否是从逻辑结构来划分的。链表在逻辑上均属于线性结构。循环链表与线性表属于不同层次，是线性表的特殊存储方式。

线性表顺序表示

线性表的顺序存储又称顺序表。逻辑上相邻的元素在物理上也相邻。随机存取。

线性表链式表示

线性表的链式存储又称为单链表。顺序存取。

表：头结点和头指针的区别

设置头结点的原因（必要性）

1. 由于第一个数据结点的位置被存放在头结点指针域中，因此对链表第一个位置上的操作与表在其他位置上的操作一致。
2. 无论链表是否为空，其头指针都指向头结点的非空指针，因此空表和非空表的处理也就统一了。

循环链表

※ 若对单链表的操作通常发生在表头或表尾，则可考虑循环单链表不设头指针而仅设尾指针。

顺序表和链表的比较

1. 结构上：
   1. 逻辑结构：两者都是线性结构；
   2. 物理结构：顺序存储时逻辑上相邻的元素物理上也相邻；链式存储时逻辑上相邻的元素物理上不一定相邻。
2. 读写方式