看看源码 -- Java集合(List接口篇)

看看源码 -- Java集合(List接口篇)

Scroll Down

List<E>接口

List接口继承自Collection接口; List集合代表的是一个有序, 可重复的集合, 集合中的每一个元素都有其对应的索引

List新增接口方法

// 在指定位置添加元素
void add(int index, E element);
boolean addAll(int index, Collection<? extends E> c);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
E get(int index);
E set(int index, E element);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index); //返回从指定位置开始迭代的迭代器
List<E> subList(int fromIndex, int toIndex);

专门为List集合准备的迭代器, 提供了反向遍历集合的方式previous()等函数和索引遍历方式nexIndex()等函数

public interface ListIterator<E> extends Iterator<E> {

 boolean hasNext();

 E next();

 boolean hasPrevious();

 E previous();

 int nextIndex();

 int previousIndex();

 void remove(); // 取消了Iterator提供的默认实现, 变为接口方法

 void set(E e); // 新增修改函数, 替换上一次调用next()或previous()返回的元素

 void add(E e); // 新增插入函数, 插入到下次调用next()函数返回的元素之前
}

List默认方法

// 通过传入一个一元运算符对每个元素进行该一元运算
default void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final ListIterator<E> li = this.listIterator();
    while (li.hasNext()) {
        // 这里就是先调用next()函数, 然后处理返回值, 再将处理后的结果拿去修改原来的值, 注意ListIterator的set函数的作用, 是修改上一次调用next()函数对应的元素
        li.set(operator.apply(li.next()));
    }
}

// 通过传入一个比较器来对元素进行排序
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);
    }
}

// 重写了Collection提供的默认方法
default Spliterator<E> spliterator() {
    // 根据族谱图, 只有ArrayList和Vector会实现RandomAccess接口
    if (this instanceof RandomAccess) {
        return new AbstractList.RandomAccessSpliterator<>(this);
    } else {
        return Spliterators.spliterator(this, Spliterator.ORDERED);
    }
}

一元运算符

@FunctionalInterface
public interface UnaryOperator<T> extends Function<T, T> {
 // 重写父类方法, 注意: 重写时方法返回值可以不一样, 但子类的返回值必须时父类返回值的子类
 static <T> UnaryOperator<T> identity() {
     return t -> t;
 }
}


@FunctionalInterface
public interface Function<T, R> {

 // 函数处理逻辑
 R apply(T t);

 // 传入一个再执行函数处理逻辑前执行的函数, 返回组合后的函数
 default <V> Function<V, R> compose(Function<? super V, ? extends T> before) {
     Objects.requireNonNull(before);
     return (V v) -> apply(before.apply(v));
 }

 // 跟上面一样, 变成处理之后了而已
 default <V> Function<T, V> andThen(Function<? super R, ? extends V> after) {
     Objects.requireNonNull(after);
     return (T t) -> after.apply(apply(t));
 }

 // 返回一个不对传入值进行任何处理的函数
 static <T> Function<T, T> identity() {
     return t -> t;
 }
}

比较器

@FunctionalInterface
public interface Comparator<T> {

 // 待实现的比较逻辑, 当第一个参数小于,等于或大于第二个参数时,返回负整数,零或正整数。
 int compare(T o1, T o2);

 // 判定两个比较器是否相等
 boolean equals(Object obj);

 // 获得相反的比较器
 default Comparator<T> reversed() {
     return Collections.reverseOrder(this);
 }

 // 返回一个新的比较器, 新的比较器会先使用当前比较器进行比较, 若得到的结果相等就使用第二个比较器进行比较
 default Comparator<T> thenComparing(Comparator<? super T> other) {
     Objects.requireNonNull(other);
     return (Comparator<T> & Serializable) (c1, c2) -> {
         int res = compare(c1, c2);
         return (res != 0) ? res : other.compare(c1, c2);
     };
 }

 // 返回新的比较器, 同上面一样, 只是在进行第二次比较的时候会先使用keyExtractor函数对比较的两个值进行处理了再调用传入的比较器进行比较
 default <U> Comparator<T> thenComparing(
         Function<? super T, ? extends U> keyExtractor,
         Comparator<? super U> keyComparator)
 {
     return thenComparing(comparing(keyExtractor, keyComparator));
 }

 // 跟上面一样, 只是要求处理函数的返回值本身实现了Comparable接口
 default <U extends Comparable<? super U>> Comparator<T> thenComparing(
         Function<? super T, ? extends U> keyExtractor)
 {
     return thenComparing(comparing(keyExtractor));
 }

