线性表

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)。

我们说"线性"和"非线性"，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。

在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的"线性表"，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。

特征

1.集合中必存在唯一的一个"第一元素"。

2.集合中必存在唯一的一个 "最后元素" 。

3.除最后一个元素之外，均有 唯一的后继(后件)。

4.除第一个元素之外，均有 唯一的前驱(前件)。

存储结构

线性表主要由顺序表示或链式表示。在实际应用中，常以[栈]、[队列]、[字符串]等特殊形式使用。

顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像(sequential mapping)。它以"物理位置相邻"来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)，这两部分信息组成数据元素的存储映像，称为结点(node)。它包括两个域;存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链 。

---

链表Tip

结构特点

1.均匀性:同一线性表的各数据元素必定具有相同的数据类型和长度。

2.有序性:各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的。

头指针与头结点的异同

头指针

• 头指针是指链表指向第一个结点的指针
• 若链表有头结点,则指向头结点的指针
• 无论链表是否为空,头指针均不为空.头指针是链表的必要元素.

头结点

• 头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(可以存放链表的长度)
• 有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其它结点的操作统一
• 头结点不一定是链表必要素

单链表结构和顺序存储结构的对比:

存储分配方式

• 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素.
• 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素.

时间性能

• 查找
  - 顺序存储结构 o(1)
  - 单链表 o(n)
• 插入和删除
  - 顺序存储结构需要平均移动表长一半的元素,时间为o(n).
  - 单链表在找出某位置的指针后,插入和删除时间仅为o(1).
• 空间性能
  - 顺序存储结构需要预分配存储空间,分大了,浪费,分小了易发生上溢.
  - 单链表不需要分配存储空间,只要有就可以分配,元素个数也不受限制.