Arraylist

ArrayList 的工作原理ArrayList has 是一个外部的一般数组，它充当数据存储。在大多数情况下，咱们不指定列表的确切大小。然而外部数组必须有一些大小！它的确如此。 它的默认大小是 10 。 public static void main(String[] args) { ArrayList<Car> cars = new ArrayList<>();}复制代码首先，让咱们看看增加新元素是什么样的。首要任务是查看 外部数组在外部数组中是否有足够的空间， 以及是否可能再放一个元素。如果有空间，则将新元素增加到列表的开端。当咱们说“到最初”时，咱们并不是指数组中的最初一个地位（那会很奇怪）。咱们指的是最初一个以后元素之后的地位。它的索引将是 cars.size() 。咱们的列表目前是空的 ( cars.size() == 0 )。因此，新元素将被增加到地位 0。 ArrayList<Car> cars = new ArrayList<>();Car ferrari = new Car("Ferrari 360 Spider");cars.add(ferrari);复制代码这很明显。如果咱们在两头插入会发生什么，即在其余元素之间？ public static void main(String[] args) { ArrayList<Car> cars = new ArrayList<>(); Car ferrari = new Car("Ferrari 360 Spider"); Car bugatti = new Car("Bugatti Veyron"); Car lambo = new Car("Lamborghini Diablo"); Car ford = new Car("Ford Modneo"); cars.add(ferrari); cars.add(bugatti); cars.add(lambo); cars.add(1, ford);// add ford to cell 1, which is already occupied}复制代码同样，首先查看数组中是否有足够的空间。如果有足够的空间，则 元素向右移动 ，从咱们插入新元素的地位开始。咱们在地位 1 插入。换句话说，从地位 3 的元素被复制到地位 4，元素 2 到地位 3，元素 1 到地位 2。 ...

1. 什么是线性表对于线性表的概念以及LinkedList和ArrayList的区别能够参考上篇文章。 Segment Fault Bugkit 上面咱们间接看看如何用Java实现ArrayList 2. java实现其中的抽象类AbstractList和接口List也是本人定义的，如须要看残缺代码，能够到文末的Github查看残缺代码。/** * @param <E> Type of element * @author bugkit * @since 2021.10.27 */public class ArrayList<E> extends AbstractList<E> implements List<E> { // 存储元素的数组 private E[] data; // 元素的默认容量，最多只能装8个 private int capacity = 8; // 创立容量为8的数组 public ArrayList() { data = (E[]) new Object[capacity]; } // 创立容量为传入参数大小的数组 public ArrayList(int capacity) { this.capacity = capacity; data = (E[]) new Object[capacity]; } // 获取在data数组中的第i个元素 @Override public E get(int i) { if (i >= size) { throw new IndexOutOfBoundsException("Index " + i + " is out of range " + size); } return data[i]; } // 移除在data数组中的第i个元素 @Override public E remove(int i) { if (i >= size) { throw new IndexOutOfBoundsException("Index " + i + " is out of range " + size); } E e = data[i]; System.arraycopy(data, i + 1, data, i, size - i); size--; return e; } // 在data数组的第i个地位插入新的元素，如果i大于以后元素的个数则会报错数组越界 @Override public boolean add(E e, int i) { if (i > size) { throw new IndexOutOfBoundsException("Index " + i + " is out of range " + size); } if (size == capacity - 1) { resize(); } if (size + 1 - i >= 0) System.arraycopy(data, i, data, i + 1, size + 1 - i); data[i] = e; size++; return true; } // 增加元素到开端 @Override public boolean add(E e) { return add(e, size); } // 移除特定元素，如果元素存在则移除该元素并返回true，否则返回false @Override public boolean remove(E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { remove(i); return true; } } return false; } // 判断ArrayList是否存在元素e @Override public boolean contains(E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return true; } } return false; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("ArrayList { "); for (int i = 0; i < size; i++) { sb.append(data[i]).append(", "); } sb.replace(sb.length() - 1, sb.length(),"").append(" }"); return sb.toString(); } // 扩容，当add元素后，size == capacity，则会将ArrayList扩容为原来的两倍， // 并将原来的元素按程序拷贝到新的data数组 private void resize() { capacity = capacity * 2; E[] newData = (E[]) new Object[capacity]; System.arraycopy(data, 0, newData, 0, size); data = newData; }}

和 LinkedList的区别：ArrayList： 底层是动静数组，反对扩容，线程不平安。对于增加和删除办法，如果是增加到列表尾部，工夫复杂度是O(1)；如果是增加到指定地位i，工夫复杂度就是O(n-i)，因为须要将后续数组的元素往后挪动一位；对于疾速随机拜访get(i),工夫复杂度是O(1)。LinkedList: 双向链表构造，线程不平安。对于增加和删除办法，如果是增加到列表尾部，因为是间接操作最初一个last节点，所以是O(1)；如果是增加到指定地位i，因为须要先挪动到链表的指定地位，所以工夫复杂度是O(i)；不反对疾速随机拜访，工夫复杂度O(n)。所以一般来说，因为反对疾速随机拜访，所以在查问元素方面，ArrayList有劣势，相同的，在增加和删除元素方面，LinkedList不须要挪动数据，所以更有劣势。当然这不是相对的，因为LinkedList也须要先遍历到指定地位（开端节点除外），具体应用还是须要依据理论业务场景来综合考量。 外围源码解析public class ArrayList<E> { private static final long serialVersionUID = 8683452581122892189L; /** * 默认初始容量 */ private static final int DEFAULT_CAPACITY = 10; /** * 用于指定大小为0的空实例时的数组实例. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 用于默认大小的空实例的共享空数组实例。 * 将它与 EMPTY_ELEMENTDATA 辨别开来，以理解增加第一个元素时要收缩多少 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 存储ArrayList元素的数组缓冲区。 * * ArrayList 的容量就是这个数组缓冲区的长度。任何带有 * elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的 * 空 ArrayList增加第一个元素时将扩大为 DEFAULT_CAPACITY 大小。 */ transient Object[] elementData; /** * ArrayList 的大小（它蕴含的元素数） */ private int size; /** * 记录List对象被批改的次数，List对象每批改一次，modCount都会加1. */ protected transient int modCount = 0; /** * 有参构造函数，结构一个具备指定初始容量的数组. */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 无参构造函数，结构一个初始容量为 10 的空数组（当增加第一个元素时才为10） * * 有参大小为0和无参的构造函数应用的空数组不一样，前者是EMPTY_ELEMENTDATA，后者是DEFAULTCAPACITY_EMPTY_ELEMENTDATA */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 依照汇合的迭代器返回的程序结构一个蕴含指定汇合元素的数组 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { //这里，例如当应用Arrays.asList来构建c时，c.toArray().getClass()的后果就不是Object[].class了，而是String[].class //如果是这种状况，就须要将非Object数组类型的elementData转成Object数据类型 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } } /** * 将ArrayList实例的容量修剪为列表的以后大小。 * 应用程序能够应用此操作来最小化实例的存储 */ public void trimToSize() { modCount++; //size是数组中理论元素的个数，而elementData.length代表的是数组的大小 if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); //顺便提一下，Arrays.copyOf办法是创立一个大小为size的新数组，依照size和elementData.length中更小的单位复制elementData中的元素。 //当然，如果传入的size大于elementData.length话，也就相当于扩容，反之则是裁剪 } } /** * 扩容机制 * * 减少实例的容量，如果必要，以确保它至多能够包容元素的数量 * 由最小容量参数指定 * @param minCapacity 所需最小容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 这里要阐明一下，只有在创立不指定大小的空实例时，扩容才会用到默认初始容量DEFAULT_CAPACITY ? 0 : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } /** * 先判断数组缓冲区是不是没有增加过元素，如果是，则返回设置容量和默认初始容量的最大值 * @param elementData * @param minCapacity * @return */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果要扩容的数组大小大于缓冲数组的大小，才能够执行扩容，否则不会扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } /** * 要调配的数组的最大大小 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 扩容机制具体实现 */ private void grow(int minCapacity) { int oldCapacity = elementData.length; // >> 1 意思是获取旧数组的一半长度，扩容相当于将数组长度扩大成原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //如果还是小于最小容量，则间接把最小容量作为新容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 依照新容量扩容 elementData = Arrays.copyOf(elementData, newCapacity); } /** * 比拟 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE， * 否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8 */ private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } /** * 返回此列表中的元素数 * */ public int size() { return size; } /** * 如果此列表不蕴含元素，则返回 true * */ public boolean isEmpty() { return size == 0; } /** * 如果此列表蕴含指定的元素，则返回true */ public boolean contains(Object o) { return indexOf(o) >= 0; } /** * 返回指定元素第一次呈现的索引，如果此列表不蕴含该元素，则为 -1 */ public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; } /** * 返回指定元素最初一次呈现的索引,如果此列表不蕴含该元素，则为 -1 */ public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null) return i; } else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i])) return i; } return -1; } /** * 返回此实例的浅拷贝。 （元素自身不会被复制。） */ public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } } /** * 以适当的程序（从第一个元素到最初一个元素）返回一个蕴含此列表中所有元素的数组 * 返回的数组将是“平安的”，因为列表实例没有对它的援用。（换句话说，这个办法调配了 * 一个新数组），因而调用者能够自在地批改返回的数组。 */ public Object[] toArray() { return Arrays.copyOf(elementData, size); } /** * 以适当的形式返回蕴含此列表中所有元素的数组序列（从第一个元素到最初一个元素）； * 返回的运行时类型数组是指定数组的数组； * 如果列表合乎指定的数组，它在其中返回； * 否则，应用指定数组的运行时类型和大小调配一个新数组。 * * 如果列表适宜指定的数组并有残余空间（即，数组的元素比列表多）， * 紧跟在汇合开端之后的数组被设置为空。 * （这在确定长度时很有用，如果调用者晓得列表不蕴含任何空元素。） */ @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); System.arraycopy(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; } @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; } /** * 返回此列表中指定地位的元素 */ public E get(int index) { rangeCheck(index); return elementData(index); } /** * 将此列表中指定地位的元素替换为指定的元素。 */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } /** * 将指定的元素附加到此列表的开端。 */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * 在此指定地位插入指定元素。 * 挪动以后在该地位的元素（如果有）和左边的任何后续元素（在它们的索引上加一）。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } /** * 移除此列表中指定地位的元素。 * 将任何后续元素向左挪动（从它们的元素中减去一个） */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } /** * 从此列表中删除第一次呈现的指定元素（如果它存在）； * 如果列表不蕴含该元素，则为不变。 */ public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /** * 跳过边界查看且不执行的公有删除办法 */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work } /** * 从此列表中删除所有元素。 * 该列表在调用返回后将会为空。 */ public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; } /** * 将指定汇合中的所有元素追加到开端（依照它们指定汇合的迭代器返回的程序）。 * */ public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } /** * 将指定汇合中的所有元素插入到此列表，从指定地位开始。 * */ public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; } /** * 从此列表中删除索引介于两者之间的所有元素 * */ protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; } /** * 查看给定的索引是否在范畴内 */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * add 和 addAll 应用的 rangeCheck 版本. */ private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * 结构一个 IndexOutOfBoundsException 具体音讯 */ private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } /** * 从此列表中删除指定汇合的所有元素 * */ public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } /** * 仅保留此列表中蕴含在指定汇合中的元素. * */ public boolean retainAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, true); } private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }}

概述（1）ArrayList 是一种变长的汇合类，基于定长数组实现。 （2）ArrayList 容许空值和反复元素，增加元素时，会扩容机制生成一个更大的数组。 （3）能够保障在 O(1) 复杂度下实现随机查找操作。 （4）ArrayList 是非线程安全类。 为谋求效率，ArrayList没有实现同步（synchronized），如果须要多个线程并发拜访，用户能够手动同步，也可应用Vector代替。类的属性 /** * 默认初始容量 */private static final int DEFAULT_CAPACITY = 10;/** * 共享的空数组实例，用于空实例 */private static final Object[] EMPTY_ELEMENTDATA = {};/** *ArrayList 理论数据存储的一个数组 *存储ArrayList的元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。 *增加第一个元素时，任何具备elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩大为DEFAULT_CAPACITY。 Object[]数组，也就是说该数组能够放任何对象（所有对象都继承自父类Object） */transient Object[] elementData;/** * 共享的空数组实例，用于默认大小的空实例 */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/** * elementData 的大小，size是逻辑长度，并不是数组长度。 */private int size;//很有意思，上面介绍protected transient int modCount = 0;static润饰的变量，常驻于办法区，咱们不须要new，JVM会提前给咱们初始化好，这个个性在理论开发过程中，常常拿来做缓存。 ArrayList new的时候思考了缓存，为了防止咱们重复的创立无用数组，所有新new进去的ArrayList底层数组都指向缓存在办法区里的Object[]数组。 构造方法 //参数为初始化容量public ArrayList(int initialCapacity) { //判断容量的合法性 if (initialCapacity > 0) { //elementData才是理论寄存元素的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //如果传递的长度为0，就是间接应用本人曾经定义的成员变量(一个空数组) this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} //无参结构，应用默认的size为10的空数组，在构造方法中没有对数组长度进行设置，会在后续调用add办法的时候进行扩容public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} //将一个参数为Collection的汇合转变为ArrayList（实际上就是将汇合中的元素换为了数组的模式）。//传入的汇合为null会抛出空指针异样（调用c.toArray()办法的时候）public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { //c.toArray()可能不会正确地返回一个 Object[]数组，那么应用Arrays.copyOf()办法 if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { //如果汇合转换为数组之后数组长度为0，就间接应用本人的空成员变量初始化elementData this.elementData = EMPTY_ELEMENTDATA; }} ...

Jdk8 总结 扩容和删除 ArrayList 就是一个实现了List接口的可主动扩容的数组，当增加元素的时候它会尝试扩容,扩容的规范是变为原来的1.5倍**，当删除元素的时候，它会左移元素，防止数组呈现"空位"容量 new ArrayList<>() 初始化容量为0，等到第一次add的时候再初始化为10有序汇合能够存储反复值和null值 示例： public static void main(String[] args) { List<String> a=new ArrayList<>(); a.add(null); a.add(null); a.add(null); System.out.println(a.size()); } 输入： 3ArrayList 是疾速失败的，在遍历的同时当汇合被批改后会抛出ConcurrentModificationException，能够应用Iterator 的删除办法来防止这个问题非线程平安的，如果你想在多线程环境中应用，能够应用Vector 或者它的线程平安包装类扩大 操作系统的局部性原理，数组的间断存储空间的个性充沛应用了局部性原理，也就是说硬件的高速缓存减速了数组的拜访性能Adding an element- 如果你应用的是  add(E e) 办法增加一个元素到ArrayList开端 ，它的工夫复杂度 O(1)；然而当空间有余引发扩容的时候，会导致新建数组而后拷贝数据，这个时候它的工夫复杂度 O(n) ;当你应用 add(int index, E element)的时候它的算法复杂度是 O(n - index) 也就是 O(n)Retrieving an element- 当你应用get(int index) 的时候，它的工夫复杂度是 O(1)，因为数组能够间接依据下标进行定位Removing an element- 当你应用 remove(int index) 它的工夫复杂度是 O(n - index) ，因为它波及到挪动元素Traverse - 遍历的工夫工夫复杂度是O(n),也就是依赖于Capacity 的大小，如果你比拟器重遍历的性能，就请不要不要给它设置一个很大的初始容量UML底层是一个Object[]，增加到ArrayList中的数据保留在了elementData属性中。 当调用new ArrayList<>()时，将一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA  赋值给了elementData，这个时候汇合的长度size为默认长度0例如当调用new ArrayList<>(100)时，依据传入的长度，new一个Object[100]赋值给elementData，当然如果玩儿的话，传了一个0，那么将一个空数组 EMPTY_ELEMENTDATA 赋值给了elementData例如当调用new ArrayList<>(new HashSet())时，依据源码，咱们可知，能够传递任何实现了Collection接口的类，将传递的汇合调用toArray()办法转为数组内赋值给elementData构造方法 ...

arraylist线程不平安底层是数组反对快速访问randomAccess尾部有空余空间在尾减少删除工夫复杂度都是O(1)，在指定地位减少删除工夫复杂度是O(n)，因为要一个一个挪JDK7 new无参结构的ArrayList对象时，间接创立了长度是10的Object[]数组elementData 。jdk7中的ArrayList的对象的创立相似于单例的饿汉式，而jdk8中的ArrayList的对象的创立相似于单例的懒汉式。 扩容过程未指定初始容量的arraylist创立进去，容量是0add元素进来时，判断外部容量是否足够（外部容量>以后size+1）判断外部容量是否足够n时，如果arraylist是空的，将容量裁减到max（10，n），如果arraylist不是空的，看看容量够不够n，不够就扩容到n扩容到n时，利用位运算将旧容量扩容到1.5倍，新容量=max（1.5倍旧容量，n）。如果max（1.5倍旧容量，n）>maxInteger-8 && n>maxInteger-8，新容量=maxInteger如果max（1.5倍旧容量，n）>maxInteger-8 && n<maxInteger-8，新容量=maxInteger-8 java 中的 length属性是针对数组说的,比如说你申明了一个数组,想晓得这个数组的长度则用到了 length 这个属性.java 中的 length() 办法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个办法.java 中的 size() 办法是针对泛型汇合说的,如果想看这个泛型有多少个元素,就调用此办法来查看! 在此列表中的指定地位插入指定的元素。先调用 rangeCheckForAdd 对index进行界线查看；而后调用 ensureCapacityInternal 办法保障capacity足够大；再将从index开始之后的所有成员后移一个地位；将element插入index地位；最初size加1。 System.arraycopy()是一个 native 办法,用来add的时候一个一个挪 /*** 复制数组* @param src 源数组* @param srcPos 源数组中的起始地位* @param dest 指标数组* @param destPos 指标数组中的起始地位* @param length 要复制的数组元素的数量*/public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length); 把src数组，在第srcPos地位插入新数据，后边的挨个挪一个 Arrays.copyOf()办法 申请一个新的数组。调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组 ensureCapacity办法，如有必要，减少此 ArrayList 实例的容量，以确保它至多能够包容由minimum capacity参数指定的元素数。最好在 add 大量元素之前用 ensureCapacity 办法，以缩小增量重新分配的次数 ...

面试官Q1：能够手写一个ArrayList的简略实现吗？ 咱们都晓得ArrayList是基于数组实现，如果让你实现JDK源码ArrayList中add()、remove()、get()办法，你晓得如何实现吗？这一节，咱们不看源码，咱们想想如何简略的实现ArrayList几个根本办法？ 确定数据结构咱们晓得，ArrayList中无论什么数据都能放，是不是意味着它是一个Object类型，既然是数组，那么是不是Object[]数组类型的？所以咱们定义的数据结构如下： private Object[] elementData; private int size;设置自定义的MyArrayList的长度为10 public MyArrayList(){ this(10); } public MyArrayList(int initialCapacity){ if(initialCapacity<0){ try { throw new Exception(); } catch (Exception e) { e.printStackTrace(); } } elementData = new Object[initialCapacity]; }有了存放数据的地位，接下来，咱们想想如何将数据放入数组？ 增加数据public void add(Object obj){ elementData[size++]=obj;}每增加一个元素，size就会自增1，咱们定义的数组长度为10，当咱们增加到11个元素的时候，显然没有中央寄存新增加的数据，这个时候咱们须要对数组进行扩容解决 对下面代码做如下批改： public void add(Object obj){ if(size==elementData.length){ //创立一个新的数组，并且这个数组的长度是原数组长度的2倍 Object[] newArray = new Object[size*2]; //应用底层拷贝，将原数组的内容拷贝到新数组 System.arraycopy(elementData, 0, newArray, 0, elementData.length); //并将新数组赋值给原数组的援用 elementData = newArray; } //新来的元素，间接赋值 elementData[size++]=obj;}用一张图来示意就是这样的： ...

前言很久之前写过一篇无关HashMap的文章：一文看懂HashMap，反应不错。原本手前面是想写篇文章来介绍ArrayList，起初事件多就忘了，明天就来好好聊聊ArrayList。 注释ArrayList相比HashMap来说就比较简单了，先来看看实现了哪些接口： public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ //默认容量大小 private static final int DEFAULT_CAPACITY = 10;//指定ArrayList容量为0时返回该数组private static final Object[] EMPTY_ELEMENTDATA = {};//当没有指定ArrayList容量时返回该数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//保留增加到ArrayList中的元素（ArrayList的底层其实就是一个数组）transient Object[] elementData; //ArrayList中元素数量private int size;.....}从下面的源码咱们能够提取出上面几个要害信息： ArrayList底层应用一个Object类型的数组来保留数据ArrayList默认大小为10能够看到ArrayList底层是应用一个数组elementData来保留数据的，因而也被称为动静数组。值得注意的是用了elementData用了transient润饰。 transient示意elementData无奈被序列化，为什么要这么设置呢？ 因为elementData外面不是所有的元素都有数据，因为容量的问题，elementData外面有一些元素是空的，这种是没有必要序列化的。ArrayList的序列化和反序列化依赖writeObject和readObject办法来实现。能够防止序列化空的元素。 接下来咱们从罕用构造函数动手： public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); }}下面两个构造函数比较简单，就是给对数组做初始化，这里不再细说。 ...

文章曾经收录在 Github.com/niumoo/JavaNotes ，更有 Java 程序员所须要把握的外围常识，欢送Star和指教。 欢送关注我的公众号，文章每周更新。前言说真的，在 Java 应用最多的汇合类中，List 相对占有一席之地的，它和 Map 一样实用于很多场景，十分不便咱们的日常开发，毕竟存储一个列表的需要随处可见。尽管如此，还是有很多同学没有弄明确 List 中 ArrayList 和 LinkedList 有什么区别，这几乎太遗憾了，这两者其实都是数据结构中的根底内容，这篇文章会从根底概念开始，剖析两者在 Java 中的具体源码实现，寻找两者的不同之处，最初思考它们应用时的注意事项。 这篇文章会蕴含以下内容。 介绍线性表的概念，具体介绍线性表中数组和链表的数据结构。进行 ArrayList 的源码剖析，比方存储构造、扩容机制、数据新增、数据获取等。进行 LinkedList 的源码剖析，比方它的存储构造、数据插入、数据查问、数据删除和 LinkedList 作为队列的应用形式等。进行 ArrayList 和 LinkedList 的总结。线性表要钻研 ArrayList 和 LinkedList ，首先要弄明确什么是线性表，这里援用百度百科的一段文字。 线性表是最根本、最简略、也是最罕用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具备雷同个性的数据元素的无限序列。你必定看到了，线性表在数据结构中是一种最根本、最简略、最罕用的数据结构。它将数据一个接一个的排成一条线（可能逻辑上），也因而线性表上的每个数据只有前后两个方向，而在数据结构中，数组、链表、栈、队列都是线性表。你能够设想一下整整齐齐排队的样子。 看到这里你可能有疑难了，有线性表，那么必定有非线性表喽？没错。二叉树和图就是典型的非线性构造了。不要被这些花里胡哨的图吓到，其实这篇文章非常简单，心愿同学急躁看完点个赞。 数组既然晓得了什么是线性表，那么了解数组也就很容易了，首先数组是线性表的一种实现。数组是由雷同类型元素组成的一种数据结构，数组须要调配一段间断的内存用来存储。留神关键词，雷同类型，间断内存，像这样。 不好意思放错图了，像这样。 下面的图能够很直观的体现数组的存储构造，因为数组内存地址间断，元素类型固定，所有具备疾速查找某个地位的元素的个性；同时也因为数组须要一段间断内存，所以长度在初始化长度曾经固定，且不能更改。Java 中的 ArrayList 实质上就是一个数组的封装。 链表链表也是一种线性表，和数组不同的是链表不须要间断的内存进行数据存储，而是在每个节点里同时存储下一个节点的指针，又要留神关键词了，每个节点都有一个指针指向下一个节点。那么这个链表应该是什么样子呢？看图。 哦不，放错图了，是这样。 上图很好的展现了链表的存储构造，图中每个节点都有一个指针指向下一个节点地位，这种咱们称为单向链表；还有一种链表在每个节点上还有一个指针指向上一个节点，这种链表咱们称为双向链表。图我就不画了，像上面这样。 能够发现链表不用间断内存存储了，因为链表是通过节点指针进行下一个或者上一个节点的，只有找到头节点，就能够以此找到前面一串的节点。不过也因而，链表在查找或者拜访某个地位的节点时，须要O(n)的工夫复杂度。然而插入数据时能够达到O(1)的复杂度，因为只须要批改节点指针指向。 ArratList下面介绍了线性表的概念，并举出了两个线性表的理论实现例子，既数组和链表。在 Java 的汇合类 ArrayList 里，实际上应用的就是数组存储构造，ArrayList 对 Array 进行了封装，并减少了不便的插入、获取、扩容等操作。因为 ArrayList 的底层是数组，所以存取十分迅速，然而增删时，因为要挪动前面的元素地位，所以增删效率绝对较低。那么它具体是怎么实现的呢？无妨深刻源码一探到底。 ArrayList 存储构造查看 ArrayList 的源码能够看到它就是一个简略的数组，用来数据存储。 ...