Java中ArrayList和LinkedList区别

public class ArrayList extends AbstractList         implements List, RandomAccess, Cloneable, java.io.Serializable {          //默认大小     private static final int DEFAULT_CAPACITY = 10;           //省略。。。          //动态数组     transient Object[] elementData;           //数组大小     private int size;          //空构造器     public ArrayList() {         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;     }          // 查询元素     public E get(int index) {         // 检查索引是否在范围内         rangeCheck(index);                             return elementData(index);     }          //顺序添加元素     public boolean add(E e) {         //扩容         ensureCapacityInternal(size + 1);          elementData[size++] = e;         return true;     }          //从数组中间添加元素     public void add(int index, E element) {         // 检查索引是否在范围内         rangeCheckForAdd(index);         // 扩容         ensureCapacityInternal(size + 1);          // 复制数组         System.arraycopy(elementData, index, elementData, index + 1,                          size - index);         // 替换元素         elementData[index] = element;         size++;     }          //是否要扩容     private void ensureCapacityInternal(int minCapacity) {         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));     }          //确定容量     private void ensureExplicitCapacity(int minCapacity) {         modCount++;         if (minCapacity - elementData.length > 0)             grow(minCapacity);     }          //计算数组容量     private static int calculateCapacity(Object[] elementData, int minCapacity) {         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {             return Math.max(DEFAULT_CAPACITY, minCapacity);         }         return minCapacity;     }          //动态数组扩容放法     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);         // 数组复制         elementData = Arrays.copyOf(elementData, newCapacity);     }           //省略。。。        }

//JDK1.8 public class LinkedList     extends AbstractSequentialList     implements List, Deque, Cloneable, java.io.Serializable {      // 元素数量     transient int size = 0;          // 链表首节点     transient Node first;          // 链表尾节点     transient Node last;          // 空构造器     public LinkedList() {              }          // Node内部类     private static class Node {         E item;         Node next;         Node prev;         Node(Node prev, E element, Node next) {             // 中间元素             this.item = element;             // 下一个元素地址             this.next = next;             // 上一个元素地址             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) {         //把链表中last元素赋给l ，如果是第一个元素则为null         final Node l = last;         //把元素封装为一个Node对象         final Node newNode = new Node<>(l, e, null);         //把链表的last元素指向新的元素         last = newNode;         //如果添加的是第一个元素         if (l == null){             //把链表的first元素指向新的元素             first = newNode;         }         //如果添加的不是第一个元素         else{             //把l的下一个元素指向新的元素             l.next = newNode;                     }         //集合中元素数量加1         size++;         modCount++;     }          void linkBefore(E e, Node succ) {         final Node pred = succ.prev;         final Node 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) {         //检测元素索引         checkElementIndex(index);         return node(index).item;     }          //返回指定元素索引处的（非空）节点     Node node(int index) {         //把链表分为两段，如果index在链表的前段，则从前往后找，否则反之         if (index <(size >> 1)) {             Node x = first;             for (int i = 0; i  x = last;             for (int i = size - 1; i > index; i--)                 x = x.prev;             return x;         }     }          //省略。。。      }