Java编程笔记8：容器（上）

2022年1月21日 1193点热度 0人点赞 0条评论

容器是编程语言的重要组成部分，容器和语言风格是紧密相关的，比如Python中的列表、元组、map等，Go的切片、映射等。

本篇文章将探讨Java中的容器。

Collection

Java中的容器可以大致分为Collection和Map两类，其中Collection包括List、Set、Query等可以保存一系列元素的容器。Map代表一种可以保存键值对的映射类型。

Collection可以被翻译作集合，但是Set同样可以被翻译作集合，但两者本质上是不一样的，前者泛指一类可以保存元素的容器，而后者指数学上的概念，即不包含重复元素的一个集，在Java中表现为去重容器。

Collection是一个接口，该接口扩展自Iterable接口，所有Collection类型的容器都会实现这个接口。下面是从Java源码中摘抄的Collection接口定义：

public interface Collection<E> extends Iterable<E> {
    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    default <T> T[] toArray(IntFunction<T[]> generator) {
        return toArray(generator.apply(0));
    }

    boolean add(E e);

    boolean remove(Object o);

    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    boolean retainAll(Collection<?> c);

    void clear();

    boolean equals(Object o);

    int hashCode();

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }

    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }

    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

其中比较重要的方法有：

int size();，返回容器中包含的元素个数。
boolean isEmpty();，判断容器是否为空。
boolean contains(Object o);，判断容器中是否包含某个元素。
Iterator<E> iterator();，返回一个容器的迭代器。
Object[] toArray();，返回一个容器中所有元素组成的数组。如果容器中的元素是有序的，数组中的元素顺序必须保持一致。
<T> T[] toArray(T[] a);，返回容器元素组成的数组（泛型版本）。
boolean add(E e);，给容器添加元素。
boolean remove(Object o);，将给定元素从容器中删除（如果有的话）。
boolean containsAll(Collection<?> c);，判断给定的Collection容器是否被当前容器包含。
boolean addAll(Collection<? extends E> c);，将给定的Collection容器中的元素添加到当前容器中。
boolean removeAll(Collection<?> c);，将给定的Collection容器中的元素从当前容器中删除。
boolean retainAll(Collection<?> c);，保留当前容器中的容器c中的所有元素，换言之，会将不在容器c中的元素从当前容器中删除。
void clear();，清空容器。
boolean equals(Object o);，判断给定的对象是否与容器相等。

这里展示一个Collection的使用示例，这个示例中使用ArrayList作为真正的容器，使用Collection句柄进行操作：

package ch8.collection;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Random;

public class Main {
    private static Random random = new Random();

    private static Collection<Integer> getRandomNumbers(int times) {
        Collection<Integer> collection = new ArrayList<Integer>();
        for (int i = 0; i < times; i++) {
            collection.add(random.nextInt(100));
        }
        return collection;
    }

    public static void main(String[] args) {
        Collection<Integer> numbers = new ArrayList<Integer>();
        numbers.add(100);
        System.out.println(numbers);
        Collection<Integer> numbers2 = getRandomNumbers(3);
        System.out.println(numbers2);
        numbers.addAll(numbers2);
        System.out.println(numbers);
        System.out.println(numbers.contains(100));
        System.out.println(numbers.containsAll(numbers2));
        numbers.remove(100);
        System.out.println(numbers);
        numbers.removeAll(numbers2);
        System.out.println(numbers);
        System.out.println(numbers.add(99));
        System.out.println(numbers);
        numbers.clear();
        System.out.println(numbers);
        // [100]
        // [60, 95, 44]
        // [100, 60, 95, 44]
        // true
        // true
        // [60, 95, 44]
        // []
        // true
        // [99]
        // []
    }
}

虽然实际工作中很少使用Collection作为ArrayList或LinkedList对象的句柄，而是使用List。但上面的示例依然可以说明Collection接口中相关方法的用途。

泛型

上面介绍Collection时使用的Collection<Integer>这样的类型，其中<>中的部分被称作“泛型”。关于泛型的详细介绍会在后续文章中。这里只说明为何要使用泛型。

JavaSE5之前是没有泛型的，所有的容器中的元素实际上都保存为Object类型：

package ch8.generic;

import java.util.ArrayList;
import java.util.List;

import util.Fmt;

class Apple {
    private static int counter = 0;
    private int id = ++counter;

