Java集合(三) List

第一节 简介

List是一个有序集合，其有两种实现：数组和链表。

• 数组支持的有序集合可以快速的随机访问，在内存中是一段连续的内存空间地址，所以访问任一元素都是O(1)；链表实现的有序集合的随机访问很慢，最好使用迭代器。
• 数组实现的集合插入和删除元素时，需要后面的元素位置都后移或前移，所以性能代价较大O(n)；而链表则可以方便的进行删除。所以只为他们提供一个接口未必是一个好的设计。

1.1 链表

在数据结构中已经很熟悉链表的结构了，这里就不再长篇大论的去整理链表的内容，而只是简要的记录。

为什么要用链表？

• 因为数组做删除等操作性能不佳。

链表和数组相比的优缺点？

• 链表易改难查，数组易查难改。查指随机访问，改指插入或删除操作。

---

第二节 List

2.1 List接口

List接口继承Collection，其声明了数组类需要实现的一系列方法。

public interface List<E> extends Collection<E> {
    // Query Operations
    int size();//数量
    boolean isEmpty();//判空
    boolean contains(Object o);//包含
    Iterator<E> iterator();//迭代器
    Object[] toArray();//转对象数组
    <T> T[] toArray(T[] a);//转泛型数组

    // Modification Operations
    boolean add(E e);//增加
    boolean remove(Object o);//移除

    ......
}

2.2 ListIterator

相较Collection，List除了Iterator外还声明了ListIterator，因为链表实现List时需要通过迭代器来实现插入元素，需要额外的一部分方法来实现链表操作。

public interface ListIterator<E> extends Iterator<E> {
    // Query Operations
    boolean hasNext();
    E next();//遍历
    boolean hasPrevious();
    E previous();//反向遍历
    int nextIndex();
    int previousIndex();

    // Modification Operations
    void remove();
    void set(E e);//用新元素替换上个元素，
    void add(E e);//在此位置前添加一个元素，假定一定会执行添加操作改变链表，所以没有返回值
}

previous() 和 next() 都是操作光标，若调用 remove() 就分别删除左侧和右侧的元素，set() 方法取代两者方法返回的上一个元素。

对于并发修改的检测只针对添加和删除元素，而 set() 则不被认为是结构性修改，可以多迭代器一起执行。

为什么有了Iterator还要有ListIterator？他们的区别是什么？

• 迭代器适合完成将元素插入链表中间的操作，但对于Set集合因为其无序，所以迭代器添加是没有意义的，所以Iterator并没有 add() 方法，而是抽象出了 ListIterator 来为有序集合实现相应的功能.

---

第三节 ArrayList

相较于 [] 数组，ArrayList因为在新增元素时封装了 grow() 函数，所以不需要在初始化时指定大小，可以叫动态数组。

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

3.1 数据结构

ArrayList实现了四个接口：List , RandomAccess , Cloneable , Serializable 。分别对应其四个特性，数组，随机访问，可克隆，可序列化。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    
    //底层还是通过数组来保存元素
    transient Object[] elementData; // non-private to simplify nested class access

    //数组大小
    private int size;

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //默认构造一个空数组
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    //获取指定下标元素
    public E get(int index) {
        //首先检查下标是否越界
        rangeCheck(index);
        //返回对应下标的元素
        return elementData(index);
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    //覆盖指定下标元素
    public E set(int index, E element) {
        //首先检查下标是否越界
        rangeCheck(index);
        //先找到要覆盖的元素
        E oldValue = elementData(index);
        //覆盖
        elementData[index] = element;
        //返回旧数据
        return oldValue;
    }
}

• 底层是对象数组。
• 获取指定下标元素，通过数组直接访问，时间复杂度为O(1)。
• 添加指定下标元素，找到对应下标元素并覆盖。
• 注意 set() 没有自动扩容，所以可能会抛出 IndexOutOfBoundsException 。

3.2 怎么插入

插入数组尾部：首先计算容量并调用 grow() 扩容，向数组尾部添加元素。

   //向集合尾部增加一个指定元素
   public boolean add(E e) {
       //首先检查当前容量是否还够用，不够则扩容
       ensureCapacityInternal(size + 1);
       //添加到数组末尾，++后执行
       elementData[size++] = e;
       return true;
   }
   
// 确保内部容量
   private void ensureCapacityInternal(int minCapacity) {
       ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
   }

// 计算容量，最小取DEFAULT_CAPACITY=10
   private static int calculateCapacity(Object[] elementData, int minCapacity) {
       // 空数组则取minCapacity(>0)或DEFAULT_CAPACITY=10的较大值
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           return Math.max(DEFAULT_CAPACITY, minCapacity);
       }
       return minCapacity;
   }

// 确保有足够容量
   private void ensureExplicitCapacity(int minCapacity) {
       //操作数+1
       modCount++;
       // overflow-conscious code
       if (minCapacity - elementData.length > 0)
           grow(minCapacity); // 扩容
   }

指定位置插入：向 ArrayList 中间插入一个元素则比较麻烦，遇到这种需求一般会使用 LinkedList 。 ArrayList 内部实现则是要把后续元素移位，是通过原数组复制的方式，并且很有可能会需要扩容。

