前言
在前面记录八 线性表的顺序存储结构和记录九 线性表的顺序存储结构扩展(动态顺序表)中我们了解到线性表的顺序存储结构。我们能够了解到其顺序表的优缺点。我们知道，顺序表的查找和更新是十分快的。通过下标索引的话，其时间复杂度为常数阶。但是，我们在进行插入，删除的时候，我们发现，我们通常需要移动大量的数据才可以完成。有没有什么存储结构能够快速的插入和删除呢？
当然有，那就是链式存储结构。
顺序表的链式存储结构
链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).【1】
链式存储结构的存储单元通常是不连续的，其每一个数据结点通常是由两个域组成。数据域和指针域(我通常认为指针域为关系域，因为部分语言并没有指针。以下，我会将指针域改成关系域)。然后每一个数据结点进行连接。
数据域 ：存放数据的地方。
关系域(指针域) ：存放数据之间关系的地方。
其存储结构抽象类型为
ADT 链式存储结构{
数据域：存放数据
关系域(指针域)：存放数据之间的关系
}结点;
那么数据之间是如何联系的呢？下看图:
举个栗子图
因为链式结构的对数据的关系是通过关系域(指针域)来联系的。所以存储空间不用连续。而因为每一个数据结点都增加了一个关系域(指针域),所以其在空间上会增加。
链表
链表，是其线性表的链式存储结构的简称。链表通常有：单链表、双向链表、循环链表、循环双向链表、静态链表，循环静态链表、循环静态双向链表等等。
单链表大致如下图(这个是我学链表的时候理解画的。偷一下懒)
结构体实现链表
掌握了单链表，除了静态链表之外，其它的都比较好理解。
单链表的方法
构造单链表
在构造单链表之前，我们首先要了解到一个概念：首元结点和头结点。
首元结点：带有数据的第一个结点。
头结点：首元结点的直接前驱结点，其没有直接前驱。
(带头结点的链表和不带头结点的链表)
首元结点和头结点
(为什么要带一个头结点呢？这不白白增加了空间吗？增加了空间不假，但是增加了头结点之后，可以增加其数据的操作性。也就是说。带头结点的链表比不带头结点的链表在插入和删除上更加方便！)
推荐博客:深刻理解：带头结点和不带头结点的区别 使用头结点的优势
所以，在构造单链表的时候，有两种方式:
1.构造带头结点的链表
2.构造不带头结点的链表
方法为(序号对应上面方式)：
1.header -> data = new Node; header->next = NULL;(为头结点的数据域申请内存，关系域(指针域)赋值为空)
2.header = NULL;(没有头指针，我们在构造的时候没有数据，可以直接让header为空)
添加结点
添加结点也有两种方式：头插法和尾插法。
头插法：数据通过头指针直接添加到链表中。(头插法在遍历的时候，数据的顺序和插入时的顺序是相反的。例如，插入的顺序是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】百度百科-链式存储结构
网友评论