if (size > 0) { // 与 clone() 类似,根据大小而不是容量分配阵列 int capacity = calculateCapacity(elementData, size); SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity); ensureCapacityInternal(size);
Object[] a = elementData; // 按正确顺序读入所有元素 for (int i = 0; i < size; i++) { a[i] = s.readObject(); } } }
MAX_ARRAY_SIZE 数值说明
1 2 3 4 5 6 7
/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ privatestaticfinalint MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index + 1, elementData, index, numMoved); elementData[--size] = null; // 方便 GC
return oldValue; }
1 2 3 4 5 6 7 8
// 上述使用到的方法实现 privatevoidrangeCheck(int index){ if (index >= size) thrownew IndexOutOfBoundsException(outOfBoundsMsg(index)); } E elementData(int index){ return (E) elementData[index]; }
检查 index 合法性,修改计数器 modCount ++
获取旧元素,作为方法返回值
计算需要还原的后面的元素个数为 size - index - 1
后面的元素全部向前移动一个单位,旧元素被覆盖
删除操作前数组的最后一位置空,方便 GC
删除 remove(Object o)
删除指定元素 o
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
publicbooleanremove(Object o){ if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); returntrue; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); returntrue; } } returnfalse; }
publicvoidadd(int index, E element){ checkPositionIndex(index);
if (index == size) linkLast(element); else linkBefore(element, node(index)); }
1 2 3 4 5 6 7 8
privatevoidcheckPositionIndex(int index){ if (!isPositionIndex(index)) thrownew IndexOutOfBoundsException(outOfBoundsMsg(index)); } // 检查下标合法性 index ∈ [0, size] privatebooleanisPositionIndex(int index){ return index >= 0 && index <= size; }
添加 addFirst(E e)
[插入元素到链表头](#插入元素到链表头 linkFirst(E e))
1 2 3
publicvoidaddFirst(E e){ linkFirst(e); }
添加 addLast(E e)
[插入元素到链表尾](#尾插法添加元素 linkLast(E e))
1 2 3
publicvoidaddLast(E e){ linkLast(e); }
删除 remove(Object o)
删除指定元素的第一个匹配项
if 待删除元素为 null
从头查找第一个 null,从链表[断开节点](#删除节点 unlink(Node x))
else 待删除元素不空
从头查找第一个值符合的元素,从链表[断开节点](#删除节点 unlink(Node x))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
publicbooleanremove(Object o){ if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); returntrue; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
尾插法添加元素 linkLast(E e)
l 指针指向链表尾部,用于标记原链表尾
根据 Node(Node<E> prev, E element, Node<E> next) 创建值为 e,前驱为 l 即 last,后继为 null 的节点,这么构造符合尾节点特点
链表尾指针移动到新链表尾
if 原链表尾是 null
说明「链表为空」,此时插入的为第一个节点,因此头指针也指向新节点
else 原链表不为 null
说明「链表不空」,尾插到链表上
size & modCount 自增
1 2 3 4 5 6 7 8 9 10 11
voidlinkLast(E e){ final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
插入元素到非空节点之前 linkBefore(E e, Node succ)
断言 index节点非空
获得 index 节点前驱 pred
创建节点,值为 e,前驱为 pred,后继为 succ
后继连接上新节点
if 前驱为空
说明「插入位置在链表头」,头指针指向新节点
else 后继为空
说明「插入位置在中间」,前驱指向新节点
size & modCount 自增
1 2 3 4 5 6 7 8 9 10 11 12
voidlinkBefore(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) first = newNode; else pred.next = newNode; size++; modCount++; }
插入元素到链表头 linkFirst(E e)
获得头节点
创建节点,值为 e,前驱为 null,后继为 f,即旧头结点
头指针移到新节点
if 旧头节点为空
说明「链表为空」,尾指针指向新节点
else 旧头节点不空
说明「链表不空」,连接 新节点&旧头结点
size & modCount 自增
1 2 3 4 5 6 7 8 9 10 11
privatevoidlinkFirst(E e){ final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }
Node<E> node(int index){ // assert isElementIndex(index); if (index < (size >> 1)) { 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; } }
获取元素四种方法的区别
getFirst() & getLast() & peekFirst() & peekLast()
1 2 3 4 5 6 7 8 9 10
public E peekFirst(){ final Node<E> f = first; return (f == null) ? null : f.item; } public E getFirst(){ final Node<E> f = first; if (f == null) thrownew NoSuchElementException(); return f.item; }
/** * Retrieves, but does not remove, the head of the queue represented by * this deque (in other words, the first element of this deque), or * returns {@code null} if this deque is empty. * * <p>This method is equivalent to {@link #peekFirst()}. * * @return the head of the queue represented by this deque, or * {@code null} if this deque is empty */ E peek();
peek() 返回 deque 队列头, 如果双端队列为空,则返回 null
查看 LinkedList 实现的 peek()
1 2 3 4
public E peek(){ final Node<E> f = first; return (f == null) ? null : f.item; }