ArrayList源码解析
-
ArrayList 是基于数组的方式来实现数据的增加、删除、修改、查找
1、内部维护了两个变量private transient Object[] elementData ;该数组缓存的集合中的元素，集合的容量就是该数组的长度， elementData 是 transient修饰，说明在序列化时 数组 elementData不在序列化范围内。 private int size; 集合的大小，集合中元素的数量2、 在看看 ArrayList的构造器
构造一个指定容量的 initialCapacity 的空的集合 super调用的 AbstractList的默认构造方法， 该方法是一个空的方法 然后判断传入的参数不能小于 0否则就跑出非法参数异常， 然后直接创建了一个 长度为 initialCapacity的数组对象，并将该对象赋值给当前实例的 elementData属性，用以存放集合中元素 public ArrayList(int initialCapacity){ super(); if(initialCapacity<0){ throw new IllegalArgumentException("Illegal Capacity initialCapacity") } this.elementData=new Object[initialCapacity]; } public ArrayList(){ this{10}} 构造一个默认为 10的空的集合 再来看一个包含指定集合 中的所有元素的集合，该集合中元素的顺序是以 的迭代器返回元素的顺序 public ArrayList(Collection<? extend E> c) { elementData=c.toArray(); size=elementData.length; if(elementData.getClass!=Object[].class) { elementData=Arrays.copyof(elementData,size,Object[].class); } }3、从上面的源码中 看到是先将 c.toArray()方法返回赋值给 elementData，将大小赋值给 size，然后进行判断 如果为 true，调用 Arras.copy方法创建一个新的 Object[]新数组，将 elementData 中元素 copy 到新 Object
数组中 然后赋值给 elementData()4、add()方法
插入对象 首先将 size+1，缠上一个 minCapacity的变量，调用 ensureCapacity（ minCapacity） 方法保证数组插入一个元素时有可用的容量，然后将元素 放到 elementData的 size位置，size+1 public boolean add(E e){ ensureCapacity(size+1); elementData[size++]=e; return true; } public void ensureCapacity(int minCapacity){ modCount++; int oldCapacity=elementData.length; if(minCapacity>oldCapacity){ Object[] oldData=elementData; int newCapacity=(oldCapacity*3)/2+1; if(newCapacity<minCapacity) newCapacity=minCapacity; elementData=Arrays.copy(elementData,newCapacity); } } 必要时数组的扩容，首先将 modCoun+1 modeCount 表示修改数组结构次数，如果传入的 minCapacity大于目前 elementData的容量则将容量扩展到 （oldCapacity*3）/2+1若此时容量仍然小于 minCapacity，直接将 minCapacity设置为最新的容量， 最后使用 Arrays的 copy方法到新的数组中 并将新数组赋值给 elementData. 在指定下表 index处插入 element首先判断下标 index 的参数是否有效，否则跑出异常，然后调用 ensureCapacity(size+1)要确保有足够容量来插入数据，然后调用 System.arraycopy 从 index 开始，将 elementData 数组元素 copy到从 index+1 开始的地方，copy 的长度为 size-index,这样 index下标出的位置就空出来了，然后将元素 element 放到下标为 index处的位置，最后将 size++ public void add(int index,E element){ if(index>size || index<0){ throw new IndexOutOfBoundsException("Index"+index+",Size:"+size); } ensureCapacity(size+1); 这一步是扩容 Systim.arraycopy(elementData,index,elementData,index+1,size-index); elementData[index]=element; size++; }5、删除方法
删除指定元素，分为两种情况， 若指定的元素为 null，则遍历当前的 elementData 数组，如果某一个下标 index的值为 null，则调用方法 fastRemove 删除元素， 如果指定的不为 null，则遍历 若某一个 index 下标处的元素和 o 进行 equals则快速删除元素 但是只能删除第一个出现的元素 快速删除是 将 index后面的元素往前复制一位 ，这样就达到删除的目的
image.png
6、查找方法
查找非常简单，(这里不粘代码了 在下面和LinkedList对比起来看)
-
注意
ArrayList是基于数组的方式实现的， 所以查找效率高，但是每次插入或者删除元素，都要大 量的移动元素，所以效率很低， 这里面主要涉及几个重要的方法 一个是减小数组的容量 就是讲当前数组的容量缩小为实际存储的容量trimToSize,还有一个就是扩容，如果容量不够，就设置新的容量为旧的容量的 1.5倍加1，因此建议能够事先确定元素数量的情况下用ArrayList（数组都是这样的特征）
LinkedList源码解析
-
LinkedList** 继承结构开始分析
public class LinkedList<E> extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList是 一个继承于 AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列
列进 行操作。
LinkedList实现 List接 口，能对它进行队列操作。
LinkedList实现 Deque接 口，双向队列它 支持从两个端点 方向检索和插 入元素。
LinkedList实现了了Cloneable接 口，即覆盖了了函数 clone()，能克隆
LinkedList实现 java.io.Serializable 接 口，这意味着 LinkedList支持序列化，能通过序列化去传输。 -
LinkedList属性
关键字 transient 标识的字段的 生命周期仅存于调 用者的内存中 而不不会写到磁盘 里里持久化transient int size = 0; /** *Pointer to first node. *Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; transient Node<E> last; LinkedList每个存储元素是 一个 Node对象 private static class Node<E> { Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 在这个对象可以分析出LinkedList存储开销比 Arraylist大因为 LinkedList每个元素在内存里里多分配了了Node next; , Node prev;两个变量值得出ArrayList 和 LinkedList 存储相同 大 小的数据LinkedList占内存 比较 大 -
LinkedList 构造方法
public LinkedList(Collection<? extends E> c) { this(); addAll(c); } return addAll(size, c);开始分析.参数 1.添加位置 , 参数 2,需要添加的数据; public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; 上部分校验数据是否为0但是少了了空指针校验 Node<E> pred, succ; if (index == size) { 保存index处的节点。插 入位置如果是size，则在头结点前 面插 入，否则在获取 index处的节点插 入succ = null; pred = last; } else { 获取前 一个节点，插 入时需要修改这个节点的next引 用 succ = node(index); pred = succ.prev; } 可以理理解node摆放的位置 for (Object o : a) { 在强制类型转换的时候编译器 会给出警告@SuppressWarnings("unchecked")此注解去除警告 @SuppressWarnings("unchecked") E e = (E) o; 创建node参数1.node头参数2.数据参数3.node尾 Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else 修改前 一节点的next指针 pred.next = newNode; pred = newNode; } 收尾的处理理 if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
LinkedList初始化操作 会处理理一 大坨的头尾地址转换ArrayList初始化操作 会不不断的 copy数组为了了
Arrays.copyOf(elementData, size, Object[].class);
（说明 这些东西原来在world上写的 复制过来格式全部变了 所以我就截图了）
-
LinkedList 添加元素
image.png
linkLast方法
image.png
linkBefore方法(按指定位置插)
image.png
LinkedList 添加 又是 处理理 头--尾.地址转换
ArrayList 添加 又会 copy 数组.为了了 自增
image.png
-
LinkedList 删除元素
image.png
unlink方法
删除节点 把节点的.所有属性指 null
image.png
LinkedList 删除元素.先把 自 己的东 西给别 人.然后 自 己指空.
ArrayList 删除元素.还是操作 Copy 数组
image.png
-
LinkedList 获取元素
image.png
node方法
image.png
LinkedList 获取元素.需要 用循环找
ArrayList 获取元素 直接 index 下标查找
image.png
-
上面的源码分析是对上一篇的线性表的一个扩展，因为ArrayList和LinkedList就是用的顺序存储结构和链式存储结构的，好了 先到这里 大家有什么疑问或者哪里写的不对 可以指正。
网友评论