单链表的存储密度高于双链表（单链表和双链表的存储密度）



学习数据结构-第二章：线性表（顺序存储，插入，删除）介绍文章讲到线性表的顺序表示也就是顺序表，顺序表虽然可以随机存储，但是在初始化的时候需要申请一大笔块连续的存储空间，并且在执行插入和删除操作时，也需要大量的移动元素，时间复杂度比较高，下面讲线性表的另一种存储结构：

线性表的链式存储又称：，通过一组的存储单元来存储线性表中的数据元素。

数据元素存储在任意位置，不一定连续，通过指针实现线性逻辑关系。

我们把单链表中这样叫做单链表的一个结点，一个存储数据元素的和下一个结点（数据元素）的地址的组成。

有头节点的单链表，它的头节点的数据域一般不存储数据，它的指针域存储第一个结点的地址。
优点：
-链表的第一个位置和其他位置的操作统一（比如插入操作：无头例程的链表，在表中插入结点的时候两边都有结点，而在表头插入结点的时候左边是没有结点的，而有头例程就都是一样的。）
-空表和非空表的操作统一

时间复杂度：O（n）

时间复杂度：O（n）

按照和按序号查找都要遍历单链表。

按序号查找

时间复杂度：O（n）

按序值查找

时间复杂度：O（n）

插入有两种方式，前插法和后插入法，某些插入位置为i，前插法就是在i的位置之前插入，后插法就是在i的位置之后插入，所以前插法要找i-1位置，而后插法直接寻找这个位置。所以如果i的位置是已知的，这样两种方法就会产生区别，前插法仍然需要遍历链表O（n），而后插法直接使用这个位置即可O（1）。后插法是可以实现前插法的，插入之后交换两个结点的位置即可。

插入结点首先要知道插入的位置，如果插入位置为，则需要知道结点的位置。然后修改新结点的指针指向结点的下一个位置，然后修改结点的指针指向新插入结点。

为什么？
这个顺序是不能交换的，如果交换会出现结
点点地址丢失的问题。这时已经将结点中存储的结点的地址给覆盖了，变成新结点的地址，接着再这相当于讲结点的指针指向了他自己。这样就把后面的链表给替换了。

结点的位置未知

如果要删除链表中第一个结点的位置，修改第号结点的指针，让其指向第号结点的位置。这是要注意要使用一个指针指向第一个结点，因为修改之后我们会失去第一个结点的位置，这样后面就无法释放结点的空间。

结点的位置已知* p

这时可以先交换结点和结点的数据，然后删除后一个结点即可，注意要有一个，方便之后释放空间。

在使用单链表的时候，我们知道当前结点的指针，在执行插入，删除等需要知道它的前驱结点的操作，我们需要通过按序号查找的方式查找到他的前驱结点。度是O（n）。

如果上游中有一个直接指向它的前驱结点的指针，那么我们就可以直接找到它的前驱例程了。所以这样就出现了双链表。

在单链表中，在表头，表中和表尾的插入步骤相同。但是注意在双链表中，在表头和表中跟在表尾插入是不一样的步骤。在双链表的表尾进行插入的时候要注意表尾后面没有下一个结点，所以不能修改下一个结点指向前驱的指针，否则会出现错误。

假设我们使用单链表，我们只知道尾指针，但是需要知道头指针，这时候是无法知道的。
这是如果将单链表的最后一个结点的指针指向头节，这样就可以找到的头指针，这样的链表形成一个环，叫做循环单链表。
这样就只设置一个尾指针就行了，而且效率更高：因为如果只有头指针，我们想找到尾指针，需要遍历单链表，但是如果有一个尾指针，我们找头指针直接就可以找到。
在循环单链表插入和删除操作，在每一个位置都是一样。

我们需要把链表最后一个结点的指针修改为头节点，并且需要修改头计数器的前驱指针指向最后一个结点。这时每一个位置的插入和删除操作都是一样。

静态链表：。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/36664.html