数据存储——双向链表

所有的代码都存放在了gitee上，该知识点上所有的源代码见：源代码

首先我们需要了解什么叫链表，通过百度百科的链表可以知道链表的定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

从这段话我们可以知道的几个知识点是：

• 非连续
• 非顺序
• 通过指针连接
• 查找时间复杂度高
• 插入时间复杂度低

双向链表

单链表源码位于（源代码/src/cn/tansanqinger/linked/DoublyLinkDemo.java）

增加数据

首先还是来聊聊原理，它和单向链表类似，都是通过结点来存储数据，它们之间的区别在于，单向链表的数据只能通过首结点往尾结点读取数据，不能反过来，但是双向链表可以实现这个功能，就好像数组一样，从前往后从后往前都是可以的。因此，再设计的时候就需要再结点设置两个地址存放位置。原理图如下

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AS7zK7EC-1601889735450)(C:\Users\C3H2\AppData\Roaming\Typora\typora-user-images\image-20201005151834505.png)]

所以再整体的设计上和单链表是没有任何区别的，那么现在开始使用代码来实现增加数据。该代码依然遵循面向接口编程。当然这里只是为了将这种思想表述出来，并不严谨。你可以将单项链表和双向链表的公共接口抽象出来，然后再进行设计（如果有不同方法，再加一级接口就好了，架构师的核心思想就是：没有什么是加一层无法解决的，如果不能，就加两层）。

interface IDoublyLink<T>{
    void add(T data);//添加数据
    int size();//返回链表长度
}
class DoublyLinkImpl<T> implements IDoublyLink<T>{
    private Node root;//根结点
    private Node end; //尾结点
    private int size; //记录长度
    @Override
    public void add(T data) {
        Node node = new Node(data);//实例化结点
        if(this.root==null){//判断根结点是否为空
            this.root = node;
            this.end = node;
        } else {
            node.last = this.end;//该实例化结点保存的上结点保存上一个结点
            this.end.next = node;//保存下一个结点
            this.end = node;//移动指针
        }
        this.size ++;
    }
    @Override
    public int size() {
        return this.size;
    }
    private class Node<T> {
        private T data;//保存数据
        private Node next;//存储下一个结点的地址
        private Node last;//保存上一个数据

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

查询数据

我们已经将数据添加到链表中，那么要如何将之读取出来呢？由于我们设计的是双向链表，那么我们在查询数据的时候就要和单向链表进行区分，因此该链表的查询我们分为正向全部查询、逆向全部查询、单一查询。查询数据实际上依然是指针移动，将指针移动到我们需要查询的数据上为止。需要说明的是在进行单一数据查询的时候，我们需要判断要查询的数据距离哪一端更近，然后再选择正向查询还是逆向查询，从而提高查询效率。

查询代码如下

interface IDoublyLink<T>{
    int size();//返回链表长度
    T[] toArrayJust();//返回所有数据，正向
    T[] toArrayAgainst();//逆向输出所有数据
    T get(int index);//返回要查询的数据
}
class DoublyLinkImpl<T> implements IDoublyLink<T>{
    @Override
    public T[] toArrayJust() {
        if(this.size==0){
            return null;
        } else {
            return array(this.root,true);
        }
    }
    @Override
    public T[] toArrayAgainst() {
        if(this.size==0){
            return null;
        } else {
            return array(this.end,false);
        }
    }
    /**
     * 对数据进行数组化处理
     * @param list 链表
     * @param flag 是否正序
     * @return 返回结构
     */
    private T[] array(Node list, boolean flag){
        Object array[] = new Object[this.size];
        int length = 0;
        while(list!=null){
            array[length++] = list.data;
            list=  flag?list.next : list.last;
        }
        return (T[]) array;
    }
    private class Node<T> {
        private T data;//保存数据
        private Node next;//存储下一个结点的地址
        private Node last;//保存上一个数据

