欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java:LinkedList源码分析

程序员文章站 2022-07-14 16:16:55
...

引言

LinkedListJava集合中重要的一个实现,其底层才用双向链表结构。和ArrayList一样,LinkedList也支持空值和重复值。由于LinkedList底层基于链表实现,存储过程中,无需像ArrayList那样进行扩容.但有得必有失,LinkedList存储元素的节点需要额外的空间前驱和后继的引用.另外,LinkedList在头部和尾部插入效率比较高,但是在制定位置进行插入时,效率一般.原因是,在指定位置插入需要定位到该位置处的节点,此操作的时间复杂度为O(N)。最后,LinkedList是非线程安全的集合类,并发环境下,多个线程同时操作LinkeList,会引发不可预知的错误.

结构体系

从结构体系我们可以大致其总结特性:

  • 实现了List接口,提供了对数据的增删查该功能
  • 实现了Deque接口,可用于双端队列
  • 实现了Cloneable接口,可被浅拷贝
  • 实现了Serializable接口,可被序列化

属性

 transient int size = 0; //表示元素的个数
 transient Node<E> first;//1.8中 结构是双向链表,所以这是头结点
 transient Node<E> last; //尾节点
复制代码

构造函数

  • 无参构造函数
     public LinkedList() {
        }
    复制代码
    啥也不干。
  • 带集合参数的构造函数
      public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
        
        public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    //可以将addAll方法理解成一个插入方法 index即为准备插入节点下标
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); //检查下标 区间为 0到size
    
        Object[] a = c.toArray();  //调用集合的toArray()方法将其转化为数组
        int numNew = a.length; //获取数组的长度
        if (numNew == 0) //长度为0 直接返回 表示addAll失败
            return false;
    
        Node<E> pred, succ; //prev表示前置节点 succ表示后置节点
        if (index == size) { //如果是在尾部插入
            succ = null; 后置节点为null
            pred = last; 前置节点为最后一个
        } else {
            succ = node(index); //后置节点为index对应的节点 
            pred = succ.prev; //前置节点为 index对应节点的前一个
        }
    
        for (Object o : a) { //增强for循环 代码更加简介
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null); //实例节点的时候赋值前置节点以及元素
            if (pred == null) //如果前置节点为空,则该节点为头结点
                first = newNode; 
            else
                pred.next = newNode; //否则的话设置新节点为前置节点的下一个节点
            pred = newNode; //将当前的节点作为新的前置节点
        }
        //遍历完成后 需要将最后一个节点与后置节点连接
        if (succ == null) { //如果后置节点为null 则表示最后一个节点即为尾部节点
            last = pred;
        } else { //否则,将最后一个节点与尾部连接
            pred.next = succ;
            succ.prev = pred;
        }
    
        size += numNew; //更新元素的大小
        modCount++; //修改更改的次数
        return true; //返回true表示更新成功
    }
    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }
    复制代码

增加元素

  • add(E e)
    public boolean add(E e) {
            linkLast(e);
            return true;
        }
        
        void linkLast(E e) {
        final Node<E> l = last; //得到last节点
        final Node<E> newNode = new Node<>(l, e, null); //新建连接左边连接last节点
        last = newNode; //将新的节点赋值给last
        if (l == null) //如果 最初的last节点为空 则 当前节点为头结点
            first = newNode;
        else
            l.next = newNode; //否则 将新节点与最初的last节点相连
        size++; //增加元素个数
        modCount++; //增加修改次数
    }
    复制代码
    该方法比较比较简单,只是创建了一个新节点插入在了链表的尾部而已.
  • add(int index, E element),可以把该方法当做单个插入的方法
    public void add(int index, E element) {
            checkPositionIndex(index); //检查下标是否合法
    
            if (index == size) //如果是在尾部,插入在尾部即可
                linkLast(element);
            else //否则,插在node(index)节点之前
                linkBefore(element, node(index));
        }
        
        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) //连接前面 如果前置节点为null 则将当前节点设置为头节点
            first = newNode;
        else //否则与前置节点相连接
            pred.next = newNode;
        size++;
        modCount++;
    }
    复制代码

获取元素

  • get(int index)
    public E get(int index) {
            checkElementIndex(index); //检查下标是否合法
            return node(index).item; //只杰根据node方法查找到节点并返回其元素即可
        }
         Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) { //位运算 表示 index<size/2 即偏向头结点
                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;
            }
        }
    复制代码
    可以看到,双向链表在这里起到的作用,在查找的时候,先根据index判断节点更靠近头部还是尾部,提升查找的效率。

删除元素

  • remove(int index)
    public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
        
        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;
    
            if (prev == null) {/表示移除的为头结点
                first = next; 
            } else { 
                prev.next = next;
                x.prev = null; 
            }
    
            if (next == null) { 
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
    复制代码
    检查下标合法后,直接调用unlink方法将该节点移除.在unlink方法中可以看到,将被移除的节点的前后节点以及元素都赋值为null,方便GC回收.

修改元素

  • set(int index, E element)
    public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
    复制代码

也很简单,不再赘述,现实用node(int index)方法定位到对应节点,然后修改其值即可。

LinkedList总结

  • 底层使用链表进行数据存储,不需要扩容
  • 增加和删除元素效率比较高,执行相应的链表操作即可
  • 查找和修改的效率比较低,虽然遍历之前根据下标判断了遍历起点,但是节点比较多的时候,效率会大幅缩减