04.Java数据结构与算法之~双链表

LinkedList底层原理

       LinkedList底层是一个双向链表；添加、删除元素效率高；按照索引查询效率低。可以两个方向查询

       每个节点都包含了对前一个和后一个元素的引用

       LinkedList同时实现了List、Deque、Queue接口，所以可以当做线性表、队列、双端队列、栈使用

       LinkedList 是非同步的（线程不安全）

       不存在LinkedList容量不足的问题

双链表的添加过程

双向链表:遍历效率可能优于单向链表

定义List接口

public interface List <E>{
    int size();
    boolean isEmpty();
    boolean contains(E element);
    void add(E element);
    E get(int index);
    E set(int index,E element);
    void add(int index,E element);
    E remove(int index);
    int indexOf(E element);
    void clear();
    String toString();
}

实现List接口

public class LinkedList<E> implements List<E>{

    private int size;   //集合的长度
    private Node first;
    private Node last;

    @Override
    public int size() {
        return size;
    }

    //判断当前集合中是否有元素
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    //判断当前元素是否存在
    @Override
    public boolean contains(E element) {
        return indexOf(element) > -1;
    }

    @Override
    public void add(E element) {
        //调用下面的add方法,根据size保证每次都添加在最后
        add(size,element);
    }
    //取得坐标位置上的节点
    private Node<E> node(int index){
        Node N = first; //指向头
        //先判断要查找的index,是靠近头还是靠近尾
        //如果靠近头就从头开始查找,如果靠近尾就从尾开始查找
        //方法: 根据index 和 size的一半去比较
        if(index > (size >> 1)){
            //靠近尾
            N = last;   //指向尾
            for(int i = size-1; i > index; i--){
                N = N.pre;
            }
        }else{
            //靠近头
            for(int i = 0; i < index; i++){
                N = N.next;
            }
        }
        return N;
    }

    @Override
    public E get(int index) {
        //防止坐标越界
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
        }
        //调用方法
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        //获得index上的node
        Node<E> node = node(index);
        //保存原来的值
        E oldElement = node.element;
        //新值覆盖老值
        node.element = element;
        //返回老值
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        //当需要添加到末尾时
        if(index == size) {
            //拿到last节点
            Node l = last;
            //构建node 完成指向关系
            Node newNode = new Node(l,null,element);
            //将原来的last 节点的next 修改成新构建出来的node
            last = newNode;
            if(l == null){
                first = newNode;
            }else {
                l.next = newNode;
            }
        }else{
            //获得指定的index
            Node<E> node = node(index);
            //获得前一个结点
            Node<E> pre = node.pre;
            //构建新的now 完成指向关系
            Node<E> newNode = new Node(pre, node, element);
            //改变指向
            pre.next = newNode;
            if (pre == null) {
                first = newNode;
            } else {
                node.pre = newNode;
            }
        }
        size++;
    }

    //链表删除的主要原理就是将被删除者的前一个元素指向后一个元素
    //比如 A->B->C 当我要删除B的时候,就让A -> C
    @Override
    public E remove(int index) {
        //防止坐标越界
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
        }
        //获得要删除的元素Node
        Node<E>node = node(index);
        //获得前一个结点
        Node<E> pre = node.pre;
        //获得后一个结点
        Node<E> next = node.next;

        if(pre == null){
            //firest进行修改
            first = next;
            next.pre = null;
        }else{
            //改变前一个结点的next
            pre.next = next;
        }
        
        if(next == null){
            //last进行修改
            last = pre;
        }else{
            next.pre = pre;
        }
        size--;
        //返回老元素
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        //查找element元素是否存在,有返回索引,没有返回-1
        Node N = first;
        int index = 0;
        //遍历
        for(Node i = N; i != null; i = i.next){
            if(element == i.element){
                return index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    public String toString(){
        Node N = first;
        StringBuilder stringBuilder = new StringBuilder("[");
        boolean flag = false;   //判断是否循环到了最后
        for(Node i = N; i != null; i = i.next){
            //说明已经到了最后一个元素
            if(i.next == null) {
                flag = true;
            }
            //如果没到最后就加 逗号
            if(flag == false){
                stringBuilder.append(i.element + ",");
            }else{  //到了最后就不加逗号
                stringBuilder.append(i.element);
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //内部Node节点类
    private static class Node<E>{
        Node<E> pre;
        Node<E> next;
        E element;
        public Node(Node next,E element){
            this.next = next;
            this.element = element;
        }

        public Node(Node pre,Node next,E element){
            this.pre = pre;
            this.next = next;
            this.element = element;
        }

        public Node() {

        }
    }
}