深入理解Java集合和Map 2:LIst接口实现类ArrayList,LinkedList,Vector源码剖析及相关特点

List接口

List接口父类为collection接口
此处主要介绍其三个实现类该三各类不仅实现了List接口,LinkedList同时继承AbstractSequentialList类,ArrayList和LinkedList继承了AbstractList类。这两个被继承类实现了一些方法和迭代器相关方法。

ArrayList类

  • 该类常用方法增删改查此处不做详细解释和使用示例。
  • 该类底层采用数组进行实现,数组类型为Object类型。可采用有参构造和无参构造,有参构造可规定列表长度。无参构造构造对象时,实际是创建一个空数组,在添加数据时才会真正的创建一个定长数组,数组长度源码中规定长度默认为10。
private static final int DEFAULT_CAPACITY = 10;
  • 该类为非线程安全类
    以add()方法为例,在源码中代码以及个人解释如下所示,可知在进行数组列表添加操作时,无锁和synchronized,可知该类时非线程安全的。(Vector为线程安全)
/**
     * Appends the specified element to the end of this list.
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!//该方法下文继续进行解释
        elementData[size++] = e;//elementData为底层实现的数组,size为当前数组最后一个位置数据的索引
        return true;
    }
  • 那么我们在添加元素进入列表中时,他是怎么对容量进行判断,容量不够又是怎么进行扩容的?
    上文中add方法中有ensureCapacityInternal(size + 1);该方法源码中定义以及个人解释如下,size+1为当前底层数组的存储数据个数,ensureCapacityInternal方法主要作用在于确认数组的容量是否能够继续添加数据。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//当前数组为空时,我们计算出数组默认初始容量DEFAULT_CAPACITY和当前数组容量minCapacity两者间的最大值
//作为当前数组的最小容量
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);//该方法下文中继续解释
    }

ensureExplicitCapacity方法和grow方法

//该方法主要是明确底层数组的长度,如果最小数组大于真实数组长度,那么我们需要调用grow方法进行数组扩容,这也使得我们在List中看到可以随时向List中增加元素,而不需要考虑容量的问题。关于扩容的具体方法见下文grow源码及个人解释。
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;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//由该句可知,新的容量是在旧的容量//基础上加上旧容量的右移一位,可知新的容量=oldCapacity+(int)(oldCapacity/2),
//第一次扩容若定义了长度则oldCapacity为定义长度,否则,oldCapacity 等于默认10,
//随后的扩容则在当前容量的基础上加上当前容量的1/2,默认扩容为10,15,22,33....
        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);//由此句可知道,列表的扩容实际是内部的数组复制,将原容量的数组复制到新容量的数组中去。
    }

Vector类

  • Vector的内部实现与ArrayList类似,他们在无参构造是默认初始均为10
  • Vector是线程安全的,在其方法上均有synchronized关键字。由此也可知它的速度上慢一些。
  • Vector通过内部源码可知,其底层也是采用数组实现,其增加长度是与ArrayList不同,其是在原有的基础上再增加相同长度
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
//增加一个原来长度,无参构造增加示例,10,20,40,80.....
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList

  • LinkedList的底层实现为链表,其维护一个双向链表,链表中节点为一个内部类,源码定义如下所示,其不像ArrayList和Vector定义为Object,而是一个泛型,无参构造new该对象时实际啥也没干。
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;
        }
    }
  • 由于维护的是链表,这也表明了LinkedList增删改很快,查询慢于其他两个。
  • 线程不安全的。
  • 由于底层为链表实现,所以不涉及扩容问题,每次添加元素均为添加一个节点,链表长度加一,删除减一。
  • 由于涉及到数据结构链表,为了学习优秀的代码方式,学习链表的操作方式,将对增删改查依次分析源码。
  • add()源码解读,见源码注释
public boolean add(E e) {//添加元素
        linkLast(e);//下面介绍
        return true;
    }
     /**
     * Links e as last element.
     */
    void linkLast(E e) {//将添加的元素链接到链表尾部
        final Node<E> l = last;//last表示尾部节点
        final Node<E> newNode = new Node<>(l, e, null);//构造一个新节点,该节点上一个元素为l,下一个元素为空
        last = newNode;//最后一个节点变为了添加的节点
        if (l == null)
	//此处时判断旧的最后一个节点是否为空,为空则表示链表内无数据,此时第一个节点应为添加的节点
            first = newNode;
        else
	//不为空,则表示链表内已有数据,链接到链表尾部即可,因为欸在构造新节点时
	//已经指明他的上一个节点为l,所以此处无需指定反向指向的对象
            l.next = newNode;
        size++; //链表长度加一
        modCount++;//修改次数加一
    }
  • get(index)源码解读,见源码注释