    public void eat() {
        Fmt.printf("Apple(%d) is eated.\n", id);
    }
}

class Orange {
}

class RedApple extends Apple {
}

class GreenApple extends Apple {
}

public class Main {
    private static void printApples(List apples) {
        for (Object object : apples) {
            Apple apple = (Apple) object;
            apple.eat();
        }
    }

    public static void main(String[] args) {
        List apples = new ArrayList();
        apples.add(new Apple());
        apples.add(new RedApple());
        apples.add(new GreenApple());
        printApples(apples);
        // Apple(1) is eated.
        // Apple(2) is eated.
        // Apple(3) is eated.
        apples.add(new Orange());
        printApples(apples);
        // Apple(1) is eated.
        // Apple(2) is eated.
        // Apple(3) is eated.
        // Exception in thread "main" java.lang.ClassCastException: class
        // ch8.generic.Orange cannot be cast to class ch8.generic.Apple
        // (ch8.generic.Orange and ch8.generic.Apple are in unnamed module of loader
        // 'app')
        // at ch8.generic.Main.printApples(Main.java:29)
        // at ch8.generic.Main.main(Main.java:40)
    }
}

就像上面的示例中展示的那样，在某些时候这会带来一些麻烦，比如容器中“意外”地添加进了我们不需要的类型，并在我们尝试将其转化为我们需要的类型时产生运行时ClassCastException异常。

而如果使用泛型，所有这些问题都可以在编译期得到检查。并且你从容器中取出的元素直接就是目标类型，无需再手动进行转换。

List

List是比Collection更为常用的容器接口，它继承自Collection，并在Collection接口的基础上添加了数字索引相关的操作。

下面的List定义摘抄自Java源码，并且删除了与Collection接口重复的部分：

public interface List<E> extends Collection<E> {
    boolean addAll(int index, Collection<? extends E> c);

    @SuppressWarnings({ "unchecked", "rawtypes" })
    default void sort(Comparator<? super E> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<E> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

    E get(int index);

    E set(int index, E element);

    void add(int index, E element);

    E remove(int index);

    int indexOf(Object o);

    int lastIndexOf(Object o);

    ListIterator<E> listIterator();

    ListIterator<E> listIterator(int index);

    List<E> subList(int fromIndex, int toIndex);

    @SafeVarargs
    @SuppressWarnings("varargs")
    static <E> List<E> of(E... elements) {
        switch (elements.length) { // implicit null check of elements
            case 0:
                @SuppressWarnings("unchecked")
                var list = (List<E>) ImmutableCollections.EMPTY_LIST;
                return list;
            case 1:
                return new ImmutableCollections.List12<>(elements[0]);
            case 2:
                return new ImmutableCollections.List12<>(elements[0], elements[1]);
            default:
                return ImmutableCollections.listFromArray(elements);
        }
    }

    static <E> List<E> copyOf(Collection<? extends E> coll) {
        return ImmutableCollections.listCopy(coll);
    }
}

这其中比较重要的方法有：

boolean addAll(int index, Collection<? extends E> c);，将指定容器中的元素添加到指定位置。
default void sort(Comparator<? super E> c)，对容器中的元素进行排序（需要指定排序规则）。
E get(int index);，或许指定位置的元素。
E set(int index, E element);，对指定位置处的元素进行替换。
void add(int index, E element);，在指定位置处添加一个元素。
E remove(int index);，从指定位置删除元素，并返回该元素。
int indexOf(Object o);，返回指定元素在容器中第一次出现的位置，-1表示不存在。
int lastIndexOf(Object o);，返回指定元素在容器中最后一次出现的位置，-1表示不存在。
ListIterator<E> listIterator();，返回一个列表迭代器（list iterator）。
ListIterator<E> listIterator(int index);，返回一个列表迭代器（从指定位置处开始迭代）。
List<E> subList(int fromIndex, int toIndex);，返回一个子列表（不包含toIndex位置的元素），该子列表与原始列表共享底层存储，所以会互相影响。

下面对这些方法进行一些简单测试：

package ch8.list;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        Random random = new Random();
        list.add(random.nextInt(100));
        System.out.println(list);
        Integer[] numbers = new Integer[] { 1, 2, 3, 4, 5, 6, 7 };
        list.addAll(Arrays.asList(numbers));
        System.out.println(list);
        System.out.println(list.indexOf(3));
        list.add(3, 99);
        System.out.println(list);
        list.addAll(3, Arrays.asList(new Integer[] { 99, 1, 99 }));
        System.out.println(list);
        System.out.println(list.lastIndexOf(99));
        list.remove(new Integer(99));
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
        // [91]
        // [91, 1, 2, 3, 4, 5, 6, 7]
        // 3
        // [91, 1, 2, 99, 3, 4, 5, 6, 7]
        // [91, 1, 2, 99, 1, 99, 99, 3, 4, 5, 6, 7]
        // 6
        // [91, 1, 2, 1, 99, 99, 3, 4, 5, 6, 7]
        // [91, 1, 2, 1, 99, 3, 4, 5, 6, 7]
    }
}

