一、线性表简介
线性表是一种线性结构，它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中，除了头尾元素，每个元素都有且只有一个直接前驱，有且只有一个直接后继，而序列头元素没有直接前驱，序列尾元素没有直接后继。
数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种相同的抽象数据类型。可以是C语言的内置类型或结构体，也可以是C++自定义类型。
二、数组（vector和array）
数组在实际的物理内存上也是连续存储的，数组有上界和下界。C语言中定义一个数组：
数组下标是从0开始的，a[0]对应第一个元素。其中，a[0]称为数组a的下界，a[6]称为数组a的上届。超过这个范围的下标使用数组，将造成数组越界错误。在C语言中，容易发生数组越界操作，尽量使用vector和string代替常规的数组和字符串。
【Note】：
（1）数组的特点是：数据连续，支持快速随机访问。
数组分为固定数组与动态数组。其中固定数组的大小必须在编译时就能够确认，动态数组允许在运行时申请数组内存。复杂点的数组是多维数组，多维数组实际上也是通过一维数组来实现的。在C语言中，可以通过malloc来分配动态数组，C++使用new。另外，C++的标准模板库提供了动态数组类型vector以及内置有固定数组类型array。
线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O（1）;而插入或删除时，时间复杂度都是O（n）。
优点：
无需为表示线性表中的逻辑关系而增加额外的存储空间
可以快速的存取线性表中任一位置的元素
缺点：
插入和删除操作需要移动大量的元素
难以确定线性表存储空间的容量
造成存储空间的“碎片”，浪费存储空间
三、单向链表（forward_list）
为了每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的信息之外，还需要存储一个指示其后继元素的信息（即直接后继元素的存储位置）。
1、单向链表的一些操作
单向链表是链表的一种。链表由节点所构成，节点内含一个指向下一个节点的指针，节点依次链接成为链表。因此，链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点，头节点不存放实际的值，它含有一个指针，指向存放元素的第一个节点。
（1）链表的结构代码：
typedef struct node{ int data; node *next;}LNode,*LinkList;//Lnode是node的别名，LinkList是node*的别名（2）查找某个节点：
bool FindNode(const LinkList head, int data){ LinkList ptr = head; while(ptr != nullptr) { if(ptr->data == data) return true; ptr = ptr->next;//移动临时指针 } return false;}（3）求节点的个数：
int NodeNum(const LinkList head){ int length = 0; LinkList ptr = head; while(ptr != nullptr) { ++length; cout << ptr->data << " "; ptr = ptr->next; } return length;}（4）插入某个节点：
//在ptr之前插入某个节点LinkList InsertNode(LinkList ptr, LinkList newnode){ if (ptr == nullptr) { ptr->next = newnode; newnode->next = nullptr; } else { newnode->next = ptr->next; ptr->next = newnode; } return newnode;}（5）删除某个节点：
void EraseNode(LinkList ptr){ LinkList Y = new LNode; if (ptr != nullptr) { Y = ptr->next; ptr->next = Y->next; delete Y; }}（6）尾插法创建链表：
void CreateListTail(LinkList *L, int n){ LinkList p,r; int i; srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); r = *L; for (i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = rand() % 100 + 1; r->next = p; /*将表尾终端节点的指针指向新节点*/ r = p; /*将当前的新节点定义为表尾终端节点*/ } r->next = NULL;}（7）删除链表：
Status ClearList(LinkList *L){ LinkList p, q; p = (*L)->next; /*p指向第一个节点*/ while (p) /*没到结尾*/ { q = p->next; free(p); p = q; } (*L)->next = NULL; /*头节点指针域为空*/ return OK;}2、单向链表结构与顺序存储结构的优缺点
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
查找：顺序存储结构O(1)，单链表O(n)。
插入和删除：顺序存储结构O(n)，单链表O(1)。
顺序存储结构需要预先分配存储空间，分大了浪费空间，分小了容易造成内存溢出；单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
3、链表反转
LinkList ReverseNode(LinkList head){ LinkList p, q, r; p = head; q = nullptr; while (p != nullptr) { r = q; q = p; p = p->next; q->next = r; } return q;}四、循环链表
将单链表中终端节点的指针由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环列表，简称循环列表（circular linked list）。循环列表解决了一个很麻烦的问题：如何从任意一个节点出发，访问到链表的全部节点。
非空的循环列表：
其实循环列表和单链表的主要差异就在于循环的判断条件上，单链表是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。
（1）插入节点：
//在链表首节点前插入节点void InsertNode(LinkList ptr, LinkList X){ LinkList head = X; ptr->next = head; LinkList curnode = head; while (curnode->next != head) { curnode = curnode->next; } curnode->next = ptr; ptr = head;}（2）删除节点：
//删除某个节点void EraseNode(LinkList ptr, LinkList Y){ while ((ptr != nullptr) && (ptr->next != Y)) { ptr = ptr->next; } Y = ptr->next; ptr->next = Y->next; delete Y;}五、双向循环链表（list）
单链表的节点链接是单方向的，要得到指定节点的前一个节点，必须从头遍历链表。
双向链表是链表的一种。与单链表一样，双向节点由节点链接而成，每个节点含有两个指针，分别指向直接前驱与直接后继。从双向链表的任何一个节点开始都能够遍历整个链表。
我们将双向链表实现为双向循环链表，也即是最后一个元素的后继将指向头节点，整个链表形成一个循环
（1）插入节点
s->prior = p; /*把p赋值给s的前驱,如图①*/s->next = p->next; /*将p的后继节点赋值给s的后继,如图②*/p->next->prior = s; /*将s赋值给p->next的前驱,如图③*/p->next = s; /*将s赋值给p的后继,如图④*/（2）删除节点