本文基于JDK1.8讲解。

前言

如何看源码？

• 看继承结构：看这个类的层次结构，处于什么位置，承担什么角色。
• 看构造方法：首先要学会如何使用这个类。
• 看常用方法：看源码无法一蹴而就，一口吃下一个大胖子，平时工作中经常用到什么方法，就去看看这个方法的功能是如何实现的。

数据结构初探-数组和链表

数组

• Java 语言中提供的数组是用来存储固定大小的同类型元素。
• 优点：存取速度快。
• 缺点：
  • 数组的大小在创建后便确定，无法扩容；
  • 插入删除元素很慢，效率很低；
  • 空间通常是有限制的；
  • 需要大块连续的内存块；

// Java中可以使用两种方式来声明数组
dataType[] arrayRefVar
dataType arrayRefVar[]
// Java中数组的创建方式同样有两种
arrayRefVar = new dataType[arraySize] 
dataType[] arrayRefVar = {value0, value1, ..., valuek}

链表

• 链表（Linked list）是一种真正的动态的数据结构。
• 链表是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点。
  的指针
• 使用链表结构可以克服数组需要预先知道数据大小的缺点，但增加了结点的指针域，空间开销比较大。
• 链表允许插入和移除链表上任意位置上的节点，但是不允许随机存取。
• 链表有很多种不同的类型：单向链表，双向链表以及循环链表。

单链表

单链表是一种线性表，实际上是由节点（Node）组成的，每一个节点包括当前节点的数据和下一个节点的引用，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个节点只能也只有它能知道下一个节点的存储位置。由N个节点（Node）组成单向链表，每一个节点都有一个向后的指针（引用）指向下一个节点，最后一个节点指向NULL表示结束，有一个Head（头）指针指向第一个节点表示开始：

增加节点

此时必须有两个指针，一个指向插入位置前的那个节点，称它为prev指针，一个指向待插入的节点，称它为node指针。

• 在链表头插入元素，先把数据封装到结点类Node中，并把Next指向Head，然后把Head指针指向新元素的结点。
  
• 在链表中间插入元素，先把数据封装到结点类Node中，并将Next指向之前prev指针指向的next，再将prev指向的Next指向Node。
  
  
• 可以看到add函数中，在链表头部插入数据需要单独处理，究其原因在于头节点没有前置节点。为了能把关于头结点的操作与其他操作统一起来，为头节点造一个前置节点（前置节点不存储任何数据），称为虚拟头节点。
  

删除节点

双向链表

双向链表：一个节点有两个方向，分别储存当前节点的前驱节点，和后续节点；双向链表的删除只需要指定前驱节点，或者后续节点就可以进行删除操作；但是缺点也很明显每次添加节点时都需要2个指向，额外增加了内存空间消耗。

List（列表）

ArrayList

• ArrayList实现List接口，获得了List集合框架基础功能。
• ArrayList继承了AbstractList，而AbstractList实现了List中的功能。
• ArrayList实现RandomAccess，得到了快速随机访问存储元素的功能，RandomAccess是一个标记接口，没有任何方法；
• ArrayList实现Cloneable，获得了clone()方法，能够实现克隆功能；
• ArrayList实现Serializable，表示能够被序列化，经过序列化去传输，典型的应用就是hessian协议。

属性

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
	// 序列化ID
    private static final long serialVersionUID = 8683452581122892189L;
	
	// 默认初始化容量为10
    private static final int DEFAULT_CAPACITY = 10;

	// 指定该ArrayList容量为0时，返回该空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

	// 它与EMPTY_ELEMENTDATA的区别在于：该数组是默认返回的，而EMPTY_ELEMENTDATA是用户指定容量为0时返回.
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  	// 数据保存的地方，当第一次添加元素进入ArrayList中时，数组将扩容至DEFAULT_CAPACITY，也就是10. transient修饰符表示该字段不会被序列化
    transient Object[] elementData; // non-private to simplify nested class access

	// ArrayList实际大小
    private int size;
	
	// 省略其他方法...
}

构造方法

 /**
  	结合结合有参和无参两个构造方法，可以看出：
  	1.如果用户指定数组容量initialCapacity，如果容量大于0，则按用户指定容量初始化；如果等于0，则返回EMPTY_ELEMENTDATA空数组；如果小于0，则抛出异常。
  	2.如果用户并未指定数组容量，则默认返回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);
        }
    }

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

/**
  * 创建一个包含collection的ArrayList
  * @param c 要放入 ArrayList 中的集合，其内元素将会全部添加到新建的 ArrayList 实例中
  * @throws NullPointerException 当参数 c 为 null 时抛出异常
     */