 // 下面三个是再第一次比较相等后将比较对象转为数值来比较
 default Comparator<T> thenComparingInt(ToIntFunction<? super T> keyExtractor) {
     return thenComparing(comparingInt(keyExtractor));
 }

 default Comparator<T> thenComparingLong(ToLongFunction<? super T> keyExtractor) {
     return thenComparing(comparingLong(keyExtractor));
 }

 default Comparator<T> thenComparingDouble(ToDoubleFunction<? super T> keyExtractor) {
     return thenComparing(comparingDouble(keyExtractor));
 }

 public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
     return Collections.reverseOrder();
 }

 @SuppressWarnings("unchecked")
 public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
     return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
 }

 public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) {
     return new Comparators.NullComparator<>(true, comparator);
 }

 public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator) {
     return new Comparators.NullComparator<>(false, comparator);
 }

 public static <T, U> Comparator<T> comparing(
         Function<? super T, ? extends U> keyExtractor,
         Comparator<? super U> keyComparator)
 {
     Objects.requireNonNull(keyExtractor);
     Objects.requireNonNull(keyComparator);
     return (Comparator<T> & Serializable)
         (c1, c2) -> keyComparator.compare(keyExtractor.apply(c1),
                                           keyExtractor.apply(c2));
 }

 public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
         Function<? super T, ? extends U> keyExtractor)
 {
     Objects.requireNonNull(keyExtractor);
     return (Comparator<T> & Serializable)
         (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
 }

 public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
     Objects.requireNonNull(keyExtractor);
     return (Comparator<T> & Serializable)
         (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
 }

 public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> keyExtractor) {
     Objects.requireNonNull(keyExtractor);
     return (Comparator<T> & Serializable)
         (c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2));
 }

 public static<T> Comparator<T> comparingDouble(ToDoubleFunction<? super T> keyExtractor) {
     Objects.requireNonNull(keyExtractor);
     return (Comparator<T> & Serializable)
         (c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2));
 }
}

List静态方法

// 将传入的元素转为一个不可变的集合 
static <E> List<E> of(E... elements) {
     switch (elements.length) { // implicit null check of elements
         case 0:
             return ImmutableCollections.emptyList();
         case 1:
             // 这里可以看到, 返回的并不是List, 而是List12, 这个类只是实现List接口
             return new ImmutableCollections.List12<>(elements[0]);
         case 2:
             return new ImmutableCollections.List12<>(elements[0], elements[1]);
         default:
             // 超过两个元素后调用返回的是ListN对象
             return new ImmutableCollections.ListN<>(elements);
     }
 }

// 复制一个集合, 复制的集合也不可变哦
static <E> List<E> copyOf(Collection<? extends E> coll) {
    return ImmutableCollections.listCopy(coll);
}

ImmutableCollections: Immutable表示一成不变的, 也就是用这个集合工具得到的集合都是无法改变的, 来, 看看他咋个做的, 为啥不可变; 好家伙, 一看源码1000+行, 我就节选了, 只看上面遇到的

来来来, 先看为啥不可变

// 这是这个类里的一个方法, 用于抛出UnsupportedOperationException异常
static UnsupportedOperationException uoe() { return new UnsupportedOperationException(); }

// 继承了AbstractCollection类, 好家伙, 把所有方法都重写为抛异常, 是个狠人, 破案了, 怪不得不可变
static abstract class AbstractImmutableCollection<E> extends AbstractCollection<E> {
 // all mutating methods throw UnsupportedOperationException
 @Override public boolean add(E e) { throw uoe(); }
 @Override public boolean addAll(Collection<? extends E> c) { throw uoe(); }
 @Override public void    clear() { throw uoe(); }
 @Override public boolean remove(Object o) { throw uoe(); }
 @Override public boolean removeAll(Collection<?> c) { throw uoe(); }
 @Override public boolean removeIf(Predicate<? super E> filter) { throw uoe(); }
 @Override public boolean retainAll(Collection<?> c) { throw uoe(); }
}

再继续看

// 这个应该就是上面那个ListN和List12的父类了, 好家伙, 操作的方法一个不留, 全给抛异常
static abstract class AbstractImmutableList<E> extends AbstractImmutableCollection<E>
         implements List<E>, RandomAccess {
 @Override public void    add(int index, E element) { throw uoe(); }
     @Override public boolean addAll(int index, Collection<? extends E> c) { throw uoe(); }
     @Override public E       remove(int index) { throw uoe(); }
     @Override public void    replaceAll(UnaryOperator<E> operator) { throw uoe(); }
     @Override public E       set(int index, E element) { throw uoe(); }
     @Override public void    sort(Comparator<? super E> c) { throw uoe(); }
 // 其他List的方法他有好好实现, 没有作怪
}