        private Node(T data) {
            this.data = data;
        }
    }
    @Override
    public T get(int index) {
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index){
                list = this.root;
                return (T) put(list,index,true).data;
            } else {
                list = this.end;
                return (T) put(list,index,false).data;
            }
        }
    }
    /**
     * 查询单一数据
     * @param index 要查询数据的下标
     * @param flag 通过正序还是逆序
     * @return 返回结果
     */
    private Node put(Node list, int index, boolean flag){
        if(flag){//正序查找
            while(index>0){
                list = list.next;
                index--;
            }
        } else {
            while (index<this.size-1){
                list = list.last;
                index++;
            }
        }
        return list;
    }
}

进行测试

public static void main(String[] args) {
    DoublyLinkImpl<String> link = new DoublyLinkImpl<>();
    link.add("A");
    link.add("B");
    link.add("C");
    System.out.println(link.size());
    System.out.println(link.get(1));
    System.out.println(Arrays.toString(link.toArrayJust()));
    System.out.println(Arrays.toString(link.toArrayAgainst()));
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-I1XNIIvB-1601889735456)(C:\Users\C3H2\AppData\Roaming\Typora\typora-user-images\image-20201005161314900.png)]

删除数据与修改数据

这里的删除数据和修改数据与之前的单向链表再本质上来说并没有什么问题，因此两个可以同时进行操作，不过依然需要说说删除数据的原理。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NlXXj9PF-1601889735460)(C:\Users\C3H2\AppData\Roaming\Typora\typora-user-images\image-20201005161918846.png)]

删除的思想为：移动指针。

在接口中添加T remove(int index)方法和T set(int index,T data)方法

代码实现为：

interface IDoublyLink<T>{
    T remove(int index);//删除数据
    T set(int index, T data);//修改数据
}
class DoublyLinkImpl<T> implements IDoublyLink<T>{
    private Node root;//根结点
    private Node end; //尾结点
    private int size; //记录长度
    @Override
    public T remove(int index) {
        Object dataNode;
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else if(index == 0){
            dataNode = this.root.data;
            this.root = this.root.next;
            this.root.last = null;
        } else if(index == this.size-1){
            dataNode = this.end.data;
            this.end = this.end.last;
            this.end.next = null;
        }else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index-1){
                list = put(this.root,index-1,true);
                dataNode = list.next.data;
                list.next = list.next.next;
                list.next.last = list;
            } else {
                list = put(this.end,index+1,false);
                dataNode = list.last.data;
                list.last = list.last.last;
                list.last.next = list;
            }
        }
        this.size--;
        return (T) dataNode;
    }
    @Override
    public T set(int index, T data) {
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index){
                list = put(this.root,index,true);
            } else {
                list = put(this.end,index,false);
            }
            Object dataNode = list.data;
            list.data = data;
            return (T) dataNode;
        }
    }
    /**
     * 查询单一数据
     * @param index 要查询数据的下标
     * @param flag 通过正序还是逆序
     * @return 返回结果
     */
    private Node put(Node list, int index, boolean flag){
        if(flag){//正序查找
            while(index>0){
                list = list.next;
                index--;
            }
        } else {
            while (index<this.size-1){
                list = list.last;
                index++;
            }
        }
        return list;
    }
    private class Node<T> {
        private T data;//保存数据
        private Node next;//存储下一个结点的地址
        private Node last;//保存上一个数据

        private Node(T data) {
            this.data = data;
        }
    }
}
public class DoublyLinkDemo {
    public static void main(String[] args) {
        DoublyLinkImpl<String> link = new DoublyLinkImpl<>();
        link.add("A");
        link.add("B");
        link.add("C");
        System.out.println(link.get(1));
        System.out.println("删除数据前"+link.size());
        System.out.println(link.remove(1));
        System.out.println("删除数据后"+link.size());
        System.out.println(Arrays.toString(link.toArrayJust()));
        System.out.println(Arrays.toString(link.toArrayAgainst()));
    }
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U9FDbjYL-1601889735465)(C:\Users\C3H2\AppData\Roaming\Typora\typora-user-images\image-20201005171544082.png)]

总结

自此，双向链表的增删改查就算是结束了，也可以去看看LinkedList中的源代码了，去了解一下其中的原理，也可以去对照着看看ArrayList和它之间的区别，如果有兴趣向看看单向链表的可以通过如下方式前往：

数据存储——单向链表

