写给小白看的双链表

前言

大家好，我是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节点的变化。

1. 新建插入节点node
2. head前驱指向node
3. node后驱指向head
4. head指向node。(这时候head只是表示第二个节点，而head需要表示第一个节点故改变指向)

尾插：

对于尾插入来说。只需考虑尾节点tail节点的变化。

1. 新建插入节点node
2. node前驱指向tail
3. tail后驱指向node
4. 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断绝关系)

2 head节点指向head.next(这样head就指向我们需要的第一个节点了，前面节点就被删除成功，如果有c++等语言第一个被孤立的节点删除释放即可，但Java会自动释放)

尾删除

尾删除需要注意的就是删除不为空时候尾删除只和tail节点有关。记得在普通链表中，我们删除尾节点需要找到尾节点的前驱节点。需要遍历整个表，而双向链表可以直接从尾节点遍历到前面。

尾删除就是删除双向链表中的最后一个节点，也就是尾指针所指向的那个节点，思想和头删除的思想一致，具体步骤为：

1. tail.pre.next=null尾节点的前一个节点(pre)的后驱节点等于null
2. tail=tail.pre尾节点指向它的前驱节点，此时尾节点由于步骤1next已经为null。完成删除
   

普通删除

普通删除需要重点掌握，普通删除要妥善处理好待删除节点的前后关系，具体流程如下：
1：找打待删除节点node的前驱节点prenode(prenode.next是要删除的节点)

2 : prenode.next.next.pre=prenode.（将待删除node的后驱节点aftnode的pre指针指向prenode，等价于aftnode.pre=prenode）

3: prenode.next=prenode.next.next;此时node被跳过成功删除。

完成删除整个流程的