需要注意的是，为了方便起见，这里使用的是基础类型int的包装类Integer组成的列表。因为列表内部比对元素时实际是通过Object.equals方法实现的，而该方法的默认实现是比对对象的地址值，而Integer等包装类和String等内置类型都对equals方法进行了重写，比对的是值而非地址。所以使用它们组成的容器进行举例更方便一些。

还要注意的是，因为容器的元素类型是Integer，所以对容器进行数字索引相关的操作需要额外注意，比如上边的list.remove(new Integer(99));，如果写成list.remove(99);就会触发“数组越界异常”。这是因为前者调用的是List.remove(Object o)这个方法，其作用是删除指定元素。而后者调用的是List.remove(int index)这个方法，其用途是从指定位置删除元素。显然我们这个容器还没有100个那么多的元素。这里的原理在于，当包装类参数组成的方法和基础元素组成的方法都可以满足调用时，编译器会优先选择后者。

Arrays.asList

还有一个需要说明的工具函数是Arrays.asList，这个方法可以将一个数组转换为List。

其具体定义：

    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

asList使用了可变参数列表，并返回一个ArrayList实现的List对象。

在Java编程笔记2：初始化和清理 - 魔芋红茶's blog (icexmoon.xyz)中我提到过可变参数列表，对于这种方式定义的形参，我们可以传递多个元素，也可以传递一整个数组，对于asList方法同样可以如此调用：

package ch8.aslist;

import java.util.Arrays;
import java.util.List;

class Fruit {
}

class Apple extends Fruit {
}

class Oranger extends Fruit {
}

class RedApple extends Apple {
}

class YellowApple extends Apple {
}

public class Main {
    public static void main(String[] args) {
        Fruit[] fruits = new Fruit[] { new Apple(), new Oranger(), new RedApple(), new YellowApple() };
        List<Fruit> list = Arrays.asList(fruits);
        List<Fruit> list2 = Arrays.asList(new RedApple(), new YellowApple());
        System.out.println(list2);
    }
}

利用asList方法和Colleciton.addAll方法可以方便地给容器批量添加元素：

...
public class Main {
    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList<Fruit>();
        fruits.addAll(Arrays.asList(new RedApple(), new YellowApple()));
        System.out.println(fruits);
        fruits.clear();
        Collections.addAll(fruits, new RedApple(), new YellowApple());
        System.out.println(fruits);
        // [ch8.aslist2.RedApple@2f92e0f4, ch8.aslist2.YellowApple@28a418fc]
        // [ch8.aslist2.RedApple@5305068a, ch8.aslist2.YellowApple@1f32e575]
    }
}

不过就像上面示例中的那样，用Collections.addAll方法可以同样实现类似的效果，而且更为方便。

不可修改的列表

此外，List还包含两个静态方法：

static <E> List<E> of(E... elements)
static <E> List<E> copyOf(Collection<? extends E> coll)

实际上of方法还有若干重载方法，其目的似乎是优化性能。

这两个方法的用途是返回一个不可修改的列表（unmodifiable lists）。

所谓不可修改的列表，有以下特征：

不能从列表中添加、删除、替换元素（但无法保证元素内容不被修改），任何此类操作都会抛出一个UnsupportedOperationException异常。
不允许null值存在，试图用null初始化一个不可修改的列表，会抛出一个NullPointerException异常。
如果所有元素都是可序列化的，列表就是可序列化的。
列表中元素的顺序，与给定的参数顺序或给定容器中的顺序一致。

下面是一个简单测试：

package ch8.un_list;

import java.util.List;

