Kevin Fan's Blog Java Develop Engineer

Java ArrayList 与 LinkedList 源码分析(Java8)

2018-08-13
Kevin Fan

Java 中我们经常用到List, List下面最常用的两个就是ArrayList和LinkedList, 这两个虽然都实现了List接口, 然而内部的实现完全不同, 下面将通过 Java 8中的源码来分析一起分析这两个List。

ArrayList 介绍

ArrayList 实现了List, 继承AbstractList, 线程不安全, 查询很快, 增删慢, 底层用数组实现。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 成员变量

size是ArrayList元素的个数, elementData是存储元素的数组, 注意数组的长度并不等于ArrayList元素的个数, 元素个数才是ArrayList的大小。

// 初始数组长度
private static final int DEFAULT_CAPACITY = 10;
// 数组, 存储ArrayList中的元素
transient Object[] elementData;
// 元素的个数(ArrayList size)
private int size;
// 数组结构上的修改次数, 用于ArrayList里的iterator
protected transient int modCount = 0;
// 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

构造函数

比较常用的两个构造函数, 其中一个有参构造初始化了一个长度为initialCapacity的数组

// 无参构造, 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);
    }
}

get(),add()方法

接下来通过分析get和add方法来了解ArrayList的工作原理。

add()方法先调用ensureCapacityInternal()来确定是否需要扩容, 它的字面意思是确保内部容量,目的是确保数组

public boolean add(E e) {
    // size+1, 这里会对数组的size进行判断,如果超过容量数组要扩容。
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 在对应的数组上添加元素
    elementData[size++] = e;
    return true;
}
/* 
这个方法是上面ensureCapacityInternal()调用的一个方法
这里主要用来判断数组是否需要扩容。
参数minCapacity是add()方法里的size+1, 即数组的长度
*/
private void ensureExplicitCapacity(int minCapacity) {
    // modCount:iterator的size+1
    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倍, oldCapacity >> 1 意思是右移一位, 相当于oldCapacity除以2,所以总共是1.5倍。
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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:
    // 数组扩容并填充原来的元素到新数组, 用Arrays.copyOf()来实现, 最终是调用native方法实现的
    elementData = Arrays.copyOf(elementData, newCapacity);
}

用native关键字修饰的方法和普通方法有什么区别呢? native是本地的意思, 也就是说它的实现并不是由Java实现的, java并不提供它的实现。

add() 方法总结

  1. add()方法在添加元素的时候分两步, 一是size+1, 二是将元素添加到数组
  2. add()方法没有用synchronized 关键字修饰,所以它是线程不安全的
  3. add()方法会自动扩容, 当元素个数超过数组长度时, 扩容1.5倍

LinkedList 介绍

不同于ArrayList, LinkedList并没有用数组结构, 它的底层是链表, 每一个元素都有对应的前后元素,LinkedList增删快, 查询慢,线程不安全。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList成员变量

LinkedList初始size为0,first是它的第一个元素(首), last是它最后一个元素(尾),每一个元素都是一个NodeNode里记录了它的上一个元素和 下一个元素,由此组成了链表结构。

// LinkedList的size, 元素个数
transient int size = 0;
// list iterator的大小, 类似于ArrayList的modCount
protected transient int modCount = 0;
// list中的第一个元素
transient Node<E> first;
// list中的最后一个元素
transient Node<E> last;
// 内部类 Node, 每一个元素都是一个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. addFirst()方法

addFirst() 向链表头部添加元素, 实现原理就是, 将新元素的next标记为原来的first, 然后将first的prev set为新元素。 addLast同理

public void addFirst(E e) {
    // 调用私有方法 linkFirst
    linkFirst(e);
}

private void linkFirst(E e) {
    final Node<E> f = first;
    // 创建一个Node对象,这个node下一个是 原来的first,元素是e(新添加的元素)
    final Node<E> newNode = new Node<>(null, e, f);
    // 将新元素赋值给first, 现在新元素是first了
    first = newNode;
    if (f == null)
        last = newNode;
    else
        // set first 之前的元素为新元素, 这样新元素和链表就联系起来了
        f.prev = newNode;
    size++;
    modCount++;
}
  1. removeLast()方法

removeLast() 删除链表最后面的一个元素,然后返回remove之后的最后一个元素last。

removeList调用内部私有方法unlinkLast(), 参数是last,所以这里我们直接看unlinkLast方法

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // element: last元素
    final E element = l.item;
    // prev: last之前的元素
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    // 将倒数第二个元素设置成last
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
  1. get() 方法

根据元素索引来获取元素,核心方法是node()方法

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

Node<E> node(int index) {
    // size>>1: size右移一位, 即size/2,先判断元素在链表的前半部分还是后半部分
    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;
    }
}
  1. contains() 方法

contains()方法可以用来查询某元素是否在list里, 这里介绍这个方法是为了让大家了解到LinkedList的循环操作。 contains方法调用indexOf方法来判断 元素是否存在, 在indexOf()方法中, 如果元素不存在, 返回-1

public boolean contains(Object o) {
    return indexOf(o) != -1;
}

// 传入要查询的元素
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        // 这里就是LinkedList循环的实现, 从first开始,依次查询每个的next,查看元素是否存在
        for (Node<E> x = first; x != null; x = x.next) {
            // 元素存在,返回index
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    // 不存在返回-1
    return -1;
}

get()contains()源码可以看出,LinkedList每次查询的时候都需要遍历一遍所有元素(一半元素), 也就是说如果我们用for循环遍历链表,那么需要 n^2^次遍历, 这也就是为什么LinkedList查询慢的原因, 在实际使用中也要尽量避免用for循环遍历,因为for循环会用到它的索引。

那如果想遍历LinkedList,最好用哪种方式呢?

推荐方法: 迭代器或者增强for循环(foreach)

增强for循环内部也是用迭代器实现的,LinkedList里面的迭代器用next来迭代,依次查询。

用while循环遍历集合

LinkedList<String> list = new LinkedList<>();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String next = iterator.next();
    System.out.println(next);
}

来看一下LinkedList里iterator的next()方法

// 迭代器中的成员变量
private Node<E> lastReturned;
private Node<E> next;

// next()方法
public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();
    // 将next 赋值给lastReturned, 然后将next标记为新的next, 返回lastReturned.item(next的元素)
    lastReturned = next;
    next = next.next;
    nextIndex++;
    return lastReturned.item;
}

上面的方法中,集合在迭代时,不需要重复遍历即可查到所有的元素, 效率高了很多。

总结

ArrayList与LinkedList共同点: 都是线程不安全的,都允许元素重复

区别:ArrayList是数组结构,查询快,增删慢; LinkedList是链表结构,大数据量查询很慢,增删很快,只需要根据前后元素就可以插入进去。

ArrayList因为是数组结构,所以遍历的时候推荐用for循环遍历,LinkedList是链表结构,推荐使用迭代器iterator遍历, 以上仅针对大数据量的情况下, 小数据量下不明显, LinkedList尽量都采用迭代器遍历。


原文链接:https://rollsbean.com/2018/08/13/java-list/


Similar Posts

Comments