public E get(int index) {
        checkElementIndex(index);//判断index是否超出了范围,超出范围将抛出越界异常
        return node(index).item;//该部分才是返回数据部分,返回节点的item成员,即想查询的数据对象,详见下方函数
    }
private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

     /**
     * Returns the (non-null) Node at the specified element index.
     */
    Node<E> node(int index) {
        // assert isElementIndex(index);
	
	//上文有提,LinkedList维护的是一个双向链表,所以在查找数据时,如果该数据位置处于
	//前半段,则正向查找,处于后半段,反向查找,这样比一个单向链表更快
        if (index < (size >> 1)) {
	//size >> 1,size表示链表长度,size>>1表示向右移位操作,即表示size/(2的1次方)
	//条件成立,正向查找
            Node<E> x = first;//起始节点为头节点
            for (int i = 0; i < index; i++)//循环向下查找,直到向下找index次
                x = x.next;//更新x节点
            return x//返回索引为index节点
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)//从尾节点反向查找
                x = x.prev;
            return x;
        }
    }
  • add(index, element),在index位置添加对象element,其他列表元素逻辑上后移一位,实际进行的是链表的插入指针地址的改变,源码解读,详情见下文源码注释。
public void add(int index, E element) {
        checkPositionIndex(index);//与上文中checkElementIndex类似,不再赘叙

        if (index == size)//如果index==size,即表明插入位置为最后一个节点,直接链接到链表尾
            linkLast(element);//该方法与上文中add()方法一致,不在介绍
        else//如果不是插在尾部,而在其他地方,则进行插入操作
            linkBefore(element, node(index));//此时传入的是要插入的对象element,和此时链表中index位置的节点,node(index)上文get()方法中已有解释,具体插入见下方linkBefore解释
    }
void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;//pred为原链表的index处节点上一个节点
        final Node<E> newNode = new Node<>(pred, e, succ);//利用插入对象e构建新节点,可知新节点的下一个节点为
//原链表的index处的节点succ,他的上一个节点为pred,此时我们只需要指定pred的下一个节点为新节点,succ上一个节点为新节点,即可完成插入
        succ.prev = newNode;//succ上一个节点为新节点
        if (pred == null)//pred为空,则代表链表中无数据,待插入节点为头节点
            first = newNode;
        else//否则,指定pred的下一个节点为新节点
            pred.next = newNode;
        size++;
        modCount++;
    }
  • remove(index),移除位于index位置处的元素,底层链表为移除位于index处的节点,源码及其个人解释见下文代码注释。
public E remove(int index) {
        checkElementIndex(index);//判断index是否超出了范围,超出范围将抛出越界异常,上文已有介绍
        return unlink(node(index));//node(index)表示处于index位置的节点,上文已有介绍
    }

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;//element待删除节点的内容
        final Node<E> next = x.next;//next表示待删除节点下一个节点
        final Node<E> prev = x.prev;//待删除结点上一个节点
	//由以上三个变量可知,我们只需要将next和prev进行链接即可,
	//即prev.next=next,next.prev=prev即可完成插入操作.

        if (prev == null) {//如果prev为空,则表示待删除节点为头节点,此时应将next变为头节点
            first = next;
        } else {
            prev.next = next;
            x.prev = null;//此处逻辑上不置空也可以,但此时x节点仍旧指向链表,虽然不影响遍历等操作
			//个人认为此处置空则可以对该节点进行垃圾回收,不置空则不行
        }

        if (next == null) {如果next为空,则表示待删除节点为尾节点,此时应将pred变为尾节点
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;//链表长度减一
        modCount++;//链表修改次数加一
        return element;//返回已删除节点的内容
    }