List总结

List体系

ArrayList和LinkedList有什么区别？

ArrayList的底层结构是数组， LinkedList的底层结构是双向链表。

ArrayList是怎么扩容的？

当数组长度不够时进行扩容，每次加一半的空间。

private void grow(int minCapacity) {
    // overflow-conscious code
    // 数组长度
    int oldCapacity = elementData.length;
    // 容量大小 = 原数组长度 + 原数组长度的0.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新容量发现比需要的容量还小，则以需要的容量为准
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量发现比最大容量还大，则使用最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 拷贝出来原有的数据
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList插入、删除、查询元素的时间复杂度各是多少？

• ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
• ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
• ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
• ArrayList从尾部删除元素极快，时间复杂度为O(1)；
• ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；

怎么求两个集合的并集、交集、差集？

• ArrayList支持求并集，调用addAll(Collection<? extends E> c)方法即可；
• ArrayList支持求交集，调用retainAll(Collection<? extends E> c)方法即可；
• ArrayList支持求单向差集，调用removeAll(Collection<? extends E> c)方法即可；

ArrayList是怎么实现序列化和反序列化的？

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
    // 防止序列化期间有修改
    int expectedModCount = modCount;
    // 写出非transient非static属性（会写出size属性）
    s.defaultWriteObject();

    // 写出元素个数
    s.writeInt(size);

    // 依次写出元素
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    // 如果有修改，抛出异常
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    // 声明为空数组
    elementData = EMPTY_ELEMENTDATA;

    // 读入非transient非static属性（会读取size属性）
    s.defaultReadObject();

    // 读入元素个数，没什么用，只是因为写出的时候写了size属性，读的时候也要按顺序来读
    s.readInt();

    if (size > 0) {
        // 计算容量
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        // 检查是否需要扩容
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // 依次读取元素到数组中
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

查看writeObject()方法可知，先调用s.defaultWriteObject()方法，再把size写入到流中，再把元素一个一个的写入到流中。

一般地，只要实现了Serializable接口即可自动序列化，writeObject()和readObject()是为了自己控制序列化的方式，这两个方法必须声明为private，在java.io.ObjectStreamClass#getPrivateMethod()方法中通过反射获取到writeObject()这个方法。

在ArrayList的writeObject()方法中先调用了s.defaultWriteObject()方法，这个方法是写入非static非transient的属性，在ArrayList中也就是size属性。同样地，在readObject()方法中先调用了s.defaultReadObject()方法解析出了size属性。

elementData定义为transient的优势，自己根据size序列化真实的元素，而不是根据数组的长度序列化元素，减少了空间占用。

集合的方法toArray()有什么问题？

返回的有可能不是Object[]类型。

public class ArrayTest {
    public static void main(String[] args) {
        Father[] fathers = new Son[]{};
        // 打印结果为class [Lcom.coolcoding.code.Son;
        System.out.println(fathers.getClass());

        List<String> strList = new MyList();
        // 打印结果为class [Ljava.lang.String;
        System.out.println(strList.toArray().getClass());
    }
}

class Father {}

class Son extends Father {}

class MyList extends ArrayList<String> {
    /**
     * 子类重写父类的方法，返回值可以不一样
     * 但这里只能用数组类型，换成Object就不行
     * 应该算是java本身的bug
     */
    @Override
    public String[] toArray() {
        // 为了方便举例直接写死
        return new String[]{"1", "2", "3"};
    }
}

什么是fail-fast？

fail-fast机制是java集合中的一种错误机制。

当使用迭代器迭代时，如果发现集合有修改，则快速失败做出响应，抛出ConcurrentModificationException异常。

这种修改有可能是其它线程的修改，也有可能是当前线程自己的修改导致的，比如迭代的过程中直接调用remove()删除元素等。

另外，并不是java中所有的集合都有fail-fast的机制。比如，像最终一致性的ConcurrentHashMap、CopyOnWriterArrayList等都是没有fast-fail的。

fail-fast是怎么实现的？

像ArrayList、HashMap中都有一个属性叫 modCount，每次对集合的修改这个值都会加1，在遍历前记录这个值到 expectedModCount中，遍历中检查两者是否一致，如果出现不一致就说明有修改，则抛出ConcurrentModificationException异常。

LinkedList是单链表还是双链表实现的？

双向链表

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除了作为List还有什么用处？

双端队列、栈

LinkedList插入、删除、查询元素的时间复杂度各是多少？

• LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；
• LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；
• LinkedList获取第几个元素，依次遍历，复杂度O(n)

什么是随机访问？

java集合类中元素的访问分为随机访问和顺序访问。随机访问一般是通过index下标访问，行为类似数组的访问。而顺序访问类似于链表的访问，通常为迭代器遍历。以List接口及其实例为例。ArrayList是典型的随机访问型，而LinkedList则是顺序访问型。List接口既定义了下标访问方法又定义了迭代器方法。所以其实例既可使用下标随机访问也可以使用迭代器进行遍历。但这两种方式的性能差异很明显。

哪些集合支持随机访问？他们都有哪些共性？

ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。

CopyOnWriteArrayList是怎么保证并发安全的？

ReentrantLock, 以及 private transient volatile Object[] array 修饰元素。

CopyOnWriteArrayList的实现采用了什么思想？

写入时复制（CopyOnWrite，简称COW）思想是计算机程序设计领域中的一种优化策略。其核心思想是，如果有多个调用者（Callers）同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此做法主要的优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。

CopyOnWriteArrayList是不是强一致性的？

不是，CopyOnWriteArrayList只保证最终一致性，不保证实时一致性,因为读写是在两个容器进行的，只有当写操作执行完毕引入指向新容器后，读才能感知到容器的变化。

CopyOnWriteArrayList适用于什么样的场景？

适用于读多写少的场景

CopyOnWriteArrayList插入、删除、查询元素的时间复杂度各是多少？

CopyOnWriteArrayList的写操作都要先拷贝一份新数组，在新数组中做修改，修改完了再用新数组替换老数组，所以空间复杂度是O(n)，性能比较低下；

CopyOnWriteArrayList的读操作支持随机访问，时间复杂度为O(1)；

删除也是空间复杂度是O(n)

CopyOnWriteArrayList为什么没有size属性？

因为每次修改都是拷贝一份正好可以存储目标个数元素的数组，所以不需要size属性了，数组的长度就是集合的大小，而不像ArrayList数组的长度实际是要大于集合的大小的。

比如，add(E e)操作，先拷贝一份n+1个元素的数组，再把新元素放到新数组的最后一位，这时新数组的长度为len+1了，也就是集合的size了。

• ← 上一篇
• 下一篇 →