class MyInteger {
    private int number;

    public MyInteger(int number) {
        this.number = number;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        } else if (obj instanceof MyInteger) {
            MyInteger other = (MyInteger) obj;
            return other.number == this.number;
        } else {
            return super.equals(obj);
        }
    }

    @Override
    public String toString() {
        return Integer.toString(this.number);
    }

    public void setValue(int value) {
        this.number = value;
    }
}

public class Main {
    private static MyInteger[] getNumbers() {
        int length = 10;
        MyInteger[] numbers = new MyInteger[length];
        for (int i = 0; i < length; i++) {
            numbers[i] = new MyInteger(i);
        }
        return numbers;
    }

    public static void main(String[] args) {
        MyInteger[] numbers = getNumbers();
        List<MyInteger> list = List.of(numbers);
        System.out.println(list);
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        list.get(0).setValue(99);
        System.out.println(list);
        // [99, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        list.remove(1);
        // Exception in thread "main" java.lang.UnsupportedOperationException
    }
}

可以看到生成的“不可修改的列表”不能删除元素，但可以修改元素中的值（这是由MyInteger的实现决定的）。

迭代器

迭代器实际上是一种设计模式，在设计模式 with Python 9：迭代器模式 - 魔芋红茶's blog (icexmoon.xyz)中我有过详细说明。因为对容器进行迭代本身是一件编程中相当频繁的事情，所以大多数编程语言都会选择通过标准库甚至是内置语法对其进行支持。

Java通过接口Iterable和Iterator对此提供支持。

Iterable的定义：

public interface Iterable<T> {
    Iterator<T> iterator();
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Iterator的定义：

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

其中Iterable表示一个可迭代对象，而Iterator代表一个具体的迭代器。

这种实现方式和Python极为类似。

最为关键的是Iterator的hasNext和next两个方法，通过这两个方法就可以利用迭代器遍历容器中的元素。

这么做的好处在于可以将类本身的职责和迭代这个功能分离，让迭代器专门承担迭代的工作，下面用一个具体示例来进行说明：

package ch8.iterator2;

import java.util.Arrays;
import java.util.Iterator;
import java.util.Random;

class RandomNumbers implements Iterable<Integer> {
    private static Random random = new Random();
    private int[] numbers;

