原创公众号:bigsai
文章已收录在 全网都在关注的数据结构与算法学习仓库
前面有很详细的讲过线性表(顺序表和链表),当时讲的链表以但链表为主,但实际上在实际应用中双链表的应用多一些就比如LinkedList。
双链表与单链表区别逻辑上它们均是线性表的链式实现,主要的区别是节点结构上的构造有所区别,这个区别从而引起操作的一些差异。
单链表:
单链表的一个节点,有储存数据的data,还有后驱节点next(指针)。也就是这个单链表想要一些遍历的操作都得通过前节点—>后节点。
双链表:
双链表的一个节点,有存储数据的data,也有后驱节点next(指针),这和单链表是一样的,但它还有一个前驱节点pre(指针)。
上文讲单链表的时候,我们当时设计的是一个带头结点的链表就错过了不带头结点操作方式,这里双链表咱们就不带头结点设计实现。并且上文单链表实现的时候是没有尾指针tail的,在这里我们设计的双链表带尾指针。
所以我们构造的这个双链表是:不带头节点、带尾指针(tail)、双向链表。
对于node节点:
class node<T> { T data; node<T> pre; node<T> next; public node() { } public node(T data) { this.data = data; } }对于链表:
public class doubleList<T> { private node<T> head;// 头节点 private node<T> tail;// 尾节点 private int length; //各种方法 } 具体操作分析对于一个链表主要的操作还是增删。增删的话不光需要考虑链表是否带头节点,还有头插、尾插、中间插等多种插入删除形式,其中的一些细节处理也是比较重要的(防止链表崩掉出错),如果你对这块理解不够深入很容易写错也很难排查出来。当然,链表的查找、按位修改操作相比增删操作还是容易很多。
初始化双链表在最初的时候头指针指向为null。那么对于这个不带头节点的双链表而言。它的head始终指向第一个真实有效的节点。tail也指向最后一个有效的节点。在最初的时候head=null,并且tail=head,此时链表为空,等待节点插入。
public doubleList() { head = null; tail = head; length = 0; } 插入空链表插入
对于空链表来说。增加第一个元素可以特殊考虑。因为在链表为空的时候head和tail均为null。但head和tail又需要实实在在指向链表中的真实数据(带头指针就不需要考虑)。所以这时候就新建一个node让head、tail等于它。
node<T> teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; }头插
对于头插入来说。步骤很简单,只需考虑head节点的变化。
新建插入节点node
head前驱指向node
node后驱指向head
head指向node。(这时候head只是表示第二个节点,而head需要表示第一个节点故改变指向)
尾插:
对于尾插入来说。只需考虑尾节点tail节点的变化。
新建插入节点node
node前驱指向tail
tail后驱指向node
tail指向node。(这时候tail只是表示倒数第二个节点,而tail需要表示最后节点故指向node)
按编号插入
对于编号插入来说。要考虑查找和插入两部,而插入既和head无关也和tail无关。
1 新建插入节点node
2 找到欲插入node的前一个节点preNode。和后一个节点nextNode
3 node后驱指向nextNode,nextNode前驱指向node(此时node和后面与链表已经联立,但是和前面处理分离状态)
4 preNode后驱指向node。node前驱指向preNode(此时插入完整操作完毕)
整个流程的动态图为:
只有单个节点删除
无论头删还是尾删,遇到单节点删除的需要将链表从新初始化!
if (length == 1)// 只有一个元素 { head = null; tail = head; length--; }头删除
头删除需要注意的就是删除不为空时候头删除只和head节点有关
流程大致分为:
1 head节点的后驱节点的前指针pre改为null。(head后面节点本指向head但是要删除第一个先让后面那个和head断绝关系)