【数据结构】Java实现双向链表

1. 接口的实现

2. 动手实现双链表

2.1 重写SeqList接口方法

2.2 在当前链表尾部添加节点（尾插）

2.3 在当前链表头部添加节点（头插）

2.4 检验index是否合法

2.5 在第index位置添加节点（任意位置）

2.6 删除第index个节点

2.7 删除第一个值element的节点

2.8 删除所有值element的节点

2.9 修改第index个节点的值为element

2.10 获取第index个节点的值

2.11 判断链表中是否存在element

2.12 获取element在链表中的位置

2.13 打印链表

2.14 获取链表长度以及清空链表

3. DoubleLinkedList整体实现

3.1 DoubleLinkedList类

3.2 Test类

3.3 测试结果

LinkedList 的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

1. 接口的实现

（这个接口在前面的单链表，动态数组中也可以用到）

public interface SeqList<E> {
    //    尾插
    void add(E element);
    //    将 element 插入到 index 位置
    void add(int index,E element);
    //    删除 index 位置元素<返回删除的值
    E removeByIndex(int index);
    //    删除第一个值element的元素
    void removeByValue(E element);
    //    删除所有值element的元素
    void removeAllValue(E element);
    //    将下标 index 位置元素设置为 element，返回替换前的值
    E set(int index,E element);
    E get(int index);
    //    判断 o 是否在其中
    boolean contains(E element);
    int indexOf(E element);
    int size();
    void clear();
}

2. 动手实现双链表

2.1 重写SeqList接口方法

定义双向链表类，实现SeqList方法，重写同String方法。

（Alt + insert 快速实现方法重写）

package seqlist.link;

import seqlist.SeqList;

public class DoubleLinkedList<E> implements SeqList<E> {
    private DoubleNode head;//头节点
    private DoubleNode tail;//尾节点

    private int size; // 车厢节点个数，保存的元素个数

    //车厢类的定义，车厢作为火车的内部类,对外部完全隐藏
    private class DoubleNode {
        E val;//保存的元素
        DoubleNode prev;
        DoubleNode next;
        DoubleNode(E val) {
            this.val = val;
        }
        public DoubleNode(E val, DoubleNode prev, DoubleNode next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
    public void addFrist(E val){ }
    @Override
    public void add(E element) { }
    @Override
    public void add(int index, E element) { }
    @Override
    public E removeByIndex(int index) { }
    @Override
    public void removeByValue(E element) { }
    @Override
    public void removeAllValue(E element) { }
    @Override
    public E set(int index, E element) { }
    public boolean rangeCheck(int index){ }
    @Override
    public E get(int index) { }
    @Override
    public boolean contains(E element) { }
    @Override
    public int indexOf(E element) { }
    @Override
    public int size() { }
    @Override
    public void clear() { }
    @Override
    public String toString() { }
}

2.2 在当前链表尾部添加节点（尾插）

（1）size++

（2）如果链表为空，这个新插入的节点就是头节点

（3）链表不为空，将当前链表的尾节点的next指向新节点，新节点的前驱prev指向尾节点

（4）更新当新节点为尾节点

public void add(E element) {
        DoubleNode node = new DoubleNode(element);
        size ++;
        if (head == null){
            head = node;
        }else {
            node.prev = tail;
            tail.next = node;
        }
        tail = node;
    }

2.3 在当前链表头部添加节点（头插）

这里头插不是重写方法！（因为前面的动态数组没又头插这一说法，所以这个方法就不放在接口里了）

（1）size++

（2）如果链表尾空，那么新节点就是头节点和尾节点

（3）链表不为空，将新节点的next指向head，head的前驱prev指向新节点

（4）更新新节点为头节点head

public void addFirst(E element) {
        DoubleNode node = new DoubleNode(element);
        size ++;
        if(head == null){
            tail = node;
        }else {
            node.next = head;
            head.prev = node;
        }
        head = node;
    }

2.4 检验index是否合法

 private boolean rangeCheck(int index) {
        if (index < 0 ||index >= size) {
            return false;
        }
        return true;
    }

2.5 在第index位置添加节点（任意位置）

（1）判断index是否合法，不合法退出

（2）判断是不是头插或者尾插，调用相应的方法添加后退出

（3）调用node方法index位置节点的找到前驱prev，将prev.next作为后继节点node方法判断index是比较靠近head就从前往后遍历，比较靠近tail就从后往前遍历，使代码效率更高

（4）节点链接，先连左边区域，再连右边区域

（5）size++

DoubleNode node = new DoubleNode(element,prev,next);

看前面的构造函数，这时候已经将node.prev = prev，node.next = next

    public void add(int index, E element) {
        if (index < 0 || index > size){
            throw new IllegalArgumentException("add index illegal");
        }
        if(head == null){
            addFirst(element);
            return;
        }
        if(index == size){
            add(element);
            return;
        }

        DoubleNode prev = node(index - 1);
        DoubleNode next = prev.next;
        DoubleNode node = new DoubleNode(element,prev,next);
        // 先处理左边区域
        prev.next = node;
        // 再处理右半区域
        next.prev = node;
        size ++;
    }
    // 根据传入索引与中间位置的关系，决定到底从前向后寻找节点还是从后向前寻找节点
    // 内部使用的工具方法
    private DoubleNode node(int index){
        if (index < (size>>1)){
            DoubleNode ret = head;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
            return ret;
        }else {
            DoubleNode ret = tail;
            for (int i = size -1; i > index; i--) {
                ret = ret.prev;
            }
            return ret;
        }
    }

2.6 删除第index个节点

（1）判断index是否合法，不合法退出

（2）调用node方法找到待删除节点

（3）调用unlink(node)方法进行删除，将node的前驱prev和后继next连接，将node的prev和next置空null，再size--。（前驱prev为空时，node是头节点，将新的头节点设为node的下一个节点next；后继next为空时node为尾节点，将node的前驱prev设尾节点）

（4）返回被删除节点的值

public E removeByIndex(int index) {
        if (!rangeCheck(index)){
            throw new IllegalArgumentException("removeByIndex index illegal");
        }
        DoubleNode node = node(index);
        unlink(node);
        return node.val;
    }
    private void unlink(DoubleNode node){
        DoubleNode prev =node.prev;
        DoubleNode next = node.next;
        // 先处理左半区域
        if(prev == null){
            this.head = next;
        }else {
            node.next = null;
            prev.next = next;
        }
        // 在处理右半区域
        if(next == null){
            this.tail = prev;
        }else {
            node.next = null;
            next.prev = prev;
        }
        size--;
    }

2.7 删除第一个值element的节点

遍历链表，在链表中找到与element值相等的节点，调用unlink(node)方法进行删除

这里的图和2.6 中的图一致

    public void removeByValue(E element) {
        DoubleNode node = head;
        for (int i = 0; i < size; i++) {
            if (node.val.equals(element)){
                unlink(node);
                return;
            }
            node = node.next;
        }
    }