    public RandomNumbers(int size) {
        if (size <= 0) {
            throw new Error();
        }
        numbers = new int[size];
        for (int i = 0; i < size; i++) {
            numbers[i] = random.nextInt(100);
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(numbers);
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            private int cursor = -1;

            @Override
            public boolean hasNext() {
                if (cursor + 1 < numbers.length) {
                    return true;
                }
                return false;
            }

            @Override
            public Integer next() {
                cursor++;
                return numbers[cursor];
            }

        };
    }
}

public class Main {
    private static void printIterable(Iterable<Integer> iterable) {
        Iterator<Integer> iterator = iterable.iterator();
        while (iterator.hasNext()) {
            int num = iterator.next();
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        RandomNumbers rn = new RandomNumbers(10);
        System.out.println(rn);
        printIterable(rn);
        // [68, 31, 66, 75, 47, 45, 18, 48, 37, 58]
        // 68 31 66 75 47 45 18 48 37 58 
    }
}

在这个示例中，RandomNumbers类代表一个指定长度的随机整数序列，在让其实现了Iterator<Integer>接口后，就可以用类似printIterable函数中的方式对其进行遍历并输出。最妙的是printIterable函数本身具有相当的可复用性，用它可以遍历任何实现了Iterable<Integer>接口的类型，这就是迭代器模式的威力。

这里直接用匿名类实现了iterator方法，关于匿名类的说明见Java编程笔记7：内部类 - 魔芋红茶's blog (icexmoon.xyz)。

更妙的是，就像在Python中可以用for...in...语法来遍历实现了迭代器协议的类型那样，在Java中同样可以直接使用foreach语法来遍历实现了Iterable接口的类型：

...
public class Main {
    public static void main(String[] args) {
        RandomNumbers rn = new RandomNumbers(10);
        System.out.println(rn);
        for (int num : rn) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

这种方式无疑比之前的方式更为简洁，所以通常会使用这样的方式遍历可迭代对象。

列表迭代器

你可能已经注意到了，List接口有一个listIterator方法，会返回一个ListIterator类型的对象。实际上ListIterator是一个扩展自Iterator的接口：

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

之前介绍的普通的迭代器只能使用hasNext和next方法向前迭代，但ListIterator可以进行“双向迭代”。这体现在它多出来的这几个方法上：

这里的“前”指的是数组的右侧，数字索引增大的一方，“后”指的是数组的左侧。

hasPrevious是否可以向后迭代。
previous向后迭代，并返回一个元素。
nextIndex，返回向前迭代时下一个元素的数字索引。
previousIndex，返回向后迭代时下一个元素的数字索引。

除了这些必要的双向迭代所需的方法之外，它还提供一些修改容器中元素的方法：

remove，删除当前元素。
set，替换当前元素。
add，添加一个元素到当前位置。

这里对列表迭代器的使用进行简单演示：

package ch8.list_iterator;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<Integer>();
        Collections.addAll(numbers, 1, 2, 3, 4, 5);
        System.out.println(numbers);
        ListIterator<Integer> li = numbers.listIterator();
        while (li.hasNext()) {
            if (li.nextIndex() == 2) {
                li.add(Integer.valueOf(99));
            }
            System.out.print(li.next() + " ");
        }
        System.out.println();
        while (li.hasPrevious()) {
            System.out.print(li.previous() + " ");
        }
        System.out.println();
        // [1, 2, 3, 4, 5]
        // 1 2 3 4 5 
        // 5 4 3 99 2 1
    }
}

需要注意的是，add、remove等方法并非所有实现ListIterator的对象都必须实现的，比如之前提到的“不可修改的列表”，其实例的listIterator方法返回的列表迭代器显然就不会实现相关方法，尝试调用这些方法只会产生一个异常。

ArrayList

标准库中有两个最常见的实现了List接口的容器：

ArrayList
LinkedList

从名字就能看出，前者是基于数组实现的，后者是基于链表实现的。而它们的优缺点也的确和数组及链表相一致：

ArrayList优于随机访问，缺点是在任意位置增加和删除元素性能较差。
LinkedList优于在任意位置添加和删除元素，缺点在于随机访问性能较差。

之所以ArrayList在添加或删除元素时性能不佳，是因为其底层实现是数组，所以在添加或删除时需要重新创建数组，尤其是在添加元素时，考虑最简单的实现方式，如果每次添加一个新元素都需要重新申请一个长度+1的新数组，并进行数据拷贝，那么效率无疑是非常差的，但这点可以通过优化底层实现来解决。

ArrayList的实现方式其实非常类似于Go的内置类型切片。所以虽然ArrayList的底层数组实际上会用复杂的方式进行扩容，但我们依然可以用类似切片的思路实现一个简单的ArrayList：

package ch8.arraylist3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.ListIterator;

import ch8.list.List;

public class SimpleArrayList<E> implements List<E> {
    private static Object[] EMPTY_ARRAY = new Object[0];
    private Object[] array;
    private int size;
    private int cap;

    public SimpleArrayList() {
        array = EMPTY_ARRAY;
    }

    public SimpleArrayList(int cap) {
        array = new Object[cap];
        this.cap = cap;
    }

    public SimpleArrayList(Collection<? extends E> c) {
        Object[] newArray = c.toArray();
        if (newArray.length > 0) {
            size = newArray.length;
            cap = newArray.length;
            if (c.getClass() == ArrayList.class) {
                array = newArray;
            } else {
                array = Arrays.copyOf(newArray, newArray.length, Object[].class);
            }
        } else {
            array = EMPTY_ARRAY;
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int cursor = -1;

            @Override
            public boolean hasNext() {
                if (cursor + 1 < size) {
                    return true;
                }
                return false;
            }

            @Override
            public E next() {
                cursor++;
                return (E) array[cursor];
            }

        };
    }

    ...

    @Override
    public boolean add(Object e) {
        if (cap > size) {
            array[size] = e;
            size++;
        } else if (size == 0) {
            // 初始一次增加1个容量
            int initCap = 1;
            array = new Object[initCap];
            array[0] = e;
            cap = initCap;
            size = 1;
        } else {
            // 一次性扩容一倍容量
            int newSize = size + 1;
            int newCap = cap * 2;
            System.out.println("do array extends,new cap is " + newCap);
            Object[] newArray = new Object[newCap];
            for (int i = 0; i < array.length; i++) {
                newArray[i] = array[i];
            }
            newArray[array.length] = e;
            array = newArray;
            cap = newCap;
            size = newSize;
        }
        return true;
    }

