Java基础-ArrayList和LinkedList

相对与HashMap，ArrayList和LinkedList都算比较简单的数据结构，通过这篇文章分别的了解一下它们。

ArrayList

来看一下ArrayList的JavaDoc：

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

简单的几句话就概况了ArrayList的全部的特点：

相当于一个“可变长的数组”
允许元素为null
内部使用数组实现，并且提供扩容机制
和Vector类似，但ArrayList不是线程安全的

add方法

1
2
3
4
5


public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

可以看到add方法直接将元素放到数组的最后，如果size + 1超过了数组的长度，会进行扩容。下面来看一下核心的扩容机制。

扩容机制

 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


private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩容为原来的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩为1.5倍还不满足需求，直接扩为最小可以满足容量的值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 拷贝数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

当添加数据的时候，如果ArrayList的大小已经不满足需求时，那么就将数组变为原长度的1.5倍，如果还是不能满足直接扩容为需要的容量（主要是对于addAll函数）。之后的操作就是把老的数组拷到新的数组里面。例如，默认的数组大小是10，也就是说当我们add10个元素之后，再进行一次add时，就会发生自动扩容，数组长度由10变为了15。

测试用例如下：

 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


/**
 * @author leer
 * Created at 12/17/18 11:51 AM
 */
public class ArrayListTest {

  // 反射获取数组的长度
  private static int getArrayListCapacity(ArrayList list) {
    int cap = 0;
    try {
      Field array = ArrayList.class.getDeclaredField("elementData");
      array.setAccessible(true);
      cap = ((Object[]) array.get(list)).length;
      array.setAccessible(false);
    } catch (NoSuchFieldException | IllegalAccessException e) {
      e.printStackTrace();
    }
    return cap;
  }

  @Test
  public void testArrayList() {
    ArrayList<String> arrayList = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
      arrayList.add(i + "test");
    }
    System.out.println("size before resize: " + getArrayListCapacity(arrayList));

    arrayList.add("resize it!");

    System.out.println("size after resize: " + getArrayListCapacity(arrayList));

    ArrayList<String> anotherList = new ArrayList<>();
    for (int i = 0; i < 30; i++) {
      anotherList.add(i + "another");
    }

    System.out.println("another list capacity: " + getArrayListCapacity(anotherList));
    System.out.println("another list size: " + anotherList.size());
    System.out.println("arrayList size: " + arrayList.size());

    int originSize = arrayList.size();
    arrayList.addAll(anotherList);

    org.junit.Assert.assertEquals(anotherList.size() + originSize, getArrayListCapacity(arrayList));
    System.out.println("size after addAll = anotherList.size() + arrayList.size() = " + getArrayListCapacity(arrayList));
  }
}

结果如下：

arraylist-test

线程安全

todo

LinkedList

我们还是来看一下JavaDoc：

Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations, and permits all elements (including {@code null}).

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Note that this implementation is not synchronized.

基于双链表
可以从头部或者尾部开始遍历
同样不是线程安全的

get方法

我们知道链表的头部或尾部插入，删除数据的时间复杂度为O(1)，同时也不需要扩容。而如果我们想要按下标遍历链表，时间复杂性度就变成了O(N)。

LinkedList采用双链表，可使按下标访问的时间复杂度变为O(N/2)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

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;
    }
}

在node方法中得到特定下标的节点：当下标小于长度的1/2时，从头部开始遍历，否则从尾部开始遍历。

区别和联系

ArrayList 、LinkedList 这两个类都实现了List 接口
ArrayList 的实现是基于动态数组，LinkedList 的实现是基于双链表的数据结构
Vector:与ArrayList形式底层都是基于数组实现，是线程安全的
ArrayList的优势：在按下标访问数据时，时间复杂度为O(1)，而LinkedList需要O(N/2)
LinkedList的优势：对在头部或尾部插入和删除操作，时间复杂度为O(1)；而ArrayList也为O(1)，但是可能需要复制数据。

Contents