一步步带你用Java实现双向链表（超详细）

@[toc]

上一节说到了单链表,这一节我们来手写一个双向链表，在这之前，需要先补充一下关于双链表的概念。

什么是双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

属性及方法

节点Node

存储的数据 T data、直接前驱节点 Node pri、直接后继节点 Node next

private static class Node<T> {
    private T data;
    private Node<T> pri;
    private Node<T> next;
}

size

链表中节点的数量

数据插入

头插法 addFirst(T value)

插入数据首先要对链表进行判空

如果链表为空

头结点 = 插入的节点 = 尾结点

不为空则:

1、将插入节点的next指向头结点
2、调整头结点的前驱为新节点
3、将新节点设置为头结点
4、size++

实现细节：
Node<T> node = new Node<>(value);
if (size == 0) {
    first = node;
    last = first;
}else {
    node.next = first;
    first.pri = node;
    first = node;
}
size++;

尾插法 addLast(T value)

依旧要对链表进行判空

为空时：

等价于头插，直接调用addFirst

不为空：

1、调整尾结点的后继next指向新节点
2、调整新节点的前驱pri指向尾结点
3、更新尾结点为新的节点
4、size++

实现细节

if (size == 0){
     return addFirst(value);
 }else {
     Node<T> node = new Node<>(value);
     last.next = node;
     node.pri = last;
     last = node;
 }
size++;

插入到指定下标位置add(int index)

由于是根据下标插入的，所以首先要判断下标

注意，此时的下标最大值应该是size-1，但是在插入的时候是==可以取到size的==，因为此时的下标代表的是==插入的位置==（注意和删除时进行区分）
下标不合法:

这里我选择了抛出异常，也可以进行其他处理

下标合法【0 - size】：

1、判断下标取值

为0 即进行头插法 addFirst(T value)
为size 即进行尾插法 addLast(T value)
为其他值：

遍历到指定节点的前一个节点-> left
设置新节点的next值为left的next值
将left的next值设置为新节点
调整新节点的pri值为left
调整新节点的next节点的pri值为新节点

​ 2、size++

实现细节

add(int index,T value){
    if (index < 0 || index > size-1){
        throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
    } else if(index == 0){
        return addFirst(value);
    }else if (index == size){
        return addLast(value);
    }else {
        Node<T> node = new Node<>(value);
        Node<T> head = first;
        for (int i = 0; i < index-1; i++) {
            head = head.getNext();
        }
        node.next = head.next;
        head.next = node;
        node.pri = head;
        node.next.pri = node;
    }
    size++;
}

数据删除(返回被删除节点存储的值)

删除头结点 removeFirst

实现思想

1、判断链表是否为空
2、存储头结点存储的数据
3、将头结点更新为头结点的next节点
4、设置新的头结点的前驱节点为空
5、返回原始头结点存储的数据
6、size–

实现细节

public T removeFirst(){
    if (size == 0){
        throw new RuntimeException("链表为空！");
    }
    T data = first.getData();
    Node<T> node = first.next;
    node.setPri(null);
    first = node;
    return data;
}

删除尾结点 removeLast

实现思想

1、判断链表是否为空
2、存储尾结点存储的数据
3、更新尾结点为尾结点的前驱节点
4、设置新的尾结点的后继节点为空
5、返回原始尾结点存储的数据
6、size–

实现细节

public T removeLast(){
    if (size == 0){
        throw new RuntimeException("链表为空！");
    }
    T data = last.getData();
    Node<T> node = last.pri;
    node.setNext(null);
    last = node;
    return data;
}

删除指定下标节点remove（int index）

1、判断链表是否为空
2、判断下标是否合法

不合法：

抛出异常

合法【0 - size-1】：

为0 即删除头结点 removeFirst()

为size-1 即删除尾结点 removeLast()

为其他值

1、遍历到指定下标对应节点的前驱节点 left，则当前节点为left的后继节点 temp
2、存储temp存储的数据 data
3、设置left的后继节点值为temp的后继节点
4、设置left的后继节点的前驱节点值为left节点
5、返回原指定下标对应的数据（也可以在返回之前将当前节点的后继值设为空，便于GC回收）
6、size–

实现细节

public T remove(int index){
    if (size == 0){
        throw new RuntimeException("链表为空！");
    }
    //注意添加的时候，下标取不到size，但是添加的位置可以是size，但是删除的时候不行
    if (index < 0 || index > size-1){
        throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
    } else if(index == 0){
        return removeFirst();
    }else {
        Node<T> node = first;
        for (int i = 0; i < index - 1; i++) {
            node = node.next;
        }
        Node<T> temp = node.next;
        if (temp != last){
            T data = temp.getData();
            node.next = temp.next;
            temp.next.pri = node;
            temp.setNext(null);
            return data;
        }else {
            return removeLast();
        }
    }
}

获取指定下标位置节点的数据 getData（int index）

实现思想

1、判断下标是否合法【0 - size-1】
2、处理特殊下标 0 size-1，直接返回头、尾结点存储的数据
3、处理其他下标

遍历到当前下标对应节点，返回对应节点存储的数据

实现细节

public T getData(int index){
    if (index<0 || index>size-1){
        throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
    }else if (size == 0){
        throw new RuntimeException("链表为空");
    }else if (size == 1){
        return first.data;
    }else {
        Node<T> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;
    }
}

获取链表长度

getSize()

遍历输出print()

public void print(){
    if (size == 0) {
        System.out.println("该链表为空!");
    }
    Node<T> node = first;
    while (node != null) {
        System.out.print(node.getData() + "\t");
        node = node.next;
    }
    System.out.println();
}

