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

一、引子

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

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

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

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

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

1. 怎么组织数据的？

   • 对于顺序表： 底层是一个数组
   • 对于链表： 每个数据是由节点组织的（由节点与节点之间的指向组织）

2. 增删查改

   • 对于顺序表： 不适合插入和删除，适合查找和修改
   • 对于链表： 不适合查找和修改，适合插入和删除

3. 等等

注意：

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

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

那什么是双链表呢？

二、双链表

1. 概念

在 【数据结构 Java 版】玩转链表（1）单链表+链表面试题 这章中我们用一图简单介绍了双向链表的样子

与单链表不同的是

• 它引入了一个前驱域 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();}

三、总结

到此为止，链表我们已经基本认识了，而接下来我们就是通过刷题和积累，去沉淀自己！希望大家看完这篇文章，可以真正的玩转链表！