再往下

// 不用想, 迭代器的修改方法也不能幸免
static final class ListItr<E> implements ListIterator<E> {

 @Stable
 private final boolean isListIterator;

 public void remove() {
     throw uoe();
 }

 public boolean hasPrevious() {
     if (!isListIterator) {
         throw uoe();
     }
     return cursor != 0;
 }

 public E previous() {
     if (!isListIterator) {
         throw uoe();
     }
     try {
         int i = cursor - 1;
         E previous = list.get(i);
         cursor = i;
         return previous;
     } catch (IndexOutOfBoundsException e) {
         throw new NoSuchElementException();
     }
 }

 public int nextIndex() {
     if (!isListIterator) {
         throw uoe();
     }
     return cursor;
 }

 public int previousIndex() {
     if (!isListIterator) {
         throw uoe();
     }
     return cursor - 1;
 }

 public void set(E e) {
     throw uoe();
 }

 public void add(E e) {
     throw uoe();
 }
}

再看一下剩下的, 就看看名字就知道了

static final class SubList<E> extends AbstractImmutableList<E>
         implements RandomAccess {}
// 我们要找的两个小伙伴
static final class List12<E> extends AbstractImmutableList<E>
         implements Serializable{}
static final class ListN<E> extends AbstractImmutableList<E>
         implements Serializable{}
// 往下继续瞄了两眼, Set, Map 都没能幸免哦
static abstract class AbstractImmutableSet<E> extends AbstractImmutableCollection<E>
         implements Set<E>{}
static final class Set12<E> extends AbstractImmutableSet<E>
         implements Serializable{}
static final class SetN<E> extends AbstractImmutableSet<E>
         implements Serializable{}
abstract static class AbstractImmutableMap<K,V> extends AbstractMap<K,V> implements Serializable

总结一下: 这就是"我得到了你的人, 却得不到你的心"的真实案例么!

AbstractList<E>抽象类

AbstractList<E>继承了AbstractCollection, 并实现了List接口

实现的方法

public boolean add(E e) {
    add(size(), e);
    return true;
}

// 增删方法默认抛出异常
public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    throw new UnsupportedOperationException();
}

// 查找第一个与传入对象相等的对象再集合中的位置, 为找到返回-1
public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return it.previousIndex();
    }
    return -1;
}

// 查找最后一个与传入对象相等的对象再集合中的位置, 为找到返回-1
public int lastIndexOf(Object o) {
    ListIterator<E> it = listIterator(size());
    if (o==null) {
        while (it.hasPrevious())
            if (it.previous()==null)
                return it.nextIndex();
    } else {
        while (it.hasPrevious())
            if (o.equals(it.previous()))
                return it.nextIndex();
    }
    return -1;
}

// Itr 是内部实现Iterator接口的实现类, 下面会说
public Iterator<E> iterator() {
    return new Itr();
}

public ListIterator<E> listIterator() {
    return listIterator(0);
}

protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();
        it.remove();
    }
}

//
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;
    ListIterator<E> e1 = listIterator();
    // 强转一下, 来获取迭代器
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

其实Abstract实现了大部分方法, 只有size()get(int index)两个方法没有实现, 不过某些方法的实现是直接抛的异常

引入的变量

// 用于记录当前集合结构被修改的次数, 结构修改指的是集合的大小被修改
protected transient int modCount = 0;

实现的类

AbstractList在内部创建了Iterator, ListIterator, Spliterator等接口的实现类

Iterator实现类
private class Itr implements Iterator<E> {
    // 指向当前位置的指针
    int cursor = 0;

    // 指向上一次位置的指针
    int lastRet = -1;

    // 记录一下数组结构当前被修改的次数, 主要是用于检测并发修改,
    // 如果发生了并发修改就会报错
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size();
    }

    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }

    // 检测并发修改
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
ListIterator实现类
private class ListItr extends Itr implements ListIterator<E> {
   // 没啥特别的, 就是新增了反向遍历的方法实现
}
SplIterator实现类
static final class RandomAccessSpliterator<E> implements Spliterator<E> {

    private final List<E> list;
    // 指向当前位置的指针
    private int index; 
    // 未使用时为-1, 使用后为该迭代器能达到的最大索引,也就是能访问到的最后一个元素的位置
    private int fence;

    // 当List为AbstractList的子类时有效
    private final AbstractList<E> alist;
    private int expectedModCount; // 当fence被设置时初始化

    RandomAccessSpliterator(List<E> list) {
        assert list instanceof RandomAccess;

        this.list = list;
        this.index = 0;
        this.fence = -1;

        this.alist = list instanceof AbstractList ? (AbstractList<E>) list : null;
        this.expectedModCount = alist != null ? alist.modCount : 0;
    }