详细遍历输出

依次输出每个节点的直接前驱存储的数据、当前节点存储的数据、后继节点存储的数据（不存在则输出 null）

public void detailPrint(){
    if (size == 0) {
        System.out.println("该链表为空!");
    }
    Node<T> node = first;
    while (node != null) {
        System.out.print("前驱节点值：");
        System.out.printf("%-5s",node.pri == null ? "null\t" : node.pri.getData()+"\t");
        System.out.print("当前节点值：");
        System.out.printf("%-6s",node.getData() + "\t");
        System.out.print("后继节点值：");
        System.out.printf("%-5s",node.next == null ? "null\t" : node.next.getData()+"\t");
        System.out.println();
        node = node.getNext();
    }
    System.out.println();
}

清空链表

public void clear(){
    first.next = null;
    last = first;
}

实现细节

为了方便大家进行测试，下面放了整体实现，欢迎大家测评

package com.jinhuan.chapter04.no4_4.doublyLinkedList;

/**
 * @Author jinhuan
 * @Date 2022/4/19 14:43
 * Description:
 * 实现双向链表
 */
public class DoublelyLinkedList<T> {
    private static int size;
    private Node<T> first;
    private Node<T> last;

    private static class Node<T> {
        private T data;
        private Node<T> pri;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getPri() {
            return pri;
        }

        public void setPri(Node<T> pri) {
            this.pri = pri;
        }

        public Node<T> getNext() {
            return next;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }

    }

    public static int getSize() {
        return size;
    }

    /**
     * 添加节点到头部
     * */
    public boolean addFirst(T value){
        Node<T> node = new Node<>(value);
        if (size == 0) {
            first = node;
            last = first;
        }else {
            node.next = first;
            first.pri = node;
            first = node;
        }
        size++;
        return true;
    }
    /**
     * 添加节点到尾部
     * */
    public boolean addLast(T value){
         if (size == 0){
             return addFirst(value);
         }else {
             Node<T> node = new Node<>(value);
             last.next = node;
             node.pri = last;
             last = node;
         }
        size++;
        return true;
    }
    /**
     * 元素添加到指定位置
     * */
    public boolean add(int index,T value){
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
        } else if(index == 0){
            return addFirst(value);
        }else if (index == size){
            return addLast(value);
        }else {
            Node<T> node = new Node<>(value);
            Node<T> head = first;
            for (int i = 0; i < index-1; i++) {
                head = head.getNext();
            }
            node.next = head.next;
            head.next = node;
            node.pri = head;
            node.next.pri = node;
        }
        size++;
        return true;
    }

    /**
     * 删除头结点
     * */
    public T removeFirst(){
        if (size == 0){
            throw new RuntimeException("链表为空！");
        }
        T data = first.getData();
        Node<T> node = first.next;
        node.setPri(null);
        first = node;
        return data;
    }

    /**
     * 删除尾节点
     * */
    public T removeLast(){
        if (size == 0){
            throw new RuntimeException("链表为空！");
        }
        T data = last.getData();
        Node<T> node = last.pri;
        node.setNext(null);
        last = node;
        return data;
    }

    /**
     * 删除指定下标结点
     * */
    public T remove(int index){
        if (size == 0){
            throw new RuntimeException("链表为空！");
        }
        //注意添加的时候，下标取不到size，但是添加的位置可以是size，但是删除的时候不行
        if (index < 0 || index > size-1){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
        } else if(index == 0){
            return removeFirst();
        }else {
            Node<T> node = first;
            for (int i = 0; i < index - 1; i++) {
                node = node.next;
            }
            Node<T> temp = node.next;
            if (temp != last){
                T data = temp.getData();
                node.next = temp.next;
                temp.next.pri = node;
                temp.setNext(null);
                return data;
            }else {
                return removeLast();
            }
        }
    }

    /**
     * 获取对应下标数据
     * */
    public T getData(int index){
        if (index<0 || index>size-1){
            throw new IndexOutOfBoundsException("数据下标越界 Index:" + index + "\tsize:" + size);
        }else if (size == 0){
            throw new RuntimeException("链表为空");
        }else if (size == 1){
            return first.data;
        }else {
            Node<T> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node.data;
        }
    }

    /**
     * 清空链表
     * */
    public void clear(){
        first.next = null;
        last = first;
    }

    /**
     * 遍历输出当前所有数据
     * */
    public void print(){
        if (size == 0) {
            System.out.println("该链表为空!");
        }
        Node<T> node = first;
        while (node != null) {
            System.out.print(node.getData() + "\t");
            node = node.next;
        }
        System.out.println();
    }

    /**
     * 详细遍历输出:
     *      前驱节点值
     *      当前节点值
     *      后继节点值
     * */
    public void detailPrint(){
        if (size == 0) {
            System.out.println("该链表为空!");
        }
        Node<T> node = first;
        while (node != null) {
            System.out.print("前驱节点值：");
            System.out.printf("%-5s",node.pri == null ? "null\t" : node.pri.getData()+"\t");
            System.out.print("当前节点值：");
            System.out.printf("%-6s",node.getData() + "\t");
            System.out.print("后继节点值：");
            System.out.printf("%-5s",node.next == null ? "null\t" : node.next.getData()+"\t");
            System.out.println();
            node = node.getNext();
        }
        System.out.println();
    }
}

以上均为本人个人观点，借此分享，希望能和大家一起进步。如有不慎之处，劳请各位批评指正！鄙人将不胜感激并在第一时间进行修改！