public ArrayList(Collection<? extends E> c) {
		// 将集合转化成Object[]数组
        elementData = c.toArray();
        // 把转化后的Object[]数组长度赋值给当前ArrayList的size，并判断是否为0
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 这句话意思是：c.toArray 可能不会返回 Object[]，可以查看 java 官方编号为 6260652 的 bug
            if (elementData.getClass() != Object[].class)
            	// // 若 c.toArray() 返回的数组类型不是 Object[]，则利用 Arrays.copyOf(); 来构造一个大小为 size 的 Object[] 数组
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替换空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

常用方法：增删改查

添加元素

添加元素ArrayList有2种方式：

• 直接插入元素：

/**
	一、直接插入元素：
		步骤： (1) 检查是否需要扩容. -- 通过ensureCapacityInternal方法判断添加一个元素后，数组容量是否会超标.
			  (2) 插入元素. -- 数组末尾添加元素
 **/
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}	

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// calculateCapacity: 得到数组最小的容量（不浪费资源）
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果数组为空数组，则返回默认容量10和minCapacity中的最大值，如果不是空数组，则返回minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// ensureExplicitCapacity: 判断数组所需的最小容量是否超过默认容量，超过就要调用grow方法进行扩容. 举个例子：当添加第11个元素时，此时数组所需最小容量是11，而数组长度为默认容量10，此时就要扩容
private void ensureExplicitCapacity(int minCapacity) {
	// 修改次数（modCount）自增1
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// grow: 数组扩容（ArrayList核心），保证ArrayList至少能存储minCapacity个元素 
private void grow(int minCapacity) {
    // 获取数组长度
    int oldCapacity = elementData.length;
    // 第一次1.5倍扩容，如果容量还是小于minCapacity，就将容量扩充为minCapacity
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果扩容后的容量大于临界值，则进行大容量分配
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // copyOf方法将旧数组中的数据复制到新数组中来
    elementData = Arrays.copyOf(elementData, newCapacity);
}

• 在指定位置插入元素：

/**
	二、在指定位置插入元素
		1.检查角标是否越界.
		2.检查空间容量，如有需要即扩容.
		3.插入元素.
 **/
public void add(int index, E element) {
	// 检查角标是否越界
    rangeCheckForAdd(index);

	// 确认容量。注意：只加1，保证资源不被浪费
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    
	// arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量): 目的就是要空出index位置插入element，将index后的元素全部往后移一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 将指定的index位置赋值为element，数组大小+1
    elementData[index] = element;
    size++;
}

// 检查角标是否越界：角标<0或者超过数组实际大小，即越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

删除元素

• 删除元素时不会减少容量，若希望减少容量则调用trimToSize()
• 它不是线程安全的。它能存放null值

/**
	根据角标删除元素：
		1.检查角标是否越界.
		2.删除元素.
		3.计算出需要移动元素的个数，并移动元素.
		4.设置为null，让GC回收.
 **/
public E remove(int index) {
	 // 检查角标是否越界
     rangeCheck(index);

	 // 修改次数+1
     modCount++;
     // 记录该索引处的元素
     E oldValue = elementData(index);
	 // 计算删除指定元素后，需要左移的元素个数
     int numMoved = size - index - 1;
     // 如果有需要左移的元素，即进行左移操作
     if (numMoved > 0)
         System.arraycopy(elementData, index+1, elementData, index, numMoved);
     // 将索引为size-1处的元素置为null，让GC回收                
     elementData[--size] = null; // clear to let GC do its work

     return oldValue;
 }

获取并修改数据

/**
	获取数据：
		1.检查角标是否越界.
		2.返回元素.
 **/
public E get(int index) {
	// 检查角标是否越界
    rangeCheck(index);
    return elementData(index);
}

/**
	修改数据：
		1.检查角标是否越界.
		2.替换新值并返回旧值.
 **/
public E set(int index, E element) {
	// 检查角标是否越界
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

Vectory

Vectory与ArrayList异同

• Vector底层也是数组，与ArrayList最大的区别就是：同步(线程安全)。实现同步的方式也很粗暴，即在方法上加synchronized关键字。加锁和释放锁的这个过程，在系统中是有开销的，因此，在单线程的环境中，Vector效率要差很多。
• 如果想要ArrayList实现同步，可以使用Collections的方法：List list = Collections.synchronizedList(new ArrayList(...));
• ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。

LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // 省略其他内容
}

• LinkedList实现List接口，获得了List集合框架基础功能。
• LinkedList实现Deque接口，提供了双端队列机制。
• LinkedList继承了AbstractList，而AbstractList实现了List中的功能。
• LinkedList实现Cloneable，获得了clone()方法，能够实现克隆功能；
• LinkedList实现Serializable，表示能够被序列化，经过序列化去传输，典型的应用就是hessian协议。
• LinkedList并没有实现RandomAccess，所以不支持随机访问。

属性

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
	// 记录LinkedList的大小
    transient int size = 0;

	// 首节点（或头结点）
    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

	// 尾结点
    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
}

/**
	Node类为LinkedList的内部私有类，用来储存节点信息：
		item: 数据
		next: 指向下一个节点
		prev：指向前一个节点	
 **/

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;
         this.next = next;
         this.prev = prev;
     }
}

构造方法

// 默认构造函数
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */

// 通过一个集合初始化LinkedList，元素顺序有这个集合的迭代器返回顺序决定
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

常用方法：增删改查

增加元素

/**
	 add(E e)方法实际上就是往链表最后添加元素
 **/
public boolean add(E e) {
	// 往链表最后添加元素
    linkLast(e);
    return true;
}