    // 根据父可拆分迭代器创建新的迭代器
    private RandomAccessSpliterator(RandomAccessSpliterator<E> parent,
                            int origin, int fence) {
        this.list = parent.list;
        this.index = origin;
        this.fence = fence;

        this.alist = parent.alist;
        this.expectedModCount = parent.expectedModCount;
    }

    private int getFence() { // initialize fence to size on first use
        int hi;
        List<E> lst = list;
        if ((hi = fence) < 0) {
            if (alist != null) {
                expectedModCount = alist.modCount;
            }
            hi = fence = lst.size();
        }
        return hi;
    }

    // 尝试去分割迭代器
    // 分割的方式是从当前迭代器指向的位置, 迭代器能达到的最远位置, 然后从中间分开
    // 返回新的迭代器的触及范围为原迭代器触及范围的前半部分
    // 原迭代器的触及访问将变为自己分割前的后半部分
    public Spliterator<E> trySplit() {
        // >>> 无符号右移一位, 牛批, 直接得到中值
        int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
        return (lo >= mid) ? null : // divide range in half unless too small
                new RandomAccessSpliterator<>(this, lo, index = mid);
    }

    // 对剩余能访问的元素进行消费, 消费后指针仍指向原位置
    public boolean tryAdvance(Consumer<? super E> action) {
        if (action == null)
            throw new NullPointerException();
        int hi = getFence(), i = index;
        if (i < hi) {
            index = i + 1;
            action.accept(get(list, i));
            checkAbstractListModCount(alist, expectedModCount);
            return true;
        }
        return false;
    }

    // 遍历消费剩余能访问的元素, 消费后指针指可触及范围的最后
    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        List<E> lst = list;
        int hi = getFence();
        int i = index;
        index = hi; //先调整指针再消费元素, 减少并发问题, 防止消费时报错导致指针无法后移
        for (; i < hi; i++) {
            action.accept(get(lst, i));
        }
        checkAbstractListModCount(alist, expectedModCount);
    }

    // 计算当前迭代器的触及范围的大小
    public long estimateSize() {
        return (long) (getFence() - index);
    }

    public int characteristics() {
        return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
    }

    // 获取当前迭代器指向的元素
    private static <E> E get(List<E> list, int i) {
        try {
            return list.get(i);
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    // 检测迭代器对应的集合是否被并发修改, 与Iterator差不多
    static void checkAbstractListModCount(AbstractList<?> alist, int expectedModCount) {
        if (alist != null && alist.modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
}
AbstractList实现类

是的, AbstractList在自己内部实现了自己

SubList: 子集合类

private static class SubList<E> extends AbstractList<E> {
    private final AbstractList<E> root; //根集合
    private final SubList<E> parent; // 父集合
    private final int offset; // 偏移量
    protected int size; // 集合尺寸

    public SubList(AbstractList<E> root, int fromIndex, int toIndex) {
        this.root = root;
        this.parent = null;
        this.offset = fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = root.modCount;
    }

    protected SubList(SubList<E> parent, int fromIndex, int toIndex) {
        this.root = parent.root;
        this.parent = parent;
        this.offset = parent.offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = root.modCount;
    }

    // 可以看到, 子集合最终操作的原集合
    public E set(int index, E element) {
        Objects.checkIndex(index, size);
        checkForComodification();
        return root.set(offset + index, element);
    }


    public Iterator<E> iterator() {
        return listIterator();
    }

    public ListIterator<E> listIterator(int index) {
        checkForComodification();
        rangeCheckForAdd(index);
        // 匿名内部类,通过调用根集合的迭代器来操作
        return new ListIterator<E>() {
            private final ListIterator<E> i =
                root.listIterator(offset + index);
            // 省略其他方法, 都是调用这个根集合迭代器操作的
        }
    }

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList<>(this, fromIndex, toIndex);
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    // 同样有并发修改检测
    private void checkForComodification() {
        if (root.modCount != this.modCount)
            throw new ConcurrentModificationException();
    }
    private void updateSizeAndModCount(int sizeChange) {
        SubList<E> slist = this;
        do {
            slist.size += sizeChange;
            slist.modCount = root.modCount;
            slist = slist.parent;
        } while (slist != null);
    }
}
SubList子类
// 继承了上面AbstractList的实现类SubList
// 没啥新东西, 就是换个名字, 然后实现RandomAccess接口而已
private static class RandomAccessSubList<E>
    extends SubList<E> implements RandomAccess {

    RandomAccessSubList(AbstractList<E> root,
                        int fromIndex, int toIndex) {
        super(root, fromIndex, toIndex);
    }
    
    RandomAccessSubList(RandomAccessSubList<E> parent,
                        int fromIndex, int toIndex) {
        super(parent, fromIndex, toIndex);
    }

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new RandomAccessSubList<>(this, fromIndex, toIndex);
    }
}

注意:

这里实现的这些类, 都有private关键词修饰, 并且除了SubList和其子类为静态类 外, 其他都为普通内部类, 也就是说, 上面实现的这些类只有他们自己内部才可以使用, 不止是AbstractList, 所有集合的实现类都自己重新实现了迭代器, 可拆分迭代器和SubList

List实现类

ArrayList

ArrayList实现了List, RandomAccess, Cloneable, Serializable等接口, 继承了AbstractList抽象类 , 目前遇到的第三个集合的实现类; 什么? 这居然是第三个? 是的, 前两个分别是在AbstractList里遇到的哦, SubListRandomAccessSubList

好了, 上源码, 额..., 好家伙, 1700+, 我们看关键的吧, 先看看声明

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

新增的属性

// 集合的默认大小
private static final int DEFAULT_CAPACITY = 10;

// 空集合的对象, 所有空集合里面都存的这个玩意,
// 注意: 这是静态的, 也就是所有空集合共享一个, 并且final修饰, 无法改变
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认容量空元素数据, 用于与EMPTY_ELEMENTDATA区别; 我也没懂这是干嘛的, 先往下看
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 保存数据的数组, 任何 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的
// 空集合在添加第一个元素是都会扩大容量为 DEFAULT_CAPACITY
transient Object[] elementData;

// 集合大小
private int size;

// 集合的最大尺寸 2^31 - 1 - 8 (最大整数减8)
// 一些虚拟机在数组中保留一些标题字, 所以得预留一点空间
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

值得注意的是, 所有保存数据的数组数据类型都是Object, 而不是泛型E, 虽然编译器会抹掉泛型, 也就是说, 这里的E是只是做一个标志, 如果我们创建集合的时候不指定E, 那一个集合是可以保存多个类型的

构造函数

// 可以传入一个容量值来初始化集合大小
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 用一个集合来初始化ArrayList, 注意, 这里是浅拷贝
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

// 当然也可以不传, 不传的话就直接赋值为默认空集合数据
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

新提供的方法

// 调整集合最大容量至当前容量
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            : Arrays.copyOf(elementData, size);
    }
}

