【数据结构 Java 版】玩转链表（3）双链表

爱被打了一巴掌 2021-09-13 20:04 286阅读 0赞

### 文章目录 ###

*   *  一、引子
     *  二、双链表
     *   *  1. 概念
         *  2. 结构
         *  3. 基操的实现
     *  三、总结

## 一、引子 ##

前面已经了解了顺序表和单链表，而在面试当中这些也是经常被提起的

在继续接下来的学习前，我们要搞清以下几个问题：

> 1.  数组和链表的区别
> 2.  顺序表和链表的区别
> 3.  ArrayList 和 LinkedList 的区别

大家发现没上述问题本质上都是同一个问题：顺序表和链表的区别

那么怎么回答呢？我们可以从共性开始介绍

1.  怎么组织数据的？
    
    >  *  **对于顺序表：** 底层是一个数组
    >  *  **对于链表：** 每个数据是由节点组织的（由节点与节点之间的指向组织）
2.  增删查改
    
    >  *  **对于顺序表：** 不适合插入和删除，适合查找和修改
    >  *  **对于链表：** 不适合查找和修改，适合插入和删除
3.  等等![在这里插入图片描述][b54f08483cb44c63b8e4458f959ef4bd.jpg_pic_center]

**注意：**

>  *  ArrayList 和 LinkedList 这两个类是 Java 中的集合类，是封装好的顺序表和链表
>  *  LinkedList 底层是一个**双向链表**

既然学了单链表，我们也要对双链表进行学习，这肯定也很重要，不然为啥 Java 的 LinkedList 底层是一个双链表呢！

那什么是双链表呢？

## 二、双链表 ##

### 1. 概念 ###

在 [【数据结构 Java 版】玩转链表（1）单链表+链表面试题][Java _1] 这章中我们用一图简单介绍了双向链表的样子![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center]

与单链表不同的是

>  *  它引入了一个前驱域 prev，**解决了单链表只能单向访问的痛点**
>  *  在头节点 head 的前提下，还可以增加一个尾节点 last，标志尾巴，这样**可以方便尾插法**

### 2. 结构 ###

那么怎么实现一个双链表呢？

首先我们依然要定义一下节点

class NodeD{ 
        public int val;
        public NodeD prev;
        public NodeD next;
        
        public NodeD(int val){ 
            this.val=val;
        }
    }

和单链表差不多，只是增加了个前驱节点

再对双链表进行定义

public class MyRealLinkedList { 
        public NodeD head;
        public NodeD last;
    }

在单链表的基础上多了个尾节点

接下来我们来实现双向不带头非循环链表的一些操作，是我们对其的理解更加深透

### 3. 基操的实现 ###

1.  头插法
    
        public void addFirst(int data){ 
            NodeD node=new NodeD(data);
            if(this.head==null){ 
                this.head=node;
            }else{ 
                node.next=this.head;
                this.head.prev=node;
                this.head=node;
            }
        }
2.  尾插法
    
        public void addLast(int data){ 
            NodeD node=new NodeD(data);
            if(this.head==null){ 
                this.head=node;
                this.last=node;
            }else{ 
                this.last.next=node;
                node.prev=last;
                this.last=node;
        }
3.  任意位置插入，第一个数据节点为0号下标
    
        public void addIndex(int index,int data){ 
            if(index<0 || index >size()){ 
                throw new RuntimeException("index 不合法");
            }
            if(index==0){ 
                addFirst(data);
            }
            if (index == size()) { 
                addLast(data);
            }
            NodeD node=new NodeD(data);
            NodeD cur=searchNode(index);
            node.next=cur;
            cur.prev.next=node;
            node.prev=cur.prev;
            cur.prev=node;
        }
4.  搜索下标为 index 的数据节点节点
    
        public NodeD searchNode(int index){ 
            int i=0;
            NodeD cur=this.head;
            while(i!=index){ 
                cur=cur.next;
                i++;
            }
            return cur;
        }
5.  查找关键字 key 是否在单链表中
    
        public boolean contains(int key){ 
            if(this.head==null){ 
                return false;
            }
            NodeD cur=this.head;
            while(cur!=null){ 
                if(cur.val==key){ 
                    return true;
                }
                cur=cur.next;
            }
            return false;
        }
6.  删除第一次出现的关键字为 key 的节点
    
        public void remove(int key){ 
            if(this.head==null){ 
                return;
            }
            NodeD cur=this.head;
            while(cur!=null) { 
                if (cur.val == key) { 
                    if (cur == this.head) { 
                        this.head = this.head.next;
                        if(this.head!=null) { 
                            this.head.prev = null;
                        }else{ 
                            this.last=null;
                        }
                    }else { 
                        cur.prev.next = cur.next;
                        if (cur == this.last) { 
                            last = cur.prev;
                        }else { 
                            cur.next.prev = cur.prev;
                        }
                    }
                    return;
                } else { 
                    cur = cur.next;
                }
            }
        }
7.  删除所有关键字为 key 的节点
    
        public void removeAllKey(int key){ 
            if(this.head==null){ 
                return;
            }
            NodeD cur=this.head;
            while(cur!=null) { 
                if (cur.val == key) { 
                    if (cur == this.head) { 
                        this.head = this.head.next;
                        if (this.head != null) { 
                            this.head.prev = null;
                        } else { 
                            this.last = null;
                        }
                    } else { 
                        cur.prev.next = cur.next;
                        if (cur == this.last) { 
                            last = cur.prev;
                        } else { 
                            cur.next.prev = cur.prev;
                        }
                    }
                }
                cur = cur.next;
            }
        }
8.  得到双链表的长度
    
        public int size(){ 
            if(this.head==null){ 
                return 0;
            }
            NodeD cur=this.head;
            int count=0;
            while(cur!=null){ 
                count++;
                cur=cur.next;
            }
            return count;
        }
9.  清除双链表
    
        public void clear(){ 
            NodeD cur=this.head;
            while(cur!=null){ 
                NodeD curNext=cur.next;
                cur.prev=null;
                cur.next=null;
                cur=curNext;
            }
            this.head=null;
            this.last=null;
        }
10. 打印双链表
    
        public void display(){ 
            if(this.head==null){ 
                return;
            }
            NodeD cur=this.head;
            while(cur!=null){ 
                System.out.print(cur.val + " ");
                cur=cur.next;
            }
            System.out.println();
        }

## 三、总结 ##

到此为止，链表我们已经基本认识了，而接下来我们就是通过刷题和积累，去沉淀自己！希望大家看完这篇文章，可以真正的玩转链表！![在这里插入图片描述][0846fc2bd1b44f20ad217daba52d4139.jpg_pic_center]

[b54f08483cb44c63b8e4458f959ef4bd.jpg_pic_center]: /images/20210913/c06ba2dd45b84808b43f8ae8deea0c78.png
[Java _1]: https://blog.csdn.net/weixin_51367845/article/details/120019451
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCe5ZCe5ZCQ5ZCQ5aSn6a2U546L_size_14_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20210913/4c19bafa67084c439a2bd5493308524c.png
[0846fc2bd1b44f20ad217daba52d4139.jpg_pic_center]: /images/20210913/0e51c3a36cae4c47bbc68cc6c6b7f206.png