/**
	在指定位置插入元素
 **/
public void add(int index, E element) {
	// 检查参数合法性
    checkPositionIndex(index);

	// 如果index = size，则调用尾插法进行元素插入；否则，则调用linkBefore方法进行插入
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

/**
	插入尾节点思路：
		1.表尾的后续节点指向新节点.
		2.新节点的前驱节点指向表尾.
		3.新节点的后继节点指向null.
 **/
void linkLast(E e) {
	// 获取尾结点
    final Node<E> l = last;
    // 构造一个新的节点，pre指向尾节点，next指向null
    final Node<E> newNode = new Node<>(l, e, null);
    // 重新赋值尾节点
    last = newNode;
    // 如果原先尾节点是null，赋值给头节点;如果尾节点不为空，尾节点的next为新生成的节点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // LinkedList的大小和修改次数（跟线程相关）加1
    size++;
    modCount++;
}

/**
	根据节点的位置，往前新增节点：
		例如 pred <-> succ 变成  pred <-> newNode <-> succ
		1.通过succ的前置节点找到pred，将其保存下来
		2.初始化一个新节点NewNode，NewNode的后置节点指向succ，NewNode的前置节点指向pred，也就是succ.prev
		3.把succ的前置节点指向newNode，newNode和succ之间双向通道已建立
		4.把pred的后置节点指向newNode，newNode和pred之间双向通道已建立
		
 **/
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 将原先succ节点前置节点指向的节点信息保存下来
    final Node<E> pred = succ.prev;
    // 构造一个新的节点，pre指向succ.prev，next指向succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将新节点作为旧节点对象的prev，与其建立连接
    succ.prev = newNode;
    // 如果pred为空则代表为新增头部，将新增节点作为头部
    if (pred == null)
        first = newNode;
    // 如果不为空，将新节点作为原来pred的next，即替换原来的next对象
    else
        pred.next = newNode;
    size++;
    modCount++;
}

// 检查索引是否超出范围: 因为元素索引是0~size-1的
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

删除元素

public E remove(int index) {
	// 检查参数合法性
    checkElementIndex(index);
    // 删除指定节点
    return unlink(node(index));
}

// 删除指定节点并返回被删除的元素值
E unlink(Node<E> x) {
    // assert x != null;
    // 获取指定节点的元素值item、前置节点prev、后置节点next
    /**
    	例如 old <-> x <-> new，此时删除x，需要如下操作：
    		1. 获取x的值、前置节点、后置节点，x.next = new， x.prev = old
    		2. 如果Old不是头节点，则将old.next = x.next，即old -> new
    		3. 如果new不是尾结点，则将new.prev = x.prev，即new -> old
    		4. 此时old和new已经建立双边通道，将x.next设为null，断开x和new之间的联系
     **/
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
	
	// 如果前置节点为Null，则代表删除的是头部节点，此时将next设为头部节点
    if (prev == null) {
        first = next;
    } else {
    // 如果前置节点不为Null，则将prev的后置节点由原来的x，换成现在的x.next
        prev.next = next;
        x.prev = null;
    }
	// 如果后置节点为Null，则代表删除的是尾部节点，此时将prev设为尾部节点
    if (next == null) {
        last = prev;
    } else {
    // 如果后置节点不为Null，则将prev的前置节点由原来的x，换成现在的x.prev
        next.prev = prev;
        // 将原先x的next置为空
        x.next = null;
    }
	// 将item数据内容置为null，LinkedList大小减1，修改次数加1
    x.item = null;
    size--;
    modCount++;
    return element;
}

查询和修改元素

// 根据索引位置获取元素
public E get(int index) {
	// 检查参数合法性
    checkElementIndex(index);
    // 根据index找到对应的node节点，再返回node的item属性
    return node(index).item;
}

// 获取指定位置的节点
Node<E> node(int index) {
    // assert isElementIndex(index);
	// 类似于二分查找（折半查找），从位置索引的中间切开，如果位置索引 < 中间，则从前往后遍历；如果索引 > 中间，则从后往前遍历.
	// 好处：采用了优化算法，判断index与链表的头部还是尾部近，避免更多的遍历
    if (index < (size >> 1)) {
    	// index = 0时不会循环，直接返回first
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
    	// index = size时也不会循环，直接返回last
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

// 在指定位置，设置元素的值
public E set(int index, E element) {
	// 检查参数合法性
    checkElementIndex(index);
    // 获取指定位置的节点
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

总结

ArrayList：

• 底层实现是数组
• ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
• 在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList：

• 底层实现是双向链表[双向链表方便实现往前遍历]

Vector：

• 底层是数组，现在已少用，被ArrayList替代，原因有两个：
  • Vector所有方法都是同步，有性能损失。
  • Vector初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存。

总的来说：查询多用ArrayList，增删多用LinkedList。

ArrayList增删慢不是绝对的(在数量大的情况下，已测试)：

• 如果增加元素一直是使用add()(增加到末尾)的话，那是ArrayList要快
• 一直删除末尾的元素也是ArrayList要快【不用复制移动位置】

但一般来说：增删多还是用LinkedList，因为上面的情况是极端的~