线性表简介：
一种逻辑结构，相同数据类型的n个数据元素的有限序列，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。
线性表的特点：
（1）元素个数有限
（2）逻辑上元素有先后次序
（3）数据类型相同
（4）仅讨论元素间的逻辑关系
注：线性表是逻辑结构，顺序表和链表是存储结构。
image.png
区别：
| 存储类别 | 顺序表 | 单链表 |
|---|---|---|
| 存储分配方式 | 用一段连续的存储单元依次存储线性表的数据元素 | 采用链式存储结构，用一组任意的存储单元存放线性表的元素 |
| 时间性能 | 查找O（1）、插入和删除O（n） | 查找O（n）、插入和删除O（1） |
| 空间性能 | 需要预分配存储空间，分大了浪费，小了容易发生上溢 | 不需要分配存储空间，只要有就可以分配，元素个数不受限制 |
链表
1. 单链表：
只有一个next指针域
/*单链表定义*/
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode,*LinkList
结构体相关知识：https://www.cnblogs.com/qyaizs/articles/2039101.html
-
头插法建立单链表：
image.png 尾插法建立单链表：需要增加一个尾指针r
LinkList<DataType>::LinkList(DataType a[], int n)
{
first = new Node<DataType>;
Node<DataType> *r = first;
for (int i = 0; i < n; i++)
{
Node<DataType> *s = new Node<DataType>;
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL;
}
image.png
-
插入节点
image.png -
删除节点
image.png
2. 双向链表：
单链表节点的缺点是只有一个后继节点，访问前驱节点只能从头遍历（如插入、删除），时间复杂度为O(n)。双链表，即添加一个指向前驱的节点，节点类型如下：
typedef struct DNode{
ElemType data;
struct DNdoe *prior,*next;
}DNode,*DLinklist;
3.循环链表
3.1循环单链表
和单链表区别在于，表中最后一个结点的指针不是指向NULL而是指向头结点，所以判空条件不是头节点是否为空，而是它是否等于头指针。
3.1循环双链表
