前言

在上一篇文章中，主要是给大家介绍了单向链表的特点及其原理，但是我们没有通过代码进行练习。今天我会继续通过一篇文章，来给大家讲解双向链表的内容，尤其是会通过代码来进行链表的操作，希望大家重点关注哦。

全文大约【3500】 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考...

一. 双向链表简介

1. 概念

在上一篇文章中，我们在介绍链表的种类时，曾经提到过双向链表。双向链表相比较于单链表，除数据域外，还具前和后两个指向指针。

双向链表中的结构术语可以解释为：

• data：链表每个结点中存储的数据域；
• next：链表每个结点中包含的指向下一个结点地址的指针域；
• prev：链表每个结点中包含的前一个结点地址的指针域。

2. 编码定义

根据上述对双向链表结点的定义，我们给出双向链表结点结构的Java定义实现：

class DNode{
    Object data;
    Node prev;
    Node next;
}

双向链表是一条真实存在的链表，由多个结点组成。在实际的编程中，通常会标记链表的两个特殊结点，分别为：头结点、尾结点。用另外一个变量size表示链表中元素的个数。

• 头结点： 链表中的第一个结点
• 尾结点： 链表中的最后一个元素

因此有如下链表类的定义：

public class DoubleLinkList{
    private int size;//大小
    private DNode head;//头结点
    private DNode last;//尾结点
}

在本篇文章接下来的内容中，我们将利用该DNode、DoubleLinkList两个定义来实现双向链表的各项操作。

二. 常见操作

因为双向链表是单链表的基础上扩展出来的结构，因此双向链表的很多操作与单链表的操作都是相同的，比如：查找元素、更新元素、插入元素、删除元素。

1. 查找元素

1.1 查找头结点

因为DoubleLinkList中已经记录了头结点head，因此头结点的查找非常简单，如下：

public Object getHead(){
    if(head == null){
        return null;
    }
    return head.data;
}

时间复杂度为O(1)。

1.2 查找尾结点

