Java 集合深入理解(4):List<E> 接口

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

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

List 接口

一个 List 是一个元素有序的、可以重复可以为 null 的集合(有时候我们也叫它“序列”)。

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

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

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

其次根据官方文档

The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

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

比如 ArrayList,本质是一个数组:

LinkedList, 双向链表:

由于 List 的元素在存储时互不干扰,没有什么依赖关系,自然可以重复(这点与 Set 有很大区别)。

List 接口定义的方法

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

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

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

集合的操作

  • remove(Object)
    • 用于删除 list 中头回出现的 指定对象;
  • add(E), addAll(Collection<? extends E>)
    • 用于把新元素添加到 list 的尾部,下面这段语句使得 list3 等于 list1 与 list2 组合起来的内容: List list3 = new ArrayList(list1); list3.addAll(list2);

    注意:上述使用了 ArrayList 的转换构造函数: public ArrayList(Collection

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

public boolean equals(Object o) {
    return this == o;
}

因此和 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, remove
    • set, remove 方法返回的是 被覆盖 或者 被删除 的元素;
  • indexOf, lastIndexOf
    • 返回指定元素在 list 中的首次出现/最后一次出现的位置(获取 lastIndexOf 是通过倒序遍历查找);
  • addAll(int,Collection)
    • 在特定位置插入指定集合的所有元素。这些元素按照迭代器 Iterator 返回的先后顺序进行插入;

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

public static <E> void swap(List<E> 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.size() -1 )次交换。

局部范围操作

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

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

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

SubAbstractListRandomAccess 最终也是继承 SubAbstractList,直接看 SubAbstractList:

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

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

所以,重点来了!

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

你猜运行结果是什么?

验证了上述重点。

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

shixinList.subList(fromIndex, toIndex).clear();

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

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<E> oldLast = voidLink.previous;
    Link<E> newLink = new Link<E>(object, oldLast, voidLink);
    voidLink.previous = newLink;
    oldLast.next = newLink;
    size++;
    modCount++;
    return true;
}
可以看到,没!有!扩容机制!
这是由于 LinedList 实际上是一个双向链表,不存在元素个数限制,使劲加就行了。
transient Link<E> voidLink;

private static final class Link<ET> {
    ET data;

    Link<ET> previous, next;

    Link(ET o, Link<ET> p, Link<ET> 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> 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<E> link = voidLink.next;
    while (link != voidLink) {
        //挨个赋值,效率不如 ArrayList
        contents[index++] = link.data;
        link = link.next;
    }
    return contents;
}

@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] contents) {
    int index = 0;
    if (size > contents.length) {
        Class<?> ct = contents.getClass().getComponentType();
        contents = (T[]) Array.newInstance(ct, size);
    }
    Link<E> 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 <T> List<T> asList(T... array) {
    return new ArrayList<T>(array);
}

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

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

迭代器 Iterator, ListIterator

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

在此基础上,List 还可以通过 listIterator(), listIterator(int location) 方法(后者指定了游标的位置)获取更强大的迭代器 ListIterator

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

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

public int indexOf(E e) {
    for (ListIterator<E> 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 <E> void replace(List<E> list, E val, E newVal) {
    for (ListIterator<E> 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 ,二分查找
  • ……

具体实现我们后续介绍,感谢关注!

关联: Collection, ListIterator, Collections

Thanks:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/List.html

https://docs.oracle.com/javase/tutorial/collections/interfaces/list.html

http://blog.csdn.net/mazhimazh/article/details/17759579#comments

http://www.blogjava.net/flysky19/articles/92775.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

char *a 与char a[] 的区别

char *a = “hello” 中的a是指向第一个字符‘h’的一个指针

511
来自专栏Java帮帮-微信公众号-技术文章全总结

第十五天 常用API-object&string&stringbuilder&stringbuffer【悟空教程】

第十五天 常用API-object&string&stringbuilder&stringbuffer【悟空教程】

1001
来自专栏LinkedBear的个人空间

唠唠SE的集合-00——概述 原

                        由于是数组实现,在增和删的时候会牵扯到数组增容、以及拷贝元素,所以慢。

742
来自专栏大数据学习笔记

Spark2.x学习笔记:2、Scala简单例子

2、 Scala简单例子 参考教程:https://yq.aliyun.com/topic/69 2.1 交互式编程 spark-shell是Spark交互式...

4268
来自专栏别先生

Scala学习教程笔记一之基础语法,条件控制,循环控制,函数,数组,集合

前言:Scala的安装教程:http://www.cnblogs.com/biehongli/p/8065679.html 1:Scala之基础语法学习笔记: ...

3385
来自专栏Java与Android技术栈

Scala学习笔记(八)

模式匹配是 Scala 的重要特性之一,前面两篇笔记Scala学习笔记(六) Scala的偏函数和偏应用函数、Scala学习笔记(七) Sealed Class...

943
来自专栏http://www.cnblogs.com

生成器&迭代器

一.生成器 在介绍生成器表达式之前,先看下列表表达式: 1 >>> l = [i for i in range(50) if i % 2] #生成...

33410
来自专栏从流域到海域

《笨办法学Python》 第30课手记

《笨办法学Python》 第30课手记 本节课讲if语句的嵌套,和c的差别仅仅是将else if简写成elif,其余类似。 原代码如下: people = 30...

1737
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1685
来自专栏Golang语言社区

Go语言 枚举和类型

package mainimport "fmt"//1.枚举的使用// 枚举指一系列相关的常量,比如下面关于一个星期中每天的定义。通过上一节的例子,我们// 看...

3408

扫码关注云+社区