线性表-链表
顺序表的链式表示
顺序表和链表
顺序表可以随机存取表中的任意元素，但插入和删除操作需要移动大量元素。
链表不需要使用地址连续的存储单元，即不需要逻辑上相邻的元素在物理位置上也相邻，通过“链”建立元素之间的逻辑关系，因此插入删除的时候不需要移动元素，只需要修改指针，但同时也会失去随机存取的优点。
链表
链表的结构
链表的结构由一个数据域和一个指针域构成，数据源是data，指针域是next，
数据域存储数据，指针域存放一个指向后继节点的指针，由此构成一条链，所以乘坐链表。
定义一个数据类型为int型的链表节点
typedef struct LNode
{
int data;
struct LNode *next;
} LNode, *LinkList;
通常用头指针L来表示一个链表（下文用L表示）
链表分为带头节点和不带头节点，
不带头节点
带头节点的
头节点是链表的第一个节点，节点内通常不存储信息，即头节点的data一般不存储数据
无论是否带头节点，头指针始终指向第一个节点
带头节点的好处
- 方便操作
- 对于空表和非空表的处理得到统一
链表实现
初始化
链表的初始化，带头节点和不带头节点是不同的，带头节点需要创建一个头节点，让头指针指向头节点，头节点的next为空，代表着没有下一个节点。
bool InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
// T = (LinkList)malloc(sizeof(LNode));
if (L == NULL)
return false;
L->next = NULL;
return true;
}
不太头节点则，只需要头指针为空即可。
相关操作
查找
链式结构不支持随机查找，所以只能通过第一个节点依次访问
LNode *GetElem(LinkList L, int i)
{
if (i < 0)
return NULL;
LNode *p;
int j = 0;
p = L;
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
查找第i个元素，从第一个节点开始向前遍历，因为带头指针，所以从0开始计数
判断是否为空
带头节点和不带头节点也需要不同操作
带头节点，应该判断头指针指向的头节点的next域是否为空
反之，判断头指针是否指向空
插入
这里是重点，
节点P指向a，a指向b，现在要在a和b之间插入x，执行后插操作
bool InsertNextNode(LNode *p, int e)
{
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL)
return false;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
s->next = p->next;
p->next = s;
这两句是重中之重，先让待插入节点指向b，然后a再指向待插入节点，这两句不能调换顺序
如果是前插操作，可以等同后插，
比如，P指向b，现在要在b之前插入一个x，但链表只能向前操作，该如何实现？
可以当作，在P指向的节点后插一个节点，然后修改其data
bool InsertPriorNode(LNode *p, int e)
{
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s = NULL)
return false;
s->data = p->data;
s->next = p->next;
p->data = e;
p->next = s;
return true;
}
利用后插，交换data，就可以实现。
同时，还有删除操作
这个便是删除操作，将实线化作虚线，但同时要考虑待删除节点的后继是否合法，比如没有后继的情况，只需要指向空即可
bool DeletNode(LNode *p)
{
if (p == NULL)
return false;
LNode *q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);
return true;
}
同时，还有删除特定值的操作
除了单链表外，还有循环链表，双循环链表，对于修改更加方便