本文介绍什么是链表,常见的链表有哪些,然后介绍链表这种数据结构会在哪些地方可以用到,以及复述队列是底层的实现,通过一个小实例来演示复述队列有哪些功能,最后通过去实现一个双向链表。
1,链表
-
<李> 1.1说明李
<李> 1.2单向链表
<李> 1.3循环链表
<李> 1.4双向链表
2,复述,队列
-
<李> 2.1说明李
<李> 2.2应用场景李
<李> 2.3演示李
3,双向链表
-
<李> 3.1说明李
<李> 3.2实现李
4,总结
5,参考文献
-
<李> 1,链表
<李> 1.1说明李
链表(链表)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(指针),由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O (n)的时间,而顺序表相应的时间复杂度分别是O (logn)和O (1)。
链表有很多种不同的类型:单向链表,双向链表以及循环链表。
优势:
可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。链表允许插入和移除表上任意位置上的节点。
劣势:
由于链表增加了节点指针,空间开销比较大。链表一般查找数据的时候需要从第一个节点开始每次访问下一个节点,直到访问到需要的位置,查找数据比较慢。
用途:
常用于组织检索较少,而删除,添加,遍历较多的数据。
如:文件系统,LRU缓存,复述,列表,内存管理等。
<强> 1.2单向链表
链表中最简单的一种是单向链表,
一个单向链表的节点被分成两个部分。它包含两个域,一个信息域和一个指针域。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址,而最后一个节点则指向一个空值。单向链表只可向一个方向遍历。
单链表有一个头节点脑袋,指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型,节点有两个成员:整型成员(实际需要保存的数据)和指向下一个结构体类型节点的指针即下一个节点的地址(事实上,此单链表是用于存放整型数据的动态数组)。链表按此结构对各节点的访问需从链表的头找起,后续节点的地址由当前节点给出。无论在表中访问哪个节点,都需要从链表的头开始,顺序向后查找。链表的尾节点由于无后续节点,其指针域为空,写作为NULL。
<强> 1.3循环链表
循环链表是与单向链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。
循环链表的运算与单链表的运算基本一致。所不同的有以下几点:
1,在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是像单链表那样置为零。
2,在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域的值等于表头指针时,说明已到表尾,而非象单链表那样判断链域的值是否为NULL。
<强> 1.4双向链表
双向链表其实是单链表的改进,当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。
在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域(当此“连接”为最后一个“连接”时,指向空值或者空列表);一个存储直接前驱结点地址,一般称之为左链域(当此“连接”为第一个“连接”时,指向空值或者空列表)。
