线性表

定义(逻辑结构)

• 由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表

• 或者说是数据类型相同的元素组成的有限集合

• 线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时称为空表。

• 对千非空的线性表或线性结构，其特点是：

  1. 存在唯一的一个被称作“第一＂的数据元素；
  2. 存在唯一的一个被称作“最后一个＂的数据元素；
  3. 除第一个之外，结构中的每个数据元素均只有一个前驱；
  4. 除最后一个之外，结构中的每个数据元素均只有一个后继。

存储结构

顺序存储

• 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。
• 逻辑上相邻的数据元素，其物理次序也是相邻的
• 简单来说就是数组

链接存储

• 用任意一组存储单元存储线性表
• 一个存储单元除包含结点数据字段的值，还必须存放其逻辑相邻结点（前驱或 后继结点）的地址信息，即指针字段。

• 链表

• 哨兵节点：

  • 为便于在表头进行插入、删除操作，通常在表的前端增加一个特殊的表头结点，称其为哨位（哨兵）结点。

//节点
struct ListNode{ 
 int data;
 ListNode* next;
 ListNode(int d){ data=d; next=NULL; }
 };

struct List{
    ListNode* headnode;//哨兵节点
}

时空效率比较

空间

• 顺序表空间来自于申请的数组空间，数组大小确定，当元素较少时，顺序表中的很多空间处于闲置状态，造成了空间的浪费；
• 链表空间是根据需要动态申请的，不存在空间浪费问题，但链表需要在每个结点上附加一个指针，从而产生额外开销

时间