单双向链表原理（单向链表和双向链表图解）



今天带各位回顾一下线性数据结构：数组、链表、栈、队列，相信通过下面的文字，你会加深对这几种数据结构的认识。

数组（Array） 是一种很常见的数据结构。它是由相同类型的元素（element）的集合所组成，并且被分配一块连续的内存来存储（与链表对比）。利用元素的索引（index）可以计算出该元素对应的存储地址。它的特点是提供随机访问并且容量有限。

2.1 链表简介

链表（LinkedList） 虽然是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入和删除的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表相应的时间复杂度分别是O(logn) 和O(1)。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但链表不会节省空间，相比于数组会占用更多的空间，因为链表中每个节点存放的还有指向其他节点的指针。链表不具有数组随机读取的优点，但是插入删除元素的时间复杂度为O(1)

2.2 链表分类

常见链表分类：

2.2.1 单链表

单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向null。

2.2.2 循环链表

循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向null，而是指向链表的头结点。

2.2.3 双向链表

双向链表 包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。

2.2.4 双向循环链表

双向循环链表 最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。

2.3 数组vs链表

3.1 栈简介

栈 (stack)只允许在有序的线性数据集合的一端（称为栈顶 top）进行加入数据（push）和移除数据（pop）。因而按照 后进先出（LIFO, Last In First Out） 的原理运作。在栈中，push 和 pop 的操作都发生在栈顶。 栈常用一维数组或链表来实现，用数组实现的队列叫作 顺序栈 ，用链表实现的队列叫作 链式栈 。

3.2 栈的常见应用常见应用场景

3.2.1 实现浏览器的回退和前进功能

我们只需要使用两个栈(Stack1和Stack2)和就能实现这个功能。比如你按顺序查看了 1,2,3,4 这四个页面，我们依次把 1,2,3,4 这四个页面压入 Stack1 中。当你想回头看2这个页面的时候，你点击回退按钮，我们依次把4,3这两个页面从Stack1 弹出，然后压入 Stack2 中。假如你又想回到页面3，你点击前进按钮，我们将3页面从Stack2 弹出，然后压入到 Stack1 中。示例图如下:

3.2.2 检查符号是否成对出现

给定一个只包括 ，，，，， 的字符串，判断该字符串是否有效。 有效字符串需满足：

比如 "()"、"()[]{}"、"{[]}" 都是有效字符串，而 "(]" 、"([)]" 则不是。

这个问题实际是Leetcode的一道题目，我们可以利用栈 来解决这个问题。

3.2.3 反转字符串

将字符串中的每个字符先入栈再出栈就可以了。

3.2.4 维护函数调用

最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out）特性。

4.1 队列简介

队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

4.2 队列分类

4.2.1 单队列

单队列就是常见的队列, 每次添加元素时，都是添加到队尾。单队列又分为 顺序队列（数组实现） 和 链式队列（链表实现）。

顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。

假设下图是一个顺序队列，我们将前两个元素1,2 出队，并入队两个元素7,8。当进行入队、出队操作的时候，front和 rear 都会持续往后移动，当 rear 移动到最后的时候,我们无法再往队列中添加数据，即使数组中还有空余空间，这种现象就是 ”假溢出“ 。除了假溢出问题之外，如下图所示，当添加元素8的时候，rear 指针移动到数组之外（越界）。

为了避免当只有一个元素的时候，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向对头元素，rear 指针指向队列最后一个元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。——From 《大话数据结构》

4.2.2 循环队列

循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。

还是用上面的图，我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候， rear 向后移动。

顺序队列中，我们说 的时候队列为空，循环队列中则不一样，也可能为满，如上图所示。解决办法有两种：

常见应用场景

版权声明：

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

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