public void add(int index, E element) {
    //首先检查下标是否越界
    rangeCheckForAdd(index);
    //确保容量够用，不够则会调用grow扩容，这个行为会增加操作数
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //通过数组复制实现插入，相当于移位操作
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //将指定位置更新
    elementData[index] = element;
    size++;
}

插入和删除等操作底层都是通过数组复制 System.arraycopy 来实现，所以性能不佳。

3.3 怎么扩容

如下列代码所示，在新增元素时若容量不够，会首先计算所需容量，然后调用 grow() ，其底层是通过调用 System.arraycopy() 进行数组的浅拷贝，生成一份一模一样的副本数组然后返回副本。对于一维数组且元素是基本数据类型，复制的是值，所以副本的变更不会影响到原数组对象。但如果是二维数组或对象数组，复制的是引用，如果对副本元素进行变更就会影响到原数组，当然一般使用场景不需要考虑这些问题。

// 扩容
private Object[] grow(int minCapacity) {
       // overflow-conscious code
       // 先保留旧容量
       int oldCapacity = elementData.length;
       // 新容量是旧容量扩容一半
       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:
       // 通过数组浅复制扩容
       return elementData = Arrays.copyOf(elementData,
                                          newCapacity(minCapacity));
   }
   
// 指定容量复制
   public static <T> T[] copyOf(T[] original, int newLength) {
       return (T[]) copyOf(original, newLength, original.getClass());
   }

   // 指定容量和数组类型复制
   public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
       // 三元表达式构建新的数组实例
       @SuppressWarnings("unchecked")
       T[] copy = ((Object)newType == (Object)Object[].class)
           ? (T[]) new Object[newLength]
           : (T[]) Array.newInstance(newType.getComponentType(), newLength);
       // 通过原生方法arraycopy将原数组内容拷贝到新数组
       System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
       return copy;
   }
   
   //对于参数分别为：源数组，源数组起始位置，目标数组，目标数组起始位置，要复制的长度
   public static native void arraycopy(Object src,  int  srcPos,
                                       Object dest, int destPos,
                                       int length);

也就意味着数组每次扩容都会创建一个新的数组，可以编程测试一下。

a1 : java.util.ArrayList@1
a1 : java.util.ArrayList@80
a1 : java.util.ArrayList@fe2
a1 : java.util.ArrayList@1ecc1
a1 : java.util.ArrayList@3babc3

3.4 怎么删除

删除操作底层还是通过数组复制来实现，只不过目标数组是本身，假设有数组[1,2,3,4]，我们要删除下标为1的元素，则对应参数值分别为：list，2，list，1，2。首先取出下标2后的元素即3和4，然后覆盖到下标1即2和3，变更后数组为[1,3,4,4]。elementData[--size] = null; 再将末尾元素置空，完成删除操作。

