Java集合(一)ArrayList、LinkedList、Vector_java arraylist和linkedlist、vector

接口继承关系和实现

Java中集合类存放在java.util包中
主要实现有三种类型：List、Set和Map

1. Collection是集合List、Set、Queue的最基本接口。
2. Map为独立接口，是映射表的基础接口。
3. Iterator用于遍历集合中的数据

List接口的实现

Java中List是一中常用的数据类型。List是中储存的是有序的数据，数据可重复。List一共有三个实现类ArrayList、LinkedList、Vector。

ArrayList

ArrayList是最常用的List实现类，内部是通过数据实现的，每个数据在内存中是连续的，允许对元素进行快速随机访问。

ArrayList初始化

当ArrayList在创建时，创建一个空的数组，容量为0

	// elementData用来存储数据的数组
	transient Object[] elementData;
	// 默认扩容容量为10
	private static final int DEFAULT_CAPACITY = 10;
	// 默认空的数组
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
···
	// 无参构造方法
	public ArrayList() {
	    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}
	
	// initialCapacity指定数组的容量
	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);
        }
    }
···
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ArrayList的添加操作

	// 直接添加元素
	public boolean add(E e) {
		// 计算数组容量，判断是否需要扩容。
		// 当添加时，初始数组为空 ，第一次扩容为默认扩容容量DEFAULT_CAPACITY=10
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 在数组最后添加元素
        elementData[size++] = e;
        return true;
    }
	
	// 根据下标插入数据
	public void add(int index, E element) {
		// 检查插入的下标是否越界
        rangeCheckForAdd(index);
		// 判断是否需要扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 复制插入下标index之后的数组，并赋值给自己
        // 将index之后整体向后移动一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将数据插入到index
        elementData[index] = element;
        size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ArrayList的扩容机制

判断是否需要扩容的3个方法

	// 扩容方法的入口
	// minCapacity判断扩容的必要参数  minCapacity=size+1
	// size+1是为了当数组长度达到 （最大容量-1）时候扩容
	private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
	
	// 这个方法主要是判断数组是否为空数组
	// 如果为空数组，使用数组默认容量DEFAULT_CAPACITY=10
	// 否则返回返回判断扩容参数minCapacity=size+1
	private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	
	// 真正判断扩容的方法
	private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // 注意！！！
        // elementData.length是数组的长度即数组的容量  而不是集合的size
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

扩容方法：grow()

	// 执行扩容的方法
	private void grow(int minCapacity) {
        // oldCapacity 旧的数组容量
        int oldCapacity = elementData.length;
        // newCapacity 扩容后数组的容量 =oldCapacity + oldCapacity / 2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            
        // MAX_ARRAY_SIZE数组长度的最大限制
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            
        // 将旧数组数据复制到扩容后的数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

优点：查询速度块，适合遍历操作
缺点:
当数据中间位置插入或删除时，需要对数组进行复制、移动等操作，效率较低。
当数组扩容时，需要把已有的数据复制到新的数组中
线程不安全

LinkedList

LinkedList是用链表存储结构存储数据的，因此很适合数据的动态插入和删除，查询遍历速度较慢。
链表结构还提供了操作表头和表尾的方法，可以当作堆栈、队列和双向队列使用。

存储数据的节点Node

	// 在链表中，数据的依靠节点来存储，并有上下节点连接
	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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

LinkedList添加数据

LinkedList添加节点通常有两种情况
一：插入节点到链表尾部
二：插入节点到链表头部
三：插入节点到指定下标位置

	// 默认从链表尾部添加节点
	public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    // 尾部添加节点
	void linkLast(E e) {
		// last最后一个节点
        final Node<E> l = last;
        // 当前节点添加到最后节点l的后面，并设置当前节点的上个节点指向l
        final Node<E> newNode = new Node<>(l, e, null);
        // 把添加的节点设置为最后节点
        last = newNode;
        // 如果最后没有节点，就把节点设置为头节点
        if (l == null)
            first = newNode;
        else
       	// 如果有最后节点，设置最后节点指向当前节点
            l.next = newNode;
        size++;
        modCount++;
    }

	// 通过下标插入节点
	public void add(int index, E element) {
		// 检查下标是否越界
        checkPositionIndex(index);
		
		// 如果插入的节点刚好是最后的节点，直接插入到最后
        if (index == size)
            linkLast(element);
        else
        // 插入节点到指定下表
            linkBefore(element, node(index));
    }
    
	// 插入指定下标节点  succ指定下标的节点，断言不等于null
	void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        // pred 指定节点index的上一个节点
        final Node<E> pred = succ.prev;
        // newNode 插入节点到指定下标位置index，并设置当前节点的上下节点指向
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 将指定index节点的上个节点指向当前节点
        succ.prev = newNode;
        // 如果上一个节点为null，设置当前节点为头节点
        if (pred == null)
            first = newNode;
        else
        // 如果上一个节点不为null，设置指向当前节点
            pred.next = newNode;
        size++;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

插入指定节点过程图

优点： 底层数据结构是链表，查询慢，增删快
缺点： 线程不安全

Vector

Vector与ArrayList一样，也是通过数组实现的，不同的是它支持线程的同步，即某一时刻只有一 个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此， 访问它比访问ArrayList慢。

	// 初始容量为10
	public Vector() {
        this(10);
    }
···
	// 操作数据的方法都有synchronized的关键字，因此Vector线程是安全的
	public synchronized boolean add(E e) {}
	···
	public synchronized E get(int index) {}
	···
	public synchronized E remove(int index) {}

1
2
3
4
5
6
7
8
9
10
11
12

优点： 底层数据结构是数组，查询快，增删慢
缺点： 线程安全，效率低