+循环链表 Day26 Java中的数据结构概念(3)

在头结点中不存储任何实质的数据对象，其 next 域指向线性表中 0 号元素所在的结点，

可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便,常用头结点。

一个带头结点的单链表实现线性表的如图 所示。

单链表的一个优点是结构简单，但是它也有一个缺点，即在单链表中只能通过一个结点的引用访问其后续结点，而无法直接访问其前驱结点，

要在单链表中找到某个结点的前驱结点，必须从链表的首结点出发依次向后寻找，但是需要Ο(n)时间。

为此我们可以扩展单链表的结点结构，使得通过一个结点的引用，不但能够访问其后续结点，也可以方便的访问其前驱结点。

扩展单链表结点结构的方法是，在单链表结点结构中新增加一个域，该域用于指向结点的直接前驱结点。

扩展后的结点结构是构成双向链表的结点结构，如图 所示。

双向链表是通过上述定义的结点使用 pre 以及 next 域依次串联在一起而形成的。一个双向链表的结构如图所示。

在双向链表中同样需要完成数据元素的查找、插入、删除等操作。在双向链表中进行查找与在单链表中类似，只不过在双向链表中查找操作可以从链表的首结点开始，

也可以从尾结点开始，但是需要的时间和在单链表中一样

Java中的LinkedList底层使用的就是双向链表。

在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。

要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。

循环链表可以被视为”无头无尾”。

循环链表中第一个节点之前就是最后一个节点，反之亦然。

循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。

对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大。

单向链表的循环带头结点的非空链表

栈（stack ）又称堆栈，它是运算受限的线性表。

其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。

表中进行插入、删除操作的一端称为 栈顶（top） ，栈顶保存的元素称为 栈顶元素。

相对的，表的另一端称为栈底（bottom）

当栈中没有数据元素时称为空栈；

向一个栈插入元素又称为 进栈或 入栈；

从一个栈中删除元素又称为 出栈或 退栈。

由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出栈，

所以又把堆栈称为 后进先出表（Last In First Out，简称 LIFO）

队列（queue ）简称队，它同堆栈一样，也是一种运算受限的线性表，

其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

在队列中把插入数据元素的一端称为 队尾（rear） ），删除数据元素的一端称为 队首（front） ）。

向队尾插入元素称为 进队或入队，新元素入队后成为新的队尾元素；

从队列中删除元素称为 离队或出队，元素出队后，其后续元素成为新的队首元素。

由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离队，

也就是说先进队的元素必然先离队，所以称队列为 先进先出表（First In First Out,简称FIFO）。

所谓双端队列是指两端都可以进行进队和出队操作的队列，如下图所示，将队列的两端分别称为前端和后端，两端都可以入队和出队。其元素的逻辑结构仍是线性结构

在双端队列进队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论前端出还是后端出，先出的元素排列在后出的元素的前面。

输出受限的双端队列，即一个端点允许插入和删除，另一个端点只允许插入的双端队列。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-62503-3.html