public class ArrayList<E> extends AbstractList<E>
? ? ? ? implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
? ??
? ? //默認(rèn)大小
? ? private static final int DEFAULT_CAPACITY = 10;
? ? ?
? ? //省略。。。
? ??
? ? //動(dòng)態(tài)數(shù)組
? ? transient Object[] elementData;?
? ??
? ? //數(shù)組大小
? ? private int size;
? ??
? ? //空構(gòu)造器
? ? public ArrayList() {
? ? ? ? this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
? ? }
? ??
? ? // 查詢(xún)?cè)?
? ? public E get(int index) {
? ? ? ? // 檢查索引是否在范圍內(nèi)
? ? ? ? rangeCheck(index);?? ??? ??? ??? ??? ?
? ? ? ? return elementData(index);
? ? }
? ??
? ? //順序添加元素
? ? public boolean add(E e) {
? ? ? ? //擴(kuò)容
? ? ? ? ensureCapacityInternal(size + 1);?
? ? ? ? elementData[size++] = e;
? ? ? ? return true;
? ? }
? ??
? ? //從數(shù)組中間添加元素
? ? public void add(int index, E element) {
? ? ? ? // 檢查索引是否在范圍內(nèi)
? ? ? ? rangeCheckForAdd(index);
? ? ? ? // 擴(kuò)容
? ? ? ? ensureCapacityInternal(size + 1);?
? ? ? ? // 復(fù)制數(shù)組
? ? ? ? System.arraycopy(elementData, index, elementData, index + 1,
? ? ? ? ? ? ? ? ? ? ? ? ?size - index);
? ? ? ? // 替換元素
? ? ? ? elementData[index] = element;
? ? ? ? size++;
? ? }
? ??
? ? //是否要擴(kuò)容
? ? private void ensureCapacityInternal(int minCapacity) {
? ? ? ? ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
? ? }
? ??
? ? //確定容量
? ? private void ensureExplicitCapacity(int minCapacity) {
? ? ? ? modCount++;
? ? ? ? if (minCapacity - elementData.length > 0)
? ? ? ? ? ? grow(minCapacity);
? ? }
? ??
? ? //計(jì)算數(shù)組容量
? ? private static int calculateCapacity(Object[] elementData, int minCapacity) {
? ? ? ? if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
? ? ? ? ? ? return Math.max(DEFAULT_CAPACITY, minCapacity);
? ? ? ? }
? ? ? ? return minCapacity;
? ? }
? ??
? ? //動(dòng)態(tài)數(shù)組擴(kuò)容放法
? ? private void grow(int minCapacity) {
? ? ? ? //?
? ? ? ? int oldCapacity = elementData.length;
? ? ? ? int newCapacity = oldCapacity + (oldCapacity >> 1);
? ? ? ? if (newCapacity - minCapacity < 0)
? ? ? ? ? ? newCapacity = minCapacity;
? ? ? ? if (newCapacity - MAX_ARRAY_SIZE > 0)
? ? ? ? ? ? newCapacity = hugeCapacity(minCapacity);
? ? ? ? // 數(shù)組復(fù)制
? ? ? ? elementData = Arrays.copyOf(elementData, newCapacity);
? ? }
? ??
? ? ?//省略。。。
? ??
? }

//JDK1.8
public class LinkedList<E>
? ? extends AbstractSequentialList<E>
? ? implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{?
? ? // 元素?cái)?shù)量
? ? transient int size = 0;
? ??
? ? // 鏈表首節(jié)點(diǎn)
? ? transient Node<E> first;
? ??
? ? // 鏈表尾節(jié)點(diǎn)
? ? transient Node<E> last;
? ??
? ? // 空構(gòu)造器
? ? public LinkedList() {
? ? ? ??
? ? }
? ??
? ? // Node內(nèi)部類(lèi)
? ? private static class Node<E> {
? ? ? ? E item;
? ? ? ? Node<E> next;
? ? ? ? Node<E> prev;
? ? ? ? Node(Node<E> prev, E element, Node<E> next) {
? ? ? ? ? ? // 中間元素
? ? ? ? ? ? this.item = element;
? ? ? ? ? ? // 下一個(gè)元素地址
? ? ? ? ? ? this.next = next;
? ? ? ? ? ? // 上一個(gè)元素地址
? ? ? ? ? ? this.prev = prev;
? ? ? ? }
? ? }
? ??
? ? // 順序添加元素
? ? public boolean add(E e) {
? ? ? ? linkLast(e);
? ? ? ? return true;
? ? }
? ??
? ? // 指定位置添加元素
? ? public void add(int index, E element) {
? ? ? ? // 檢查是否越界
? ? ? ? checkPositionIndex(index);?? ?
? ? ? ? // 在鏈表末尾添加，否則在之前插入元素
? ? ? ? if (index == size)?? ??? ??? ?
? ? ? ? ? ? linkLast(element);
? ? ? ? else
? ? ? ? ? ? linkBefore(element, node(index));
? ? }
? ??
? ? // 添加元素e
? ? void linkLast(E e) {
? ? ? ? //把鏈表中l(wèi)ast元素賦給l ，如果是第一個(gè)元素則為null
? ? ? ? final Node<E> l = last;
? ? ? ? //把元素封裝為一個(gè)Node對(duì)象
? ? ? ? final Node<E> newNode = new Node<>(l, e, null);
? ? ? ? //把鏈表的last元素指向新的元素
? ? ? ? last = newNode;
? ? ? ? //如果添加的是第一個(gè)元素
? ? ? ? if (l == null){
? ? ? ? ? ? //把鏈表的first元素指向新的元素
? ? ? ? ? ? first = newNode;
? ? ? ? }
? ? ? ? //如果添加的不是第一個(gè)元素
? ? ? ? else{
? ? ? ? ? ? //把l的下一個(gè)元素指向新的元素
? ? ? ? ? ? l.next = newNode; ? ? ? ? ? ?
? ? ? ? }
? ? ? ? //集合中元素?cái)?shù)量加1
? ? ? ? size++;
? ? ? ? modCount++;
? ? }
? ??
? ? void linkBefore(E e, Node<E> succ) {
? ? ? ? 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++;
? ? }
? ??
? ? //獲取元素
? ? public E get(int index) {
? ? ? ? //檢測(cè)元素索引
? ? ? ? checkElementIndex(index);
? ? ? ? return node(index).item;
? ? }
? ??
? ? //返回指定元素索引處的（非空）節(jié)點(diǎn)
? ? Node<E> node(int index) {
? ? ? ? //把鏈表分為兩段，如果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;
? ? ? ? }
? ? }
? ??
? ? //省略。。。
? ??
}