在Java语言中,用到集合的时候,通常使用ArrayList来实现。本篇文章,将为大家介绍另外一种容器LinkedList,下面主要介绍了LinkedList的整体结构,以及用源码展示具体的使用方法。

    一、LinkedList的整体结构

    1.1、LinkedList的继承关系

    • public class LinkedList<E> extends AbstractSequentialList <E> implements List<E>, Deque<E>
    • LinkedList具备AbstractSequentialList的特点:AbstractSequentialList 只支持按次序访问,而不像 AbstractList 那样支持随机访问
    • LinkedList具备List的特点
    • LinkedList具备Deque的特点:Deque是一个线性collection,支持在两端插入和移除元素

    1.2、LinkedList的结构

    //元素个数
    transient int size = 0;
    //第一个元素指针
    transient Node<E> first;
    //最后一个元素指针
    transient Node<E> last;
    //Node节点的结构
    private static class Node<E> {
        E item;//当前元素
        Node<E> next;//当前元素的下一个指针
        Node<E> prev;//当前元素的上一个指针
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    

    1.2.1 Node的结构

    LinkedList结构

    LinkedList特点

    1.LinkedList是通过双链表去实现的。

    2.LinkedList不存在容量不足的问题,因为是链表。

    3.LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法,所以LinkedList可以作为FIFO(先进先出)的队列;LinkedList可以作为LIFO(后进先出)的栈

     二、源码分析

    2.1、添加元素

    //添加元素
    public boolean add(E e) {
        //默认调用,尾部添加元素的方法
        linkLast(e);
        return true;
    }
    //尾部添加元素
    void linkLast(E e) {
        //记录当前尾部元素
        final Node<E> l = last;
        //创建一个新的Node节点 ,prev是当前的尾节点,next指向null
        final Node<E> newNode = new Node<>(l, e, null);
        //将last设置为新节点
        last = newNode;
        //判断当前尾部节点是否为null
        if (l == null)
            //当前尾部节点为null,就挂到头结点上
            first = newNode;
        else
            //当前尾部节点不为null,就将新建的Node挂到当前last节点的next指针上
            l.next = newNode;
        //元素的个数+1
        size++;
        //LinkedList修改记录+1
        modCount++;
    }
    

    新增元素add()方法默认是尾部追加,核心就是将新建的Node节点追加到当前last节点的next指针上 ,伪代码:

    Node newNode=new Node();
    newNode.prev=last;
    last.next=newNode;
    last=newNode;
    last.next=null;

    addFirst:首部追加

    public void addFirst(E e) {
        linkFirst(e);
    }
    //头部追加
    private void linkFirst(E e) {
        //记录当前首部元素
        final Node<E> f = first;
        //新建一个Node节点
        final Node<E> newNode = new Node<>(null, e, f);
        //首部元素指向新建的节点
        first = newNode;
        //判断当前首部指针是否为null
        if (f == null)
            //当前首部指针为null,就把新建的节点挂到last指针上
            last = newNode;
        else
            //当前首部指针不为null,就把新建的节点挂到,当前first指针指向元素的prev指针上
            f.prev = newNode;
        //元素个数+1
        size++;
        //LinkedList修改记录+1
        modCount++;
    }
    

    首部追加的逻辑与尾部追加基本相同,伪代码:

    Node newNode=new Node();
    newNode.next=first;
    first.prev=newNode;
    first=newNode;
    first.prev=null;(也可以:newNode.prev=null)

    指定位置添加元素:add(int index, E element):

    public void add(int index, E element) {
        //检查要插入的位置是否合法
        checkPositionIndex(index);
        //如要插入的位置在最后,直接调用linkLast()
        if (index == size)
            linkLast(element);
        else
            //如要插入的位置不在最后,就先查找再插入
            linkBefore(element, node(index));
    }
     
    //查找要插入元素的位置
    Node<E> node(int index) {
        // assert isElementIndex(index);
        //如果要插入的位置小于集合的一半,我就从头开始找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //如果要插入的位置大于等于集合的一半,我就从尾部开始找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    //将新建的元素插入到查找的元素前面
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    

    LinkedList是一个双向链表,他只记录了头部和尾部位置,如果我们要指定位置插入,他会这么做:

    1.先遍历查找出要插入的元素位置,然后再插入;查找方式是根据 index < (size >> 1) 判断结果,决定是从头遍历,还是从尾部遍历,这种遍历方式类似于二分查找(只在第一层循环二分)

    2.新建一个Node节点,插入到查找出来的元素的前面

    由此可知为何链表对随机位置读写是不合适的;他的时间复杂度=O(n/2) ,如果n很大,我们一般就认为他的时间复杂度=O(n)

    2.2、删除元素

    //重写List的remove()
    public boolean remove(Object o) {
        if (o == null) {
            //如果要删除的元素null元素,从头开始查找这个null元素
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
             //如果要删除的元素不null元素,从头开始查找这个非null元素
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    //执行删除逻辑,实质就是打断改元素与链表的引用关系
    E unlink(Node<E> x) {
        // assert x != null;
        //记录改元素的值,实际作用就是做返回值
        final E element = x.item;
        //记录当前元素的下一个节点
        final Node<E> next = x.next;
        //记录当前元素的上一个节点
        final Node<E> prev = x.prev;
        //判断 x->prev 节点是否为null,为null就是删除头结点 
        if (prev == null) {
            first = next;
        } else {
            //将 x->prev节点的next指针指向x节点的下一个节点
            prev.next = next;
            //将 x->prev 指针,设置为null(断开引用关系)
            x.prev = null;
        }
         //判断 x->next 节点是否为null,为null就是删尾部结点 
        if (next == null) {
            last = prev;
        } else {
            //将x->next节点的prev指针指向x->prev
            next.prev = prev;
            //将 x->next指针,设置为null(断开引用关系)
            x.next = null;
        }
        //将x的值设置为null
        x.item = null;
        //集合大小-1
        size--;
        //集合的修改记录-1
        modCount++;
        return element;
    }
    

    这里我们看到LinkedList重写了List的remove方法,整个删除逻辑也是先查找再删除,时间复杂度O(n),如果是删除首部元素时间复杂度=O(1),若要删除尾部元素请使用removeLast( ) 

    • LinkedLis删除首部元素:removeFirst()
    • LinkedLis删除尾部元素:removeLast()
    • LinkedLis首部出队:pollFirst( ) ,队列的特点
    • LinkedLit尾部出队:pollLast( ),队列的特点

    2.3、迭代器

    Iterator迭代器只能是从头往尾迭代,而LinkedList是双向链表,他还可以从尾往头部迭代,JAVA提供了一个新的迭代器接口:

    public interface ListIterator<E> extends Iterator<E>{
        //判断是否存在下一个元素
        boolean hasNext();
        //获取下一个元素
        E next();
        //判断是否还有前一个元素
        boolean hasPrevious();
        //获取前一个元素
        E previous();
    }
    

    LinkedList实现该接口:

    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;//上一次next() 或者 previous()的元素
        private Node<E> next;//lastReturned->next 指向的元素
        private int nextIndex;//下一个元素的位置
        private int expectedModCount = modCount;
    }
    

    LinkedList从前往后遍历:

    //是否存在下一个元素
    public boolean hasNext() {
        return nextIndex < size;
    }
    public E next() {
        //检查集合的版本
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
        //lastReturned赋值上次next
        lastReturned = next;
        //next赋值为上次next->next
        next = next.next;
        //下一个元素的位置
        nextIndex++;
        return lastReturned.item;
    }
    

    LinkedList从后往前遍历:

    //判断是否到头了
    public boolean hasPrevious() {
        return nextIndex > 0;
    }
    //从尾部往头部取数据
    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
        // next==null:第一次遍历取尾节点(last),或者上一次遍历时把尾节点删除掉了
        // next!=null:已经发生过遍历了,直接取前一个节点即可(next.prev)
        lastReturned = next = (next == null) ? last : next.prev;
        //遍历的指针-1
        nextIndex--;
        return lastReturned.item;
    }
    

    迭代器删除元素:

    public void remove() {
        checkForComodification();
        // lastReturned 是本次迭代需要删除的值
        // lastReturned==null则调用者没有主动执行过 next() 或者 previos(),二直接调remove()
        // lastReturned!=null,是在上次执行 next() 或者 previos()方法时赋的值
        if (lastReturned == null)
            throw new IllegalStateException();
        //保存将当前要删除节点的下一个节点(如果是从尾往头遍历,该值永远是null)
        Node<E> lastNext = lastReturned.next;
        //删除当前节点
        unlink(lastReturned);
     
        // next == lastReturned:从尾到头递归顺序,并且是第一次迭代,并且要删除最后一个元素的情况下,
        // previous() 方法里面设置了 lastReturned = next = last,所以 next 和 lastReturned会相等
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }
    

    三、总结

    LinkedList底层数据结构是双向链表,所以他更适合顺序操作,由于他继承了Deque接口,同时他具有队列的性质,非线程安全的集合

    到这里,本篇关于Java中LinkedList容器的整体结构和使用方法的内容就介绍完了,想要了解更多相关Java容器LinkedList内容,请搜索W3Cschool以前的文章或继续浏览下面的相关文章!