与头结点同理，查找尾结点的时间复杂度同样为O(1），编码如下：

public Object getLast(){
    if(last == null){
        return null;
    }
    return last.data;
}

1.3 查找指定位置结点

当需要查找指定位置的结点元素时，双向链表比单链表的实现方式有所不同，原因是： 单链表因为是单向的，因此只能从头结点向后单向查找；但双向链表前后均可查找，因此在进行指定位置查找时，为了提高查找效率，会首先判断要查找的位置处于链表的前半段还是后半段，若前半段则从头结点向后查找，若后半段则从尾结点向前查找，具体编程如下所示：

public Object get(int index){
    //排除边界异常
    if(index <0 || index>=size){
        return null;
    }
	//要查找的位置位于链表前半段
	if(index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        return x.data;
    }else {//要查找的位置位于链表后半段
        DNode x = last;
        for(int i = size - 1; i >= index; i--){
            x = x.prev;
        }
        return x.data;
    }
}

在上述代码中，size >> 1 的写法比较少见，“>>”在计算机编程中代表移位操作。常见的移位操作有两种：

通过实际的编程验证，我们可以知道：执行右移1位操作，变量数据会缩小为原来的1/2。左移相反。同时，我们可以分析出时间复杂度为O(n)。

2. 更新元素

更新元素操作需要两步：

• 找到要更新的元素
• 执行更新操作

根据位置的不同，可以将更新操作分为三种情况：更新头结点，更新尾结点，更新指定位置结点。

2.1 更新头结点

更新头结点代码与查找头结点类似，如下：

public boolean updateHead(Object obj){
    if(head == null){
        return false;
    }
	head.data = obj;
	return true;
}

更新头结点的时间复杂度为O(1)。

2.2 更新尾结点

public boolean updateLast(Object obj){
    if(last == null){
        return false;
    }
	last.data = obj;
}

更新尾结点的时间复杂度同样是O(1)。

2.3 更新指定位置结点

public boolean update(int index, Object obj){
    if(index < 0 || index >= size){
        return false;
    }
    if(index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        x.data = obj;
    }else {
        DNode x = last;
        for(int i = size-1; i >= index; i--){
            x = last.prev;
        }
        x.data = obj;
    }
    return true;
}public boolean addHead(Object data){
    DNode h = head;
	DNode newNode = new DNode(null,data,h);
	head = newNode;
	if(h == null);{
        last = newNode;
    }else {
        h.prev = newNode;
    }
	size++;
	return true;
}

如上代码所示，修改指定结点元素的值采用的算法也是：先判断要操作的位置在前半段还是后半段，然后再进行精准查找，最后执行修改操作。

指定位置修改操作的时间复杂度为O(n)。

3. 插入元素

分析过了查找元素和更新元素操作的具体情况，我们很清晰的便能分析出插入元素操作的具体情况，其实也分为三种具体情景：头结点位置插入，尾结点位置插入，指定位置插入元素。

3.1 头结点位置插入

public boolean addHead(Object data){
    DNode h = head;
	DNode newNode = new DNode(null,data,h);
	head = newNode;
	if(h == null);{
        last = newNode;
    }else {
        h.prev = newNode;
    }
	size++;
	return true;
}

根据如上代码，我们可以看到，在头结点位置插入新的元素，只需要将新添加的结点置为head结点，同时处理好新结点和原链表中头结点的指向关系即可。很明显，头结点位置插入的时间复杂度为O(1)。

3.2 尾结点位置插入

尾结点插入与头结点插入原理相同，只需要替换为尾结点以及指针的指向。如下所示：

public boolean addLast(Object data){
    DNode l = last;
	DNode newNode = new DNode(l,data,null);
	last = newNode;
	if(last == null){
        head = last;
    }else {
        l.next = newNode;
    }
	size++;
	return true;
}

时间复杂度为O(1)。

3.3 指定位置插入

在进行指定位置插入时，编程代码稍多些，原因是需要以下几步完成：

• 判断插入的位置是否超范围
• 若插入的位置在最后，则执行在尾结点的插入逻辑
• 先根据要插入的位置，查找并获取到对应位置的结点元素
• 然后执行插入逻辑

public boolean add(int index,Object data){
    if(index < 0 || index > size){
        return false;
    }
    if(index == size){
        addLast(data);
        return true;
    }else {
        //先找到要插入的指定位置的结点
        DNode x = index(index);
    	//执行插入操作
        DNode prevNode = x.prev;
        DNode newNode = new DNode(prevNode,data,x);
        x.prev = newNode;
        if(prevNode == null){
            head = newNode;
        }else {
            prevNode.next = newNode;
        }
        size++;
    }
}

//查找index位置上的结点并返回
public DNode index(int index){
    if( index < 0 || index >= size){
        return null;
    }
	if( index < (size>>1)){
        DNode x = head;
        for(int i = 0; i < index; i++){
            x = x.next;
        }
        return x;
    }else {
        DNode x = last;
        for(int i = size-1; i >= index; i--){
            x = x.prev;
        }
        return x;
    }
}

根据上述代码，我们可以发现插入指定位置的代码，需要用到查找指定位置的操作，先查找再插入，因此时间复杂度同样为O(n)。

4. 删除元素

有了前面的分析经验，我们可以非常自然的分析出删除操作同样分三种：删除头结点、删除尾结点、删除指定结点。接下来，一起来看看详细的情况：

4.1 删除头结点

public Object removeHead(){
    if(head == null){
        return null;
    }
    DNode h = head;
    Object data = h.data;
    DNode next = h.next;
	//将原来头结点的数据域和指针域均赋值为null置空
    h.data = null;
    h.next = null;

    //将当前结点的next作为新的头结点
    head = next;

    //如果next为null，则说明当前链表只有一个节点，删除该节点，则链表的first、last都为null
    if(next == null){
        last = null;
    }else {
        // next要作为新的头节点，则其prev属性为null
        next.prev = null;
    }
    size--;
    return data;
}

删除头结点只涉及头结点的逻辑判断和操作，因此删除头结点时间复杂度为O(1)。

4.2 删除尾结点

与删除头结点原理相同，操作尾结点。代码如下：

public Object removeLast(){
    DNode l = last;
    if(l == null){
        return null;
    }
    Object data = l.data;
    DNode prev = l.prev;
	//将当前尾节点的属性赋值为null，为了GC清理
    l.data = null;
    l.prev = null;
	// 让当前尾节点的prev作为新的尾节点，赋值给last属性
    last = prev;
	// 如果prev为null，则说明当前链表只有一个节点，删除该节点，则链表的first、last都为null
    if(prev == null){
        head = null;
    }else {
        // prev要作为新的尾节点，则其next属性为null
        prev.next = null;
    }
    size--;
    return data;
}

很明显，删除尾结点的时间复杂度为O(1)。

4.3 删除指定结点

删除指定结点的编码实现如下：

public Object remove(int index){
    if(index < 0 || index >= size){
        return null;
    }
	//首先通过查找方法，查找到
	DNode node = index(index;
	//执行删除操作
	Object data = node.data;
	DNode next = node.next;
	DNode prev = node.prev;

	// 如果prev是null，则说明删除的是当前头节点，则将next作为新的头节点，赋值给head
	if(prev == null){
        head = prev;
    }else {
        // 如果删除的不是当前头节点，则将要删除节点的prev与next连接一起，即将prev的next属性赋值成next
        prev.next = next;
        // 如果prev不是null，则赋值为null
        node.prev = null;
    }

	// 如果next是null，则说明删除的是当前尾节点，则将prev作为新的尾节点，赋值给last
	if(next == null){
        last = prev;
    }else {
        // 如果删除的不是当前尾节点，则将要删除节点的prev与next连接一起，即将next的prev赋值成prev
        next.prev = prev;
        // 如果next不是null，则赋值为null
        node.next = null;
    }
	//将要删除的结点的data数据域设置为null
	node.data = null;
	//链表的结点个数-1操作
	size--;
	return data;
}

如上代码所示，删除指定位置的结点元素也需要先执行index(index)查找算法，至于index的实现，在前文介绍指定位置插入结点操作时，已经进行了实现，此处直接进行使用。

我们不难分析得到，删除指定位置的结点的时间复杂度是O(n)。

三. 其他操作

作为一种常见的数据结构，除了对自身结点元素的一些操作，还有一些对链表状态的获取，比如链表的长度，链表是否为空等，这里给大家介绍一下双向链表的一些其他操作。

1. 链表的大小(元素结点的个数)

public int size(){
    return size;
}

2. 判断链表是否为空

public boolean isEmpty(){
    return size == 0;
}

3. 获取链表元素组成的数组

public Object[] toArray(){
    Object[] result = new Object[size];
    int i = 0;
    for(DNode node = head; node != null; node = node.next){
        resunt[i++] = node.data;
    }
    return result;
}

4. 清空链表

public void clear(){
    for(DNode node = head; node != null; ){
        DNode next = node.next;
        node.data = null;
        node.next = null;
        node.prev = null;
        node = next;
    }
    head = last = null;
    size = 0;
}

四. 结语

至此，我们已经连续用两篇文章给大家介绍了链表的相关知识。

在上一篇文章中，我们主要介绍了链表的基础知识和单链表的常规操作， 同时辅以图示来说明各种操作情况。在本篇文章中，主要是从Java编程角度作为切入点，来进一步讲解双向链表的一些操作。 特别是本篇文章中的大量代码实践，需要大家能够理清逻辑关系，希望你可以动手练起来哦。

本栏目推荐文章
• 写代码时如何合理的画图表达逻辑结构
• 成绩管理系统软件体系结构设计说明书
• JVM学习-Class文件结构
• 线性表
• 数据结构里的一棵树
• Sql Server中同步两个数据库表的数据结构(转)
• pandas修改json数据结构
• 【机器学习】多元线性回归
• 【算法】【线性表】【链表】删除排序链表中的重复元素 II
• 【算法】【线性表】【链表】删除排序链表中的重复元素

线性 双向 结构数据结构 线性 双向 算法 数据结构 线性 双向 结构 线性 双向 结构 数据结构 双向 模板 结构 线性 结构 数据结构 线性 结构 数据 结构 拓扑 双向llc 双向 结构 算法 数据结构 根基 线性 非线性 解决方案 结构 方案