    ...

    public static void main(String[] args) {
        SimpleArrayList<Integer> sal = new SimpleArrayList<>();
        fillSimpleArrayList(sal);
        printSimpleArrayList(sal);
        sal = new SimpleArrayList<>(10);
        fillSimpleArrayList(sal);
        printSimpleArrayList(sal);
        sal = new SimpleArrayList<>(Arrays.asList(new Integer[]{1,2,3,4,5}));
        fillSimpleArrayList(sal);
        printSimpleArrayList(sal);
        // do array extends,new cap is 2
        // do array extends,new cap is 4
        // do array extends,new cap is 8
        // do array extends,new cap is 16
        // 0 1 2 3 4 5 6 7 8 9
        // 0 1 2 3 4 5 6 7 8 9
        // do array extends,new cap is 10
        // do array extends,new cap is 20
        // 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9
    }

    private static void fillSimpleArrayList(SimpleArrayList<Integer> sal) {
        for (int i = 0; i < 10; i++) {
            sal.add(i);
        }
    }

    private static void printSimpleArrayList(SimpleArrayList sal) {
        for (Object object : sal) {
            System.out.print(object + " ");
        }
        System.out.println();
    }

}

和Go的切片类似，在SimpleArrayList内部，使用cap属性保存当前底层数组的容量，用size保存当前列表中的实际元素个数。并且在需要对底层数组扩容时，采取每次在当前容量上扩容一倍的方式扩展底层数组的实际长度。

测试也说明了这一点，底层数组的实际容量以2、4、8、16的方式扩展，这无疑比每添加一个元素就扩展一次底层数组的方式要性能优越的多。

同时SimpleArrayList还提供一个接收一个int参数的构造函数，该构造函数可以在初始化的时候直接创建一个指定容量的底层数组。如果你在使用SimpleArrayList的时候已经知道要添加的元素个数，这个构造函数就非常有用，可以避免不必要的底层数组扩展带来的额外开销。

此外SimpleArrayList还可以通过给定一个Collection的方式来初始化。

实际上，真实的ArrayList虽然采用的并非这种简单策略进行底层数组扩容，但其原理和行为都是类似的，并且同样提供三种构造函数用于初始化ArrayList，所以这里的SimpleArrayList还是相当的有借鉴意义。

完整的SimpleArrayList定义见java-notebook/SimpleArrayList.java at main · icexmoon/java-notebook (github.com)，当然我只实现了关键的List接口的方法，其余方法都是自动生成代码，有兴趣的童鞋可以继续完善这个代码。

LinkedList

前面已经说过了，之所以LinkedList随机读写性能较差，因为它的底层实现是链表，这是链表这个数据结构所具有的特性。实际上同样可以通过改善实现方式来进行优化，比如说用一个额外数组来维护链表的数字索引，当然这也会带来一些其他的麻烦。事实上每种类型的数据结构都有其优缺点，并没有尽善尽美的数据结构。

下面展示一个我实现的简单的LinkedList，作为一个实现机制的示例：

package ch8.linkedlist;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.ListIterator;

import ch8.list.List;

public class SimpleLinkedList<T> implements List<T> {
    private Node<T> first = null;

    public SimpleLinkedList() {
    }

    public SimpleLinkedList(Collection<? extends T> c) {
        if (c.size() > 0) {
            boolean isInited = false;
            Node<T> currentNode = null;
            for (T t : c) {
                if (!isInited) {
                    first = new Node<T>(t);
                    currentNode = first;
                    isInited = true;
                    continue;
                }
                Node<T> newNode = new Node<T>(t);
                currentNode.link(newNode);
                currentNode = newNode;
            }
        }
    }

	...
        
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            Node<T> current;

            @Override
            public boolean hasNext() {
                if (first == null) {
                    return false;
                } else if (current == null) {
                    return true;
                } else {
                    return current.hasNext();
                }
            }

            @Override
            public T next() {
                if (first == null) {
                    return null;
                } else if (current == null) {
                    current = first;
                    return current.getData();
                } else {
                    current = current.getNext();
                    return current.getData();
                }
            }

        };
    }

