Java 集合深入理解 4 ：Listlt Egt 接口

点击查看Java集合框架深入理解系列，-(゜-゜)つロ乾杯~

蓝瘦！香菇！连着加班几天，醉了。学学List放松下！

在Java集合深入理解：Collection中我们熟悉了Java集合框架的基本概念和优点，也了解了根接口之一的Collection，这篇文章来加深Collection的子接口之一List的熟悉。

List接口

一个List是一个元素有序的、可以重复、可以为null的集合。

Java集合框架中最常使用的几种List实现类是ArrayList，LinkedList和Vector。在各种List中，最好的做法是以ArrayList作为默认选择。当插入、删除频繁时，使用LinkedList，Vector总是比ArrayList慢，所以要尽量避免使用它，具体实现后续文章介绍。

为什么List中的元素“有序”、“可以重复”呢?

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

其次根据官方文档：

TheuserofthisinterfacehasprecisecontroloverwhereinthelisteachelementisinserteTheusercanaccesselementsbytheirintegerindex(positioninthelist),andsearchforelementsinthelist.

可以看到，List接口的实现类在实现插入元素时，都会根据索引进行排列。

比如ArrayList，本质是一个数组：

LinkedList,双向链表：

由于List的元素在存储时互不干扰，没有什么依赖关系，自然可以重复。

List接口定义的方法

List中除了继承Collection的一些方法，还提供以下操作：

位置相关：List和数组一样，都是从0开始，我们可以根据元素在list中的位置进行操作，比如说get,set,add,addAll,remove;搜索：从list中查找某个对象的位置，比如indexOf,lastIndexOf;迭代：使用Iterator的拓展版迭代器ListIterator进行迭代操作;范围性操作：使用subList方法对list进行任意范围的操作。

Collection中提供的一些方法就不介绍了，不熟悉的可以去看一下。

集合的操作