public E remove(int index) {
    // 首先检查下标是否越界
    rangeCheck(index);

    // 操作数+1
    modCount++;
    // 获取要删除的元素
    E oldValue = elementData(index);

    // 要复制的长度，即删除元素后面的所有元素
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    
    //减小size，末尾置空
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

public boolean remove(Object o) {// 移除指定对象时，通过对象实现的equals进行等值判断，遍历所有元素，并覆盖式复制移除末尾元素
    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;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

一个经常遇到的问题就是想在遍历数组时顺便删除指定对象，如以下两种。

//普通for循环
for(int i = 0;i < list.size();i++) {
    String s = list.get(i);
    if("b".equals(s)) {
        list.remove(s);
    }
}
//不能删掉连续相邻的第二个b

//for-each
for(String s : list) {
    if(s.equals("b")) {
        list.remove(s);
    }
}
//抛出异常ConcurrentModificationException

为什么会这样呢？回想起删除最终要执行的arraycopy，第一次删除成功后，后续的元素都会前移一位，所以第二个b自然会跳过执行了。这种情况可以通过倒序删除来解决，只要遍历顺序是逆向的，就不会因为元素左移而导致被“躲掉”。

for-each本质上是迭代器遍历，采用快速失败模式，next() 方法会检查当前 modCount 操作数是否是期望的值，而 ArrayList 的 remove() 方法会 modCount++ ，所以会抛出异常。可以使用 iterator.remove() 来代替。

3.5 ArrayList和Vector的区别

Vector类的所有方法都是同步的，所以可以线程安全的使用Vector，而ArrayList则不同步。但单线程情况下Vector仍需要在同步操作上消耗很多时间，所以一般不涉及多线程不会使用Vector。

---

第四节 LinkedList

通过简单的示例来了解一下LinkedList用法：

   List<String> staff = new LinkedList<>();
   staff.add("张三");
   staff.add("李四");
   staff.add("王五");
   
// 迭代器遍历链表
   ListIterator<String> iterator = staff.listIterator();
   String first = iterator.next();
   System.out.println("first:" + first);
   String second = iterator.next();
   System.out.println("second:" + second);
   String pre1 = iterator.previous();
   System.out.println("pre1:" + pre1);
   iterator.remove();
   iterator.forEachRemaining(str->System.out.println(str + " "));   

执行结果如下，可以比较明显的看出，迭代器就是元素间的光标，每次移动都返回跨过的元素地址。

first:张三
second:李四
pre1:李四
王五 

所以可以分析出以上代码执行过程，假设光标可移动位置如下，0张三1李四2王五3，再移动就会抛出异常。将移动轨迹注释到代码上。

String first = iterator.next();//0->1，返回张三
System.out.println("first:" + first);
String second = iterator.next();//1->2，返回李四
System.out.println("second:" + second);
String pre1 = iterator.previous();//2->1，返回李四
System.out.println("pre1:" + pre1);
iterator.remove();//删除上个跨过的元素，也就是李四
iterator.forEachRemaining(str->System.out.println(str + " "));//从1遍历，只剩王五

链表虽然提供了根据整数索引访问元素的 get() 方法，但效率不高。

4.1 数据结构

LinkedList通过静态内部类Node来实现链表，Node是链表节点，只须记住相邻关系即可。因为有首尾节点，实现了 Deque 接口，所以LinkedList很明显是个双向链表。

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;

    //节点
    private static class Node<E> {
        //项目
        E item;
        //下个节点
        Node<E> next;
        //上个节点
        Node<E> prev;
    }
}

4.2 怎么get

链表因为其结构特性，查询指定下标元素的效率要低于数组，每次查询都要从两端节点移动到指定下标。

public E get(int index) {
    //检查下标是否越界
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    //>>表示二进制右移n位，这里表示/2
    if (index < (size >> 1)) {//离首节点比较近，从0遍历到指定下标
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {//离尾节点比较近，从size - 1遍历到指定下标
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

4.3 怎么插入

插入链表尾部：可以根据观察源码add方法，链表插入元素只须影响到插入位置周围的元素，集合其他元素不会被影响，因此插入效率很高。

//新增元素
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    //l记录当前尾节点
    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;//链接l和新节点
    //更新元素数和操作数
    size++;
    modCount++;
}

指定位置插入：链表的指定位置插入核心为linkBefore方法，只会影响到插入位置前后的元素。链表也可以通过迭代器进行插入，LinkedList通过内部类实现了ListIterator。

//指定位置插入
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);//尾节点插入
    else
        linkBefore(element, node(index));//非尾节点插入
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;//期望操作数

    ......
    public void add(E e) {
        //检查操作数是否符合期望值
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);//尾节点插入
        else
            linkBefore(e, next);//非尾节点插入
        nextIndex++;
        expectedModCount++;
    }
    ......
}
    
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++;
}
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);//创建新节点，并设置前后节点分别为pred和succ
    succ.prev = newNode;//更新succ的前个节点
    if (pred == null)
        first = newNode;//若succ为首节点，则更新新节点为首节点
    else
        pred.next = newNode;//否则更新pred的后个节点
    size++;
    modCount++;
}

4.4 怎么删除

根据源码可知删除元素时只需对指定元素前后相邻的元素进行相应的操作，因为是双向链表所以要断开和前后的链接，并分别再连上前后节点，并清空要删除元素对保存值对象的引用，方便GC。

public E remove(int index) {
    //检查下标是否越界
    checkElementIndex(index);
    //先遍历得到指定下标元素，remove::Object的区别只是在查询过程
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    //获取要删除节点x的值
    final E element = x.item;
    //获取x下一个节点
    final Node<E> next = x.next;
    //获取x上一个节点
    final Node<E> prev = x.prev;

    if (prev == null) {//要删除的节点是首节点，则直接设置下个节点为首节点
        first = next;
    } else {//否则链接上一个节点和下一个节点，并断开x和上个节点的链接
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {要删除的节点是尾节点，则直接设置上个节点为尾节点
        last = prev;
    } else {//否则链接上一个节点和下一个节点，并断开x和下个节点的链接
        next.prev = prev;
        x.next = null;
    }

    //清除x的值（断开对item的引用）
    x.item = null;
    size--;
    modCount++;
    return element;
}

---

第五节 Vector

Vector所有方法都通过synchronized同步，是一个线程安全的数组集合，一般不太常用。

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    
    protected Object[] elementData;
    protected int elementCount;
    protected int capacityIncrement;
    
    public synchronized void addElement(E obj) {
        modCount++;
        add(obj, elementData, elementCount);
    }

    public synchronized int size() {
        return elementCount;
    }
    
    public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }

        return elementData(index);
    }

    public synchronized void removeElementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        modCount++;
        elementCount--;
        elementData[elementCount] = null; /* to let gc do its work */
    }

    public synchronized int lastIndexOf(Object o) {
        return lastIndexOf(o, elementCount-1);
    }
    public synchronized int lastIndexOf(Object o, int index) {
        if (index >= elementCount)
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

        if (o == null) {
            for (int i = index; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
}

---

第六节 CopyOnWriteArrayList

参考《CopyOnWriteArrayList的实现原理》。

---

参考博客和文章书籍等：

《Java核心技术 卷Ⅰ》

因博客主等未标明不可引用，若部分内容涉及侵权请及时告知，我会尽快修改和删除相关内容