动态数组elementData
transient Object[] elementData;
除此之外还有一些数据
1 //默认初始容量 2 private static final int DEFAULT_CAPACITY = 10; 3 4 //共享空数组 5 private static final Object[] EMPTY_ELEMENTDATA = {}; 6 7 //默认初始空数组 8 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 9 10 //动态数组中对象数量 11 private int size;
1、当用无参构造器构造一个ArrayList实例时,使用DEE
1 /** 2 * Constructs an empty list with an initial capacity of ten. 3 * 无参构造器：将DEE空数组传递给elementData 4 */ 5 public ArrayList() { 6 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 7 }
2、当使用传入初始容量但是大小为0的构造器构造一个空ArrayList实例时，使用EE
1 /** 2 * Constructs an empty list with the specified initial capacity. 3 *有参构造器，判断传入的数组大小，若为有效数字且不为0则根据传递的值构造一个数组 4 * 若传入的为0，则将EE空数组给elementData 5 * 若传入的为无效数字，则抛出异常 6 * @param initialCapacity the initial capacity of the list 7 * @throws IllegalArgumentException if the specified initial capacity 8 * is negative 9 */ 10 public ArrayList(int initialCapacity) { 11 if (initialCapacity > 0) { 12 this.elementData = new Object[initialCapacity]; 13 } else if (initialCapacity == 0) { 14 this.elementData = EMPTY_ELEMENTDATA; 15 } else { 16 throw new IllegalArgumentException("Illegal Capacity: "+ 17 initialCapacity); 18 } 19 }
3、区别：作用不同
DEE空数组是无参构造器中调用，后来增加第一个元素时扩容为默认大小10
EE是在构造出空数组（传入有参参数0）时调用，它的作用在于使得所有ArrayList空实例都指向同一个对象也就是EE
1 public E get(int index) { 2 Objects.checkIndex(index, size); 3 return elementData(index); 4 } 5 6 public E set(int index, E element) { 7 Objects.checkIndex(index, size); 8 E oldValue = elementData(index); 9 elementData[index] = element; 10 return oldValue; 11 }
（1）在尾部添加一个元素add(E e)
1 public boolean add(E e) { 2 modCount++; 3 add(e, elementData, size); 4 return true; 5 } 6 7 private void add(E e, Object[] elementData, int s) { 8 if (s == elementData.length) 9 elementData = grow(); 10 elementData[s] = e; 11 size = s + 1; 12 }
（2）在指定位置上添加一个元素add(int index,E e)
1 public void add(int index, E element) { 2 rangeCheckForAdd(index); 3 modCount++; 4 final int s; 5 Object[] elementData; 6 if ((s = size) == (elementData = this.elementData).length) 7 elementData = grow(); 8 System.arraycopy(elementData, index, 9 elementData, index + 1, 10 s - index); 11 elementData[index] = element; 12 size = s + 1; 13 }
（3）grow方法：在两个add方法中都会在插入元素之前检查数组容量是否足够，若不足则需要扩容
1 private Object[] grow(int minCapacity) { 2 return elementData = Arrays.copyOf(elementData, 3 newCapacity(minCapacity)); 4 } 5 6 private Object[] grow() { 7 return grow(size + 1); 8 } 9 10 private int newCapacity(int minCapacity) { 11 // overflow-conscious code 12 int oldCapacity = elementData.length; 13 //重点步骤 14 int newCapacity = oldCapacity + (oldCapacity >> 1); 15 if (newCapacity - minCapacity <= 0) { 16 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 17 return Math.max(DEFAULT_CAPACITY, minCapacity); 18 if (minCapacity < 0) // overflow 19 throw new OutOfMemoryError(); 20 return minCapacity; 21 } 22 return (newCapacity - MAX_ARRAY_SIZE <= 0) 23 ? newCapacity 24 : hugeCapacity(minCapacity); 25 }
（1）移除某一位置上的对象remove(int index)
1 public E remove(int index) { 2 Objects.checkIndex(index, size); 3 4 modCount++; 5 E oldValue = elementData(index); 6 7 int numMoved = size - index - 1; 8 if (numMoved > 0) 9 System.arraycopy(elementData, index+1, elementData, index, 10 numMoved); 11 elementData[--size] = null; // clear to let GC do its work 12 13 return oldValue; 14 }
（2）移除某一对象remove(Object o)
1 //遍历找到o的位置，然后移除，这里的fastRemove方法相对于上面的remove方法少了index验证的步骤，因为能够找到要被删除元素的index则index一定合理 2 public boolean remove(Object o) { 3 if (o == null) { 4 for (int index = 0; index < size; index++) 5 if (elementData[index] == null) { 6 fastRemove(index); 7 return true; 8 } 9 } else { 10 for (int index = 0; index < size; index++) 11 if (o.equals(elementData[index])) { 12 fastRemove(index); 13 return true; 14 } 15 } 16 return false; 17 }
ArrayList接口是实现了Serializable接口的，说明是可以序列化的
但是我们在前面已经看到保存对象集合的elementData用transient修饰，是不被序列化的
这是因为elementData为了后续扩容会保存一定的容量，为了避免序列化这部分内容，序列化就采取上诉的方式用readObject和writeObject方法来序列化
1 private void readObject(java.io.ObjectInputStream s) 2 throws java.io.IOException, ClassNotFoundException { 3 4 // Read in size, and any hidden stuff 5 s.defaultReadObject(); 6 7 // Read in capacity 8 s.readInt(); // ignored 9 10 if (size > 0) { 11 // like clone(), allocate array based upon size not capacity 12 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); 13 Object[] elements = new Object[size]; 14 15 // Read in all elements in the proper order. 16 for (int i = 0; i < size; i++) { 17 elements[i] = s.readObject(); 18 } 19 20 elementData = elements; 21 } else if (size == 0) { 22 elementData = EMPTY_ELEMENTDATA; 23 } else { 24 throw new java.io.InvalidObjectException("Invalid size: " + size); 25 } 26 }
1 private void writeObject(java.io.ObjectOutputStream s) 2 throws java.io.IOException { 3 // Write out element count, and any hidden stuff 4 int expectedModCount = modCount; 5 s.defaultWriteObject(); 6 7 // Write out size as capacity for behavioural compatibility with clone() 8 s.writeInt(size); 9 10 // Write out all elements in the proper order. 11 for (int i=0; i<size; i++) { 12 s.writeObject(elementData[i]); 13 } 14 15 if (modCount != expectedModCount) { 16 throw new ConcurrentModificationException(); 17 } 18 }
Vector和ArrayList操作基本相同，只不过对方法加了synchronized做同步处理,以add方法为例
1 //add1 2 public synchronized boolean add(E e) { 3 modCount++; 4 add(e, elementData, elementCount); 5 return true; 6 } 7 8 //add2 9 public void add(int index, E element) { 10 insertElementAt(element, index); 11 } 12 13 public synchronized void insertElementAt(E obj, int index) { 14 if (index > elementCount) { 15 throw new ArrayIndexOutOfBoundsException(index 16 + " > " + elementCount); 17 } 18 modCount++; 19 final int s = elementCount; 20 Object[] elementData = this.elementData; 21 if (s == elementData.length) 22 elementData = grow(); 23 System.arraycopy(elementData, index, 24 elementData, index + 1, 25 s - index); 26 elementData[index] = obj; 27 elementCount = s + 1; 28 }
1 //扩容重点步骤：确定扩容的大小 2 private int newCapacity(int minCapacity) { 3 // overflow-conscious code 4 int oldCapacity = elementData.length; 5 int newCapacity = oldCapacity + ((capacityIncrement > 0) ? 6 capacityIncrement : oldCapacity); 7 if (newCapacity - minCapacity <= 0) { 8 if (minCapacity < 0) // overflow 9 throw new OutOfMemoryError(); 10 return minCapacity; 11 } 12 return (newCapacity - MAX_ARRAY_SIZE <= 0) 13 ? newCapacity 14 : hugeCapacity(minCapacity); 15 }
双向链表存储，有一个头结点first，一个尾节点last,每一个节点有两个指针，一个指向它的前驱节点，一个指向它的后继节点
1 /** 2 * Pointer to first node. 3 */ 4 transient Node<E> first; 5 6 /** 7 * Pointer to last node. 8 */ 9 transient Node<E> last; 10 11 private static class Node<E> { 12 E item; 13 Node<E> next; 14 Node<E> prev; 15 16 Node(Node<E> prev, E element, Node<E> next) { 17 this.item = element; 18 this.next = next; 19 this.prev = prev; 20 } 21 }
1 public E get(int index) { 2 checkElementIndex(index); 3 return node(index).item; 4 } 5 6 /** 7 * Returns the (non-null) Node at the specified element index. 8 * 用二分法简单判断一下对象在链表前半部分还是后半部分 9 * 决定是从first指针向后遍历还是last指针向前遍历 10 */ 11 Node<E> node(int index) { 12 // assert isElementIndex(index); 13 14 if (index < (size >> 1)) { 15 Node<E> x = first; 16 for (int i = 0; i < index; i++) 17 x = x.next; 18 return x; 19 } else { 20 Node<E> x = last; 21 for (int i = size - 1; i > index; i--) 22 x = x.prev; 23 return x; 24 } 25 }
1 public E set(int index, E element) { 2 checkElementIndex(index); 3 Node<E> x = node(index); 4 E oldVal = x.item; 5 x.item = element; 6 return oldVal; 7 }
1 /** 2 * Links e as last element. 3 */ 4 void linkLast(E e) { 5 final Node<E> l = last; 6 final Node<E> newNode = new Node<>(l, e, null); 7 last = newNode; 8 if (l == null) 9 first = newNode; 10 else 11 l.next = newNode; 12 size++; 13 modCount++; 14 } 15 16 /** 17 * Inserts element e before non-null Node succ. 18 */ 19 void linkBefore(E e, Node<E> succ) { 20 // assert succ != null; 21 final Node<E> pred = succ.prev; 22 final Node<E> newNode = new Node<>(pred, e, succ); 23 succ.prev = newNode; 24 if (pred == null) 25 first = newNode; 26 else 27 pred.next = newNode; 28 size++; 29 modCount++; 30 }
1 /** 2 * Unlinks non-null last node l. 3 */ 4 private E unlinkLast(Node<E> l) { 5 // assert l == last && l != null; 6 final E element = l.item; 7 final Node<E> prev = l.prev; 8 l.item = null; 9 l.prev = null; // help GC 10 last = prev; 11 if (prev == null) 12 first = null; 13 else 14 prev.next = null; 15 size--; 16 modCount++; 17 return element; 18 }
ArrayList和LinkedList都是线程不安全的，因此若想要实现线程安全有一下替换的实现方案
List<String> synList1 = Collections.synchronizedList(new ArrayList<>());
List<String> synList2 = Collections.synchronizedList(new LinkedList<>());
CopyOnWriteArrayList：重点是读写分离
1、原理：
写操作的时候会在一个复制的数组上进行，并且要加锁
读操作在原数组上进行
写操作完毕之后，读操作的数组指针指向新的复制数组
2、关键代码
写操作
1 public boolean add(E e) { 2 synchronized (lock) { 3 Object[] elements = getArray(); 4 int len = elements.length; 5 Object[] newElements = Arrays.copyOf(elements, len + 1); 6 newElements[len] = e; 7 setArray(newElements); 8 return true; 9 } 10 } 11 12 public E remove(int index) { 13 synchronized (lock) { 14 Object[] elements = getArray(); 15 int len = elements.length; 16 E oldValue = elementAt(elements, index); 17 int numMoved = len - index - 1; 18 if (numMoved == 0) 19 setArray(Arrays.copyOf(elements, len - 1)); 20 else { 21 Object[] newElements = new Object[len - 1]; 22 System.arraycopy(elements, 0, newElements, 0, index); 23 System.arraycopy(elements, index + 1, newElements, index, 24 numMoved); 25 setArray(newElements); 26 } 27 return oldValue; 28 } 29 }
读操作
public E get(int index) { return elementAt(getArray(), index); }
3、应用场景
因为CopyOnWriteArrayList允许读写同时进行，大大提高了读操作的性能，因此适用于读多写少的应用场景
4、缺点
（1）内存占用：有一个复制的写数组，因此内存占用增加了一倍
（2）数据不一致：读操作不能实时性得到写操作数据
因此不适合与内存敏感、实时性要求高的应用场景
1、ArrayList与Vector比较
（1）ArrayList是线程不安全的，因此读写效率高，Vector是线程安全的
（2）扩容时ArrayList扩大为原来的1.5倍，Vector扩大为原来的2倍
2、ArrayList与LinkedList比较
（1）ArrayList是用动态数组实现，LinkedList是用双向链表实现
（2）ArrayList支持随机访问，LinkedList不支持
（3）LinkedList插入删除更快
原文：https://www.cnblogs.com/huanglf714/p/11050509.html