前言

在前面记录八 线性表的顺序存储结构和记录九 线性表的顺序存储结构扩展(动态顺序表)中我们了解到线性表的顺序存储结构。我们能够了解到其顺序表的优缺点。我们知道，顺序表的查找和更新是十分快的。通过下标索引的话，其时间复杂度为常数阶。但是，我们在进行插入，删除的时候，我们发现，我们通常需要移动大量的数据才可以完成。有没有什么存储结构能够快速的插入和删除呢？
当然有，那就是链式存储结构。

顺序表的链式存储结构

链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).【1】

链式存储结构的存储单元通常是不连续的，其每一个数据结点通常是由两个域组成。数据域和指针域(我通常认为指针域为关系域，因为部分语言并没有指针。以下，我会将指针域改成关系域)。然后每一个数据结点进行连接。

数据域 ：存放数据的地方。

关系域(指针域) ：存放数据之间关系的地方。

其存储结构抽象类型为

ADT 链式存储结构{
    数据域：存放数据
    关系域(指针域)：存放数据之间的关系
}结点;

那么数据之间是如何联系的呢？下看图:

举个栗子图

链表

链表，是其线性表的链式存储结构的简称。链表通常有：单链表、双向链表、循环链表、循环双向链表、静态链表，循环静态链表、循环静态双向链表等等。

单链表大致如下图(这个是我学链表的时候理解画的。偷一下懒)

结构体实现链表

掌握了单链表，除了静态链表之外，其它的都比较好理解。

单链表的方法

构造单链表

在构造单链表之前，我们首先要了解到一个概念：首元结点和头结点。

首元结点：带有数据的第一个结点。

头结点：首元结点的直接前驱结点，其没有直接前驱。

(带头结点的链表和不带头结点的链表)

首元结点和头结点

添加结点

添加结点也有两种方式：头插法和尾插法。

头插法：数据通过头指针直接添加到链表中。(头插法在遍历的时候，数据的顺序和插入时的顺序是相反的。例如，插入的顺序是1、2、3、4、5。则遍历输出后则就是5、4、3、2、1.)

尾插法：首先遍历找到尾部结点。然后通过尾部结点将数据添加到链表中。(其主要是麻烦在需要找到尾部结点。如果只有头指针，则每一次添加都需要遍历一次来链表。所以我们通常会添加一个尾指针来指向链表的尾部。)

方法为：
1.头插法：
1.添加的结点的关系域(指针域)先指向首元结点。(保存原先的数据)
2.再将头结点指向新添加的结点。(没有头结点，就直接让添加的结点变成头指针)

(带头结点的的链表)
newNode->next = header->next;//新添加的结点先保存好原先的数据。指向首元结点
header->next = newNode;//再将头结点的指针域指向新添加的结点。
(不带头结点的链表)
newNode->next = header;//先保存好原先的数据。即添加结点的关系域(指针域)指向首元结点
header = newNode;//修改头指针

2.尾插法：
1.先找到尾结点。
2.尾结点的指针域指向新添加的结点。

(没有尾结点的链表)
Node move = new Node;//创建一个移动的指针。(不能用头指针去寻找尾结点，因为头指针是整个链表的标识。如果我们找不到头结点的时候，我们就找不到链表了。)
//带有头结点的链表
while(move ->next != NULL){//循环找到尾结点
    move = move->next;
}
//不带头结点的链表
while(move != NULL){//循环找到尾结点
    move = move->next;
}
newNode->next = move->next;//先保存好尾部结点的指针域。(单链表尾结点为NULL)
move->next = newNode;//尾部结点指向新添加的数据。
(有尾结点的链表)
newNode->next = tail->next;//先保存好尾部结点的指针域
tail  = newNode;//尾部结点指向新的结点

插入数据

插入数据

方法：
1.找到需要插入结点的前一个结点。
2.将插入结点的指针域指向第一步找到结点的指针域。(保存数据，防止数据丢失)
3.将第一步找到的结点的指针域指向插入结点
(不需要移动大量的数据，只需要移动指针即可。)

(设需要将newNode结点插入到insertNode结点之前)
Node move = new Node;//创建一个移动的指针。(不能用头指针去寻找尾结点，因为头指针是整个链表的标识。如果我们找不到头结点的时候，我们就找不到链表了。)
//带有头结点的链表(没有头结点特别不好插入。各种判断。这里就不进行了。)
while(move->next != NULL){//循环遍历，查找的数据的前一个结点。
    if (move->next->data == insertNode->data){//查找到前一个结点
         break;         
    }
    move = move->next;
}
newNode->next = move ->next;//(move为插入结点的前一个结点.move->next指向的就是insertNode)
move->next = newNode;//插入新结点

删除数据

删除数据

方法：
1.找到需要删除结点的前一个结点。
2.保存第一步找到的结点的指针域。
3.将第一步找到的结点的指针域等于下一个结点的指针域。
3.释放第二步保存的指针域。

(设需要删除delNode结点)
Node move = new Node;//创建一个移动的指针。(不能用头指针去寻找尾结点，因为头指针是整个链表的标识。如果我们找不到头结点的时候，我们就找不到链表了。)
//带有头结点的链表
while(move->next != NULL){
      if(move->next->data == delNode->data){//第一步：判断是否为需要删除的结点(move是需要删除结点的前一个结点的)
              Node del = move->next;//第二步：保存需要删除的结点
              move->next = move->next->next;//第三步：删除结点
              delete del;//第四步:释放内存
              break;
      }
      move = move->next;
}

总结

链式存储结构使用与大量的插入和删除操作。其不适合与查找操作。因为其查找每次都的遍历整个链表。而且。链式存储结构会比顺序存储结构多一个空间。用来存放数据的关系。且链式存储结构不需要连续的空间。而顺序存储结构一定是连续的。

链式存储结构的抽象类已经在记录七 线性表给出。

参考资料:【1】百度百科-链式存储结构