Java教程

ArrayList和LinkedList源码分析

本文主要是介绍ArrayList和LinkedList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

ArrayList

构造方法:

  • 默认构造方法:ArrayList()
    1、将空的Object数组赋值给elementData
  • 设定集合大小构造方法:ArrayList(int initialCapacity)
    1、判断initialCapacity < 0, 抛异常,
    2、initialCapacity > 0 ,给elementData创建对应大小的Object数组
    3、initialCapacity == 0,给elementData赋值一个空的Object数组
  • 传入一个集合构造方法:ArrayList(Collection<? extends E> c)
    1、先将传入的Collection对象转成数组,赋值给elementData
    2、判断elementData.length == 0, 给elementData赋值空数组
    3、判断elementData.length != 0, 接着会重新copy一个与1操作相同的数组

add(E e)添加元素

1、首先拿到当前elementData的数组大小记为size
2、接着,如果elementData数组为空数组,则会将size + 1 与 默认大小DEFAULT_CAPACITY = 10 取最大值,如果里面存有元素,则不会进行比较后赋值
在这里插入图片描述

3、只有当数组满载情况下会触发扩容算法 (elementData数组有元素时minCapacity = elementData.length + 1,elementData为空数组时,minCapacity = 10)
在这里插入图片描述
4、扩充集合容器算法:拿到当前elementData数组大小通过右移1位位运算后 + elementData数组大小,记为newCapacity(新容器容量)。如果newCapacity < minCapacity(默认容量 或者 当前elementData数组大小 + 1) 会将 minCapacity 赋值给 newCapacity。容器的最大容量为Integer.MAX_VALUE - 8,如果预设定的容量 > 最大值,则强制设为最大值。定好容器容量后copy一个新容量的数组并将之前老的元素存储到新数组中。
在这里插入图片描述
5、容器扩容完后,进行添加元素到新数组中
在这里插入图片描述

add(int index , E element)

1、首先会检查插入的角标是否合法,如果角标 > 数组长度 或者 角标 < 0,都会报角标越界异常
2、同样扩容规则和add(E e)的扩容规则一致
3、通过System.arraycopy(Object[] src, int srcPos, Object[] dest, int destPos, int length),方法进行拷贝,srcPos从指定原数组位置开始取元素,destPos从目标数组位置开始存元素,length取的元素长度,之后将得到新数组后,会预留指定元素位置用于插入新值
在这里插入图片描述在这里插入图片描述

remove(int index)

1、先检查下标合法性
2、取出移除指定位置的元素,用于返回给客户端
3、同样移除操作也是借助于System.arraycopy()方法进行复制操作
4、操作完后,将数组大小进行–size,然后把最后一个元素置空等待GC回收内存
在这里插入图片描述

remove(Object o)

1、该方法与remove(int index)方法移除的逻辑大致相同
2、根据指定的object去移除元素,是先根据指定的object找到在数组中的下标,之后再通过下标去移除元素
在这里插入图片描述
在这里插入图片描述

LinkedList

构造方法

  • 默认构造方法LinkedList():空实现
  • 传参构造方法LinkedList(Collection<? extends E> c):会调用默认构造方法,然后在调用addAll()将c集合添加进去

LinkedList.add(E e)方法

1、内部调用了LinkedList.linkLast(E e)
2、跟进linkLast(E e):
----a、定义一个节点l(作用类似交换2个变量的temp变量)用于记录last节点指向的节点,可进行后面newNode(新插入元素节点)插入位置的确定。同时把l节点指向last节点(作用可在步骤f查看)
----b、接着创建一个newNode节点,并为newNode指定前一个节点为l。接着把last节点单指向newNode节点(作用可在步骤e、f查看)
----c、如果当前集合是空的,那么直接将first节点指向newNode节点。
----d、如果在插入之前集合存在元素,那么步骤b已经确定了newNode节点的前一个节点为l,接下来设置l的下一个节点是newNode节点,这样就确定了l节点和newNode节点的位置关系。
----e、由于在步骤b结束后,会重新让last节点指向newNode节点,那么在步骤d结束后,确定了newNode节点位置,于此同时last的位置也已确定。
----f、l节点位置的确定:在该方法一开始就让l节点指向上一次添加到集合中元素的节点位置及last节点,而每次添加元素时,last节点是位置已经确定。
在这里插入图片描述

3、例:第一次插入元素,那么last节点指向newNode节点,然后让first指向newNode节点,即newNode节点位置已经确定好同时last节点指向newNode节点,所以last节点也确定位置。接着插入第二个元素时,last节点指向第一个已经确定的位置,并让l节点指向last,致使l节点的位置也确定,通过步骤d操作就确定了newNode节点的位置,后面插入元素以此类推

4、添加元素的流程图:
在这里插入图片描述

LinkedList.addAll(Collection<? extends E> c)

1、该方法内部调用addAll(int index,Collection<? extends E> c)
2、继续跟进:如果当前集合不为空时,调用了node(int index),其内部是进行二分法查找(由此发现,LinkedList查找元素性能低),找到指定位置的节点,目的是在后面进行设置指定节点与插入元素的一个位置关系。
在这里插入图片描述

3、确定了插入元素节点的前一个节点,然后进行遍历插入的集合元素,并且对元素节点建立链关系(建立链关系与add(E e)方式雷同)
在这里插入图片描述

LinkedList.remove(int index)

1、删除原理:同样是通过调用node(int index)进行二分法查找指定位置的元素节点,然后开始对指定的节点进行断链、置null,然后让分开的两段链相互链接形成一个整链,最后使其成为孤立的null对象,最后由GC回收。
2、在remove(int index)中调用了unlink(Node<E> x),该方法是做了断链、置空、连接链操作
在这里插入图片描述

总结

  • ArrayList:底层是数组实现的,默认容器容量为10,动态扩容算法是当数组长度达最大时,继续添加元素,扩大容量是以原数组的容量的1.5倍扩大创建一个新的数组,然后将原有的元素复制到新数组中。删除元素,从需要删除的元素位置开始,遍历数组,将后面的元素从删除位置开始重新赋值,将数组末尾元素置空,让GC回收,来达到删除目的。由此可见,ArrayList集合在增删效率上比较差,由于底层数组,查找可直接通过索引去取,所以查找会逊色一点。
  • LinkedList:底层是链表数据结构,既然是链表,那么集合不存在扩容一说,插入和删除元素只需要断链、再合链即可。如果是插入/删除指定位置,那么首先需要通过二分法进行查找指定位置的元素,然后再对其进行锻炼、再合链等操作。由此可见LinkedList集合在查找性能上会较低,在增删(非指定位置)效率上会逊色一点。

补充:
1、<< 左移1位 => 原数 * 2,左移2位 => 原数 * 2 * 2…以此类推(左移 右边添0)
2、>> 右移1位 => 原数 / 2 取整,右移2位 => 原数 / 2 / 2… 以此类推(右移 左边添0)

这篇关于ArrayList和LinkedList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!