// 增加结合集合容量
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,
                                       newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

// 快速删除元素
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

总结一下:

ArrayList主要是对接口AbstractList方法提供了具体的实现, 没有增添新的东西,

在实现的方法上,. 有AbstractList有一定的区别,AbstractList在实现方法上基本都是 采用迭代器来访问的元素, 原因是AbstractList还不是真正的实现类, 所以没有确定具体保存数据的方式, 只能使用迭代器来访问; 而ArrayList不一样, 它已经是具体的实现类了, 且使用的是能够随机访问的数组来保存数据, 所以, ArrayList在实现时重写了AbstractList已经实现的一些方法, 利用了数组能够随机访问的特点, 直接在数组上对集合进行了操作(且使用了较多的for循环), 而不是使用迭代器

还有就是, ArrayList内部也同样实现了迭代器

Vector

先看看声明, emmmm, 其实跟ArrayList是一样的

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

新增的属性

// 跟ArrayList一样用于保存元素的数组
protected Object[] elementData;

// 相当于ArrayList的size
protected int elementCount;

// 每次容量扩张时的增长量
protected int capacityIncrement;

// 跟ArrayList一样
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

属性上与ArrayList相比, ArrayList采用静态变量来保存一些常量, 除了增长量还有默认容量, 空集合等常量, Vector的默认容量也是10, 不过是直接在构造器里写死的,直接调用的带参构造this(10)

实现的的方法

public synchronized int hashCode() {
    return super.hashCode();
}

public synchronized String toString() {
    return super.toString();
}

....

Vector几乎重写了所有方法, 且将所有方法都带上了synchronized关键字, 可以看到, 连toString, hashCode这些方法都带上了synchronized关键字, 方法的实现上的话, 都差不多, 同意利用了数组的随机访问特点

Stack

Stack是Vector的子类, 利用Vector实现的栈这种数据结构

新增的方法
// 模拟入栈
public E push(E item) {
    addElement(item);

    return item;
}

// 模拟出栈
public synchronized E pop() {
    E obj;
    int len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

// 获取栈顶元素, 但不出栈
public synchronized E peek() {
    int len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

// 清空栈
public boolean empty() {
    return size() == 0;
}

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}