线性表

定义：具有相同数据类型的n（n>=0）个数据元素的有限序列。
若用L命名线性表，其一般表示如下：L=（a1,a2....ai,ai+1...,an）
逻辑特性：其中，a1是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后一个”数据元素，又称表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素，每个元素有且只有一个直接后继。

由此，线性表特点归纳如下：

表中元素个数有限
表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序
表中元素都是数据元素，每个元素都是单个元素
表中元素的数据类型都相同。者意味着每一个元素占有相同大小的存储空间
表中元素具有抽象性。即仅讨论元素间的逻辑关系，不靠路元素究竟表示什么内容

Intention：线性表是一种逻辑结构，表示元素间一对一的关系
顺序表和链表是指存储结构。

顺序表

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

表中元素逻辑顺序与其物理顺序相同，所以插入和删除操作需要移动大量元素
顺序表中最主要的特点是随机访问，通过首地址和元素序号可以在O（1）时间内找到指定元素
顺序表存储密度高，每个节点只存储数据元素

顺序表中元素位序是从1开始，而数组中元素下表是从0开始的。

线性表的链式存储

定义：不需要使用地址连续的存储单元，是通过“链”建立起的数据元素间的逻辑关系，又称单链表
对线性表的插入、删除不需要移动元素，而只需要修改指针

单链表：通过任意的存储单元来存储线性表中的数据元素。每个链表节点除存放元素自身信息外，还需存放一个指向其后继的指针next。

特点：

单链表附加指针域，解决了顺序表需要大量连续存储空间的特点，但是浪费空间
单链表是非随机存取的存储结构，查找节点时，需要从表头开始遍历，依次查找。

双链表

双链表节点中存在两个指针，prior 和 next，分别指向其前驱节点和后继节点

循环链表

单链表最后一个节点指针不指向NULL，而是改为指向头节点，从而整个链表形成一个环。

特点：

判断链表是否为空，通过判断头结点的指针是否与头结点相等。
循环链表在任何一个位置插入和删除都是等价的，无需判断是否在表尾