该页面整体代码如下，也可以上gitee上下载。

package cn.tansanqinger.linked;
import java.util.Arrays;
interface IDoublyLink<T>{
    void add(T data);//添加数据
    int size();//返回链表长度
    T[] toArrayJust();//返回所有数据，正向
    T[] toArrayAgainst();//逆向输出所有数据
    T get(int index);//返回要查询的数据
    T remove(int index);//删除数据
    T set(int index, T data);//修改数据
}
class DoublyLinkImpl<T> implements IDoublyLink<T>{
    private Node root;//根结点
    private Node end; //尾结点
    private int size; //记录长度
    @Override
    public void add(T data) {
        Node node = new Node(data);//实例化结点
        if(this.root==null){//判断根结点是否为空
            this.root = node;
            this.end = node;
        } else {
            node.last = this.end;//该实例化结点保存的上结点保存上一个结点
            this.end.next = node;//保存下一个结点
            this.end = node;//移动指针
        }
        this.size ++;
    }
    @Override
    public int size() {
        return this.size;
    }
    @Override
    public T[] toArrayJust() {
        if(this.size==0){
            return null;
        } else {
            return array(this.root,true);
        }
    }
    @Override
    public T[] toArrayAgainst() {
        if(this.size==0){
            return null;
        } else {
            return array(this.end,false);
        }
    }
    @Override
    public T get(int index) {
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index){
                list = this.root;
                return (T) put(list,index,true).data;
            } else {
                list = this.end;
                return (T) put(list,index,false).data;
            }
        }
    }
    @Override
    public T remove(int index) {
        Object dataNode;
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else if(index == 0){
            dataNode = this.root.data;
            this.root = this.root.next;
            this.root.last = null;
        } else if(index == this.size-1){
            dataNode = this.end.data;
            this.end = this.end.last;
            this.end.next = null;
        }else {

            Node list;
            //判断从哪端开始查询
            if(this.size/2>index-1){
                list = put(this.root,index-1,true);
                dataNode = list.next.data;
                list.next = list.next.next;
                list.next.last = list;
            } else {
                list = put(this.end,index+1,false);
                dataNode = list.last.data;
                list.last = list.last.last;
                list.last.next = list;
            }
        }
        this.size--;
        return (T) dataNode;
    }

    @Override
    public T set(int index, T data) {
        if(this.size==0 || this.size<=index || index<0){//排除干扰
            return null;
        } else {
            Node list;
            //判断从哪端开始查询
            if(this.size/2>index){
                list = put(this.root,index,true);
            } else {
                list = put(this.end,index,false);
            }
            Object dataNode = list.data;
            list.data = data;
            return (T) dataNode;
        }
    }
    /**
     * 查询单一数据
     * @param index 要查询数据的下标
     * @param flag 通过正序还是逆序
     * @return 返回结果
     */
    private Node put(Node list, int index, boolean flag){
        if(flag){//正序查找
            while(index>0){
                list = list.next;
                index--;
            }
        } else {
            while (index<this.size-1){
                list = list.last;
                index++;
            }
        }
        return list;
    }
    /**
     * 对数据进行数组化处理
     * @param list 链表
     * @param flag 是否正序
     * @return 返回结构
     */
    private T[] array(Node list, boolean flag){
        Object array[] = new Object[this.size];
        int length = 0;
        while(list!=null){
            array[length++] = list.data;
            list=  flag?list.next : list.last;
        }
        return (T[]) array;
    }
    private class Node<T> {
        private T data;//保存数据
        private Node next;//存储下一个结点的地址
        private Node last;//保存上一个数据

        private Node(T data) {
            this.data = data;
        }
    }
}
public class DoublyLinkDemo {
    public static void main(String[] args) {
        DoublyLinkImpl<String> link = new DoublyLinkImpl<>();
        link.add("A");
        link.add("B");
        link.add("C");
        System.out.println(link.get(1));
        System.out.println("删除数据前"+link.size());
        System.out.println(link.remove(1));
        System.out.println("删除数据后"+link.size());
        System.out.println(Arrays.toString(link.toArrayJust()));
        System.out.println(Arrays.toString(link.toArrayAgainst()));
    }
}