remove(Object)用于删除list中头回出现的指定对象；add(,addAll(Collection)用于把新元素添加到list的尾部，下面这段语句使得list3等于list1与list2组合起来的内容：Listlist3=newArrayList(list;listaddAll(list;注意：上述使用了ArrayList的转换构造函数:publicArrayList(Collection

Object的equlas()方法默认和==一样，比较的是地址是否相等。

因此和Set，Map一样，List中如果想要根据两个对象的内容而不是地址比较是否相等时，需要重写equals()和hashCode()方法。remove(),contains(),indexOf()等等方法都需要依赖它们：

@Override 
public boolean contains(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            //需要重载 Object 默认的 equals 
            if (object.equals(a[i])) {
                return true;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                return true;
            }
        }
    }
    return false;
}

@Override
 public int indexOf(Object object) {
    Object[] a = array;
    int s = size;
    if (object != null) {
        for (int i = 0; i < s; i++) {
            if (object.equals(a[i])) {
                return i;
            }
        }
    } else {
        for (int i = 0; i < s; i++) {
            if (a[i] == null) {
                return i;
            }
        }
    }
    return -1;
}

两个List对象的所有位置上元素都一样才能相等。

位置访问，搜索

基础的位置访问操作方法有：

get,set,add,removeset,remove方法返回的是被覆盖或者被删除的元素；indexOf,lastIndexOf返回指定元素在list中的首次出现/最后一次出现的位置;addAll(int,Collectio在特定位置插入指定集合的所有元素。这些元素按照迭代器Iterator返回的先后顺序进行插入；

下面是一个简单的List中的元素交换方法：

public static  void swap(List a, int i, int j) {
    E tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

不同的是它是多态的，允许任何List的子类使用。Collections中的shuffle就有用到和下面这种相似的交换方法：

public static void shuffle(List list, Random rnd) {
    for (int i = list.size(); i > 1; i--)
        swap(list, i - 1, rnd.nextInt(i));
}

这种算法使用指定的随机算法，从后往前重复的进行交换。和一些其他底层shuffle算法不同，这个算法更加公平，同时够快次交换。

局部范围操作

List.subList(intfromIndex,inttoIndex)方法返回List在fromIndex与toIndex范围内的子集。注意是左闭右开，[fromIndex,toIndex)。

注意！List.subList方法并没有像我们想的那样：创建一个新的List，然后把旧List的指定范围子元素拷贝进新List，根！本！不！是！subList返回的扔是List原来的引用，只不过把开始位置offset和size改了下，见List.subList()在AbstractList抽象类中的实现：

public List subList(int start, int end) {
    if (start >= 0 && end <= size()) {
        if (start <= end) {
            if (this instanceof RandomAccess) {
                return new SubAbstractListRandomAccess(this, start, end);
            }
            return new SubAbstractList(this, start, end);
        }
        throw new IllegalArgumentException();
    }
    throw new IndexOutOfBoundsException();
}

    SubAbstractList(AbstractList list, int start, int end) {
        fullList = list;
        modCount = fullList.modCount;
        offset = start;
        size = end - start;
    }

可以看到，的确是保持原来的引用。

重点来了！

由于subList持有List同一个引用，所以对subList进行的操作也会影响到原有List，举个栗子：

你猜运行结果是什么？

验证了上述重点。

我们可以使用subList对List进行范围操作，比如下面的代码，一句话实现了删除shixinList部分元素的操作：

还可以查找某元素在局部范围内的位置：

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

List与Array区别？

List在很多方面跟Array数组感觉很相似，尤其是ArrayList，那List和数组究竟哪个更好呢？

相似之处：都可以表示一组同类型的对象都使用下标进行索引不同之处：数组可以存任何类型元素List不可以存基本数据类型，必须要包装数组容量固定不可改变；List容量可动态增长数组效率高;List由于要维护额外内容，效率相对低一些

容量固定时优先使用数组，容纳类型更多，更高效。

在容量不确定的情景下，List更有优势，看下ArrayList和LinkedList如何实现容量动态增长：

ArrayList的扩容机制:

public boolean add(E object) {
    Object[] a = array;
    int s = size;
    //当放满时，扩容
    if (s == a.length) {
        //MIN_CAPACITY_INCREMENT 为常量，12
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

可以看到：

当ArrayList的元素个数小于6时，容量达到最大时，元素容量会扩增12；反之，增加当前元素个数的一半。

LinkedList的扩容机制：

public boolean add(E object) {
    return addLastImpl(object);
}

private boolean addLastImpl(E object) {
    Link oldLast = voidLink.previous;
    Link newLink = new Link(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}

可以看到，没！有！扩容机制！

这是由于LinedList实际上是一个双向链表，不存在元素个数限制，使劲加就行了。

transient Link voidLink;

private static final class Link {
    ET data;

    Link previous, next;

    Link(ET o, Link p, Link n) {
        data = o;
        previous = p;
        next = n;
    }
}

List与Array之间的转换

在List中有两个转换成数组的方法：

Object[]toArray()返回一个包含List中所有元素的数组；T[]toArray(T[]array)作用同上，不同的是当参数array的长度比List的元素大时，会使用参数array保存List中的元素；否则会创建一个新的数组存放List中的所有元素；

ArrayList中的实现：

public Object[] toArray() {
    int s = size;
    Object[] result = new Object[s];
    //这里的 array 就是 ArrayList 的底层实现，直接拷贝
    //System.arraycopy 是底层方法，效率很高
    System.arraycopy(array, 0, result, 0, s);
    return result;
}

public  T[] toArray(T[] contents) {
    int s = size;
    //先判断参数能不能放下这么多元素
    if (contents.length < s) {
        //放不下就创建个新数组
        @SuppressWarnings('unchecked') T[] newArray
            = (T[]) Array.newInstance(contents.getClass().getComponentType(), s);
        contents = newArray;
    }
    System.arraycopy(this.array, 0, contents, 0, s);
    if (contents.length > s) {
        contents[s] = null;
    }
    return contents;
}

LinkedList的实现：

public Object[] toArray() {
    int index = 0;
    Object[] contents = new Object[size];
    Link link = voidLink.next;
    while (link != voidLink) {
        //挨个赋值，效率不如 ArrayList
        contents[index++] = link.data;
        link = link.next;
    }
    return contents;
}

@Override
@SuppressWarnings('unchecked')
public  T[] toArray(T[] contents) {
    int index = 0;
    if (size > contents.length) {
        Class ct = contents.getClass().getComponentType();
        contents = (T[]) Array.newInstance(ct, size);
    }
    Link link = voidLink.next;
    while (link != voidLink) {
        //还是比 ArrayList 慢
        contents[index++] = (T) link.data;
        link = link.next;
    }
    if (index < contents.length) {
        contents[index] = null;
    }
    return contents;
}

数组工具类Arrays提供了数组转成List的方法asList:

@SafeVarargs
public static  List asList(T... array) {
    return new ArrayList(array);
}

使用的是Arrays内部创建的ArrayList的转换构造函数：

    private final E[] a;
    ArrayList(E[] storage) {
        if (storage == null) {
            throw new NullPointerException('storage == null');
        }
        //直接复制
        a = storage;
    }

List继承了Collection的iterator()方法，可以获取Iterator，使用它可以进行向后遍历。

在此基础上，List还可以通过listIterator(),listIterator(intlocatio方法获取更强大的迭代器ListIterator。

使用ListIterator可以对List进行向前、向后双向遍历，同时还允许进行add,set,remove等操作。

List的实现类中许多方法都使用了ListIterator，比如List.indexOf()方法的一种实现：

public int indexOf(E e) {
    for (ListIterator it = listIterator(); it.hasNext(); )
        if (e == null ? it.next() == null : e.equals(it.next()))
            return it.previousIndex();
    // Element not found
    return -1;
}

ListIterator提供了add,set,remove操作，他们都是对迭代器刚通过next(),previous()方法迭代的元素进行操作。下面这个栗子中，List通过结合ListIterator使用，可以实现一个多态的方法，对所有List的实现类都适用：

public static  void replace(List list, E val, E newVal) {
    for (ListIterator it = list.listIterator(); it.hasNext(); )
        if (val == null ? it.next() == null : val.equals(it.next()))
            it.set(newVal);
}

List的相关算法：

集合的工具类Collections中包含很多List的相关操作算法：

sort，归并排序shuffle，随机打乱reverse，反转元素顺序swap，交换binarySearch，二分查找……

文章为作者独立观点，不代表股票交易接口观点

Java 集合深入理解 4 ：Listlt Egt 接口

接口测试环境搭建

[Unity接口]子类即继承接口类也继承MonoBehaviour的快速操作和重构实现

C 在基类定义好方法让子类继承接口就能实现

答：PCI接口为什么有些长有些短？