	...
    @Override
    public boolean add(T e) {
        if (first == null) {
            first = new Node<T>(e);
        } else {
            Node<T> newNode = new Node<T>(e);
            Node<T> lastNode = getLastNode();
            lastNode.link(newNode);
        }
        return true;
    }
	
    ...

    private Node<T> getLastNode() {
        if (first == null) {
            return first;
        }
        Node<T> current = first;
        while (true) {
            if (current.hasNext()) {
                current = current.getNext();
            } else {
                break;
            }
        }
        return current;
    }

    private class Node<T> {
        private Object data;
        private Node<T> next;

        public Node(T data) {
            this.data = data;
        }

        public T getData() {
            return (T) data;
        }

        public void link(Node<T> next) {
            this.next = next;
        }

        public boolean hasNext() {
            return next != null;
        }

        public Node<T> getNext() {
            return next;
        }
    }

    public static void main(String[] args) {
        SimpleLinkedList<Integer> numbers = new SimpleLinkedList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        for (Integer integer : numbers) {
            System.out.print(integer + " ");
        }
        System.out.println();
        numbers = new SimpleLinkedList<>(Arrays.asList(new Integer[] { 1, 2, 3, 4, 5 }));
        numbers.add(99);
        for (Integer integer : numbers) {
            System.out.print(integer + " ");
        }
    }
}

同样的，这个类只实现了演示所需的方法，大部分List的方法都没有实现。但这个类依然可以说明底层的链表机制。

这里使用私有内部类Node作为链表的实现类，这是考虑到链表节点仅应当被SimpleLinkedList使用。

这里的实现相当“粗糙”，可以实现进一步优化，比如用一个额外的Node<T>引用来保存最后一个链表节点，这样在调用add方法的时候就不需要对整个链表进行遍历，只需要给最后一个节点追加新节点即可。

真实的LinkedList类在List接口的基础上添加了大量额外方法，其中有一些方法功能相近，比如：

package ch8.linkedlist;

import java.util.Collections;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> ll = new LinkedList<>();
        Collections.addAll(ll, 1, 2, 3, 4, 5);
        System.out.println(ll.getFirst());
        System.out.println(ll.element());
        System.out.println(ll.peek());
        // 1
        // 1
        // 1
    }
}

getFirst、element、peek三种方法都可以返回首个元素，这可能会使一些开发者迷惑。

实际上这些方法之所以这样设计，是为了让LinkedList可以更多地“模拟”一些其他的数据结构，比如栈或队列。

Stack

利用LinkedList我们可以很容易地实现一个栈：

package ch8.stack;

import java.util.LinkedList;

public class Stack<T> {
    private LinkedList<T> datas = new LinkedList<>();

    public T pop() {
        return datas.removeFirst();
    }

    public void push(T data) {
        datas.addFirst(data);
    }

    public T peek() {
        return datas.getFirst();
    }

    public boolean empty() {
        return datas.isEmpty();
    }

    @Override
    public String toString() {
        return datas.toString();
    }
}

进行一个简单测试：

package ch8.stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < 5; i++) {
            System.out.println("push " + i);
            stack.push(i);
            System.out.println(stack);
        }
        System.out.println("starting pop stack.");
        while (!stack.empty()) {
            Integer num = stack.pop();
            System.out.println(num + " is poped.");
            System.out.println(stack);
        }
        // push 0
        // [0]
        // push 1
        // [1, 0]
        // push 2
        // [2, 1, 0]
        // push 3
        // [3, 2, 1, 0]
        // push 4
        // [4, 3, 2, 1, 0]
        // starting pop stack.
        // 4 is poped.
        // [3, 2, 1, 0]
        // 3 is poped.
        // [2, 1, 0]
        // 2 is poped.
        // [1, 0]
        // 1 is poped.
        // [0]
        // 0 is poped.
        // []
    }
}

实际上标准库同样实现了一个Stack：java.util.Stack。但该类实际上是通过继承Vector类来实现的，除了提供栈必须的pop、push等方法外，继承了大量本不需要的Vector的方法，以设计模式的标准来看的话，这样做并不是很合适，所以通过上面的方式实现的Stack类更符合单一行为原则。

本来打算用一篇文章总结完容器的，发现并不现实，篇幅过长，其余的部分放在下篇好了。

谢谢阅读。

参考资料：

本作品采用知识共享署名 4.0 国际许可协议进行许可