【集合系列】- 深入浅出分析Collection中的List接口

一、list简介

list 的数据结构就是一个序列，存储内容时直接在内存中开辟一块连续的空间，然后将空间地址与索引对应。

以下是list集合简易架构图

由图中的继承关系，可以知道，arraylist、linkedlist、vector、stack都是list的四个实现类。

• abstractcollection 是一个抽象类，它唯一实现collection接口的类。abstractcollection主要实现了toarray()、toarray(t[] a)、remove()等方法。
• abstractlist 也是一个抽象类，它继承于abstractcollection。abstractlist实现list接口中除size()、get(int location)之外的函数，比如特定迭代器listiterator。
• abstractsequentiallist 是一个抽象类，它继承于abstractlist。abstractsequentiallist 实现了“链表中，根据index索引值操作链表的全部函数”。
• arraylist 是一个动态数组，它由数组实现。随机访问效率高，随机插入、随机删除效率低。
• linkedlist 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。linkedlist随机访问效率低，但随机插入、随机删除效率高。
• vector 也是一个动态数组，和arraylist一样，也是由数组实现。但是arraylist是非线程安全的，而vector是线程安全的。
• stack 是栈，它继承于vector。它的特性是：先进后出(filo, first in last out)。

下面对各个实现类进行方法剖析！

二、arraylist

arraylist实现了list接口，也是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。
除该类未实现同步外，其余跟vector大致相同。

在java1.5之后，集合还提供了泛型，泛型只是编译器提供的语法糖，方便编程，对程序不会有实质的影响。因为所有的类都默认继承至object，所以这里的数组是一个object数组，以便能够容纳任何类型的对象。

常用方法介绍

2.1、get方法

get()方法同样很简单，先判断传入的下标是否越界，再获取指定元素。

public e get(int index) {
        rangecheck(index);
        return elementdata(index);
}

/**
 * 检查传入的index是否越界
 */
private void rangecheck(int index) {
        if (index >= size)
        throw new indexoutofboundsexception(outofboundsmsg(index));
}

2.2、set方法

set()方法也非常简单，直接对数组的指定位置赋值即可。

public e set(int index, e element) {
        rangecheck(index);
        e oldvalue = elementdata(index);
        elementdata[index] = element;
        return oldvalue;
}

2.3、add方法

arraylist添加元素有两个方法，一个是add(e e)，另一个是add(int index, e e)。
这两个方法都是向容器中添加新元素，可能会出现容量（capacity）不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

grow方法实现

private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length;
        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);
}

添加元素还有另外一个addall()方法，addall()方法能够一次添加多个元素，根据位置不同也有两个方法，一个是在末尾添加的addall(collection<? extends e> c)方法，一个是从指定位置开始插入的addall(int index, collection<? extends e> c)方法。

不同点：addall()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关，时间复杂度是线性增长！

2.4、remove方法

remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素；另一个是remove(object o)，通过o.equals(elementdata[index])来删除第一个满足的元素。

需要将删除点之后的元素向前移动一个位置。需要注意的是为了让gc起作用，必须显式的为最后一个位置赋null值。

• remove(int index)方法

public e remove(int index) {
        rangecheck(index);
        modcount++;
        e oldvalue = elementdata(index);
        int nummoved = size - index - 1;
        if (nummoved > 0)
            system.arraycopy(elementdata, index+1, elementdata, index,
                             nummoved);
        elementdata[--size] = null; //赋null值，方便gc回收
        return oldvalue;
}

• remove(object o)方法

public boolean remove(object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementdata[index] == null) {
                    fastremove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementdata[index])) {
                    fastremove(index);
                    return true;
                }
        }
        return false;
}

三、linkedlist

在上篇文章中，我们知道linkedlist同时实现了list接口和deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（queue），同时又可以看作一个栈（stack）。

linkedlist底层通过双向链表实现，通过first和last引用分别指向链表的第一个和最后一个元素，注意这里没有所谓的哑元（某个参数如果在子程序或函数中没有用到，那就被称为哑元），当链表为空的时候first和last都指向null。

public class linkedlist<e>
    extends abstractsequentiallist<e>
    implements list<e>, deque<e>, cloneable, java.io.serializable
{
     /**容量*/
    transient int size = 0;

    /**链表第一个元素*/
    transient node<e> first;

     /**链表最后一个元素*/
    transient node<e> last;
    
    ......
}

/**
 * 内部类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;
    }
}

常用方法介绍

3.1、get方法

get()方法同样很简单，先判断传入的下标是否越界，再获取指定元素。

public e get(int index) {
        checkelementindex(index);
        return node(index).item;
}

/**
 * 检查传入的index是否越界
 */
private void checkelementindex(int index) {
        if (!iselementindex(index))
            throw new indexoutofboundsexception(outofboundsmsg(index));
}

3.2、set方法

set(int index, e element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改node中item的值。

public e set(int index, e element) {
        checkelementindex(index);
        node<e> x = node(index);
        e oldval = x.item;
        x.item = element;
        return oldval;
}

3.3、add方法

同样的，add()方法有两方法，一个是add(e e)，另一个是add(int index, e element)。

• add(e e)方法

该方法在linkedlist的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间，只需要简单修改几个相关引用即可。

public boolean add(e e) {
        linklast(e);
        return true;
}

/**
 * 添加元素
 */
void linklast(e e) {
        final node<e> l = last;
        final node<e> newnode = new node<>(l, e, null);
        last = newnode;
        if (l == null)
            //原来链表为空，这是插入的第一个元素
            first = newnode;
        else
            l.next = newnode;
        size++;
        modcount++;
}

• add(int index, e element)方法

该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

具体分成两步，1.先根据index找到要插入的位置；2.修改引用，完成插入操作。

public void add(int index, e element) {
        checkpositionindex(index);

        if (index == size)
            //调用add方法，直接在末尾添加元素
            linklast(element);
        else
            //根据index找到要插入的位置
            linkbefore(element, node(index));
}

/**
 * 插入位置
 */
void linkbefore(e e, node<e> succ) {
        // assert succ != null;
        final node<e> pred = succ.prev;
        final node<e> newnode = new node<>(pred, e, succ);
        succ.prev = newnode;
        if (pred == null)
            first = newnode;
        else
            pred.next = newnode;
        size++;
        modcount++;
}

同样的，添加元素还有另外一个addall()方法，addall()方法能够一次添加多个元素，根据位置不同也有两个方法，一个是在末尾添加的addall(collection<? extends e> c)方法，另一个是从指定位置开始插入的addall(int index, collection<? extends e> c)方法。

里面也for循环添加元素，addall()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关，时间复杂度是线性增长！

3.4、remove方法

同样的，remove()方法也有两个方法，一个是删除指定下标处的元素remove(int index)，另一个是删除跟指定元素相等的第一个元素remove(object o)。

两个删除操作都是，1.先找到要删除元素的引用；2.修改相关引用，完成删除操作。

• remove(int index)方法

通过下表，找到对应的节点，然后将其删除

public e remove(int index) {
        checkelementindex(index);
        return unlink(node(index));
}

• remove(object o)方法

通过equals判断找到对应的节点，然后将其删除

public boolean remove(object o) {
        if (o == null) {
            for (node<e> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (node<e> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
}

删除操作都是通过unlink(node<e> x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

/**
 * 删除一个node节点方法
 */
e unlink(node<e> x) {
        // assert x != null;
        final e element = x.item;
        final node<e> next = x.next;
        final node<e> prev = x.prev;
        
        //删除的是第一个元素
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        //删除的是最后一个元素
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modcount++;
        return element;
}

四、vector

vector类属于一个挽救的子类，早在jdk1.0的时候，就已经存在此类，但是到了jdk1.2之后重点强调了集合的概念，所以，先后定义了很多新的接口，比如arraylist、linkedlist，但考虑到早期大部分已经习惯使用vector类，所以，为了兼容性，java的设计者，就让vector多实现了一个list接口，这才将其保留下来。

在使用方面，vector的get、set、add、remove方法实现，与arraylist基本相同，不同的是vector在方法上加了线程同步锁synchronized，所以，执行效率方面，会比较慢！

4.1、get方法

public synchronized e get(int index) {
        if (index >= elementcount)
            throw new arrayindexoutofboundsexception(index);

        return elementdata(index);
}

4.2、set方法

public synchronized e set(int index, e element) {
        if (index >= elementcount)
            throw new arrayindexoutofboundsexception(index);

        e oldvalue = elementdata(index);
        elementdata[index] = element;
        return oldvalue;
}

4.3、add方法

public synchronized boolean add(e e) {
        modcount++;
        ensurecapacityhelper(elementcount + 1);
        elementdata[elementcount++] = e;
        return true;
}

4.4、remove方法

public synchronized boolean removeelement(object obj) {
        modcount++;
        int i = indexof(obj);
        if (i >= 0) {
            removeelementat(i);
            return true;
        }
        return false;
}

五、stack

在 java 中 stack 类表示后进先出（lifo）的对象堆栈。栈是一种非常常见的数据结构，它采用典型的先进后出的操作方式完成的；在现实生活中，手枪弹夹的子弹就是一个典型的后进先出的结构。

在使用方面，主要方法有push、peek、pop。

5.1、push方法

push方法表示，向栈中添加元素

public e push(e item) {
        addelement(item);
        return item;
}

5.2、peek方法

peek方法表示，查看栈顶部的对象，但不从栈中移除它

public synchronized e peek() {
        int     len = size();
        if (len == 0)
            throw new emptystackexception();
        return elementat(len - 1);
}

5.3、pop方法

pop方法表示，移除元素，并将要移除的元素方法

  public synchronized e pop() {
        e       obj;
        int     len = size();
        obj = peek();
        removeelementat(len - 1);
        return obj;
}

关于 java 中 stack 类，有很多的质疑声，栈更适合用队列结构来实现，这使得stack在设计上不严谨，因此，官方推荐使用deque下的类来是实现栈！

六、总结

• arraylist(动态数组结构)，查询快（随意访问或顺序访问），增删慢，但在末尾插入，速度与linkedlist相差无几！
• linkedlist（双向链表结构），查询慢，增删快！
• vector（动态数组结构），相比arraylist都慢，被arraylist替代，基本不在使用。优势是线程安全（函数都是synchronized），如果需要在多线程下使用，推荐使用并发容器中的工具类来操作，效率高！
• stack（栈结构）继承于vector，数据是先进后出，基本不在使用，如果要实现栈，推荐使用deque下的arraydeque，效率比stack高！

七、参考

1、jdk1.7&jdk1.8 源码
2、carpenterlee - java集合分析
3、博客园 - 朽木 - arraylist、linkedlist、vector、stack的比较

作者：炸鸡可乐
出处：