集合、Collection 接口、List接口

集合的理解和好处

前面，我们保存多个数据可以使用数组，但数组有不足的地方

数组

数组的长度创建时必须指定，而且一定指定，不能修改
保存的必须为同一类型的元素

使用数组进行增加/删除的代码比较麻烦

Person[] pers = new Person[1];
pers[0] = new Person();

// 增添新的Person对象
Person[] pers2 = new Person[pers.length + 1];
for (int i = 0; i < pers.length; i++) {
    pers2[i] = pers[i];
}
pers2[pers2.length - 1] = new Person();

集合
1. 可以动态保存任意多个对象，使用比较方便
2. 提供了一系列方便操作对象的方法：add、remove、set、get等
3. 使用集合添加、删除新元素的代码简洁明了

集合框架体系

Java集合类很多，主要分为两类：

单列集合（Collection）

Collection 接口有两个重要的子接口 List 和 Set，它们的子类都是单列集合。

双列集合（Map）

存放的一个元素包含两个值 key 和 value

Collection 接口和常用方法

Collection 接口实现类特点

public interface Collection<E> extends Iterable<E>

Collection 实现子类可以存放对各元素，每个元素可以是Object
有些Collection的实现类，可以存放重复的元素，有些不可以
Collection的实现类，有些是有序的（List），有些不是有序的（Set）
Collection接口没有直接的实现子类，是通过它的子接口 Set 和 List 来实现的

Collection 接口的常用方法

boolean	add(E e)
boolean	addAll(Collection<? extends E> c)
void	clear()
boolean	contains(Object o)
boolean	containsAll(Collection<?> c)
boolean	isEmpty()
Iterator<E>	iterator()
boolean	remove(Object o)
boolean	removeAll(Collection<?> c)
int	size()
Object[]	toArray()
<T> T[]	toArray(T[] a)

Collection 接口遍历元素

public interface Iterator<E>

boolean	hasNext() //用于判断集合中是否还有下一个元素可以访问。
E	next() 	//返回迭代器的下一个元素，并将迭代器的指针移到下一个位置。
default void	remove() //从集合中删除迭代器最后访问的元素（可选操作）

Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素
所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用以返回一个是实现了 Iterator 接口的对象，即可以返回一个迭代器

Iterator 用于遍历集合，本身不存放对象

注意：在调用 iterator.next() 方法之前必须要调用 iterator.hasNext() 进行检测。若不调用，且下一条记录无效，直接调用 it.next() 会抛出 NoSuchElementException 异常。

// 1. 先得到 col 对应的迭代器
// 2. 使用while循环遍历
 Iterator iterator = col.iterator();
// 快速生成 while, idea 快捷键 itit
while (iterator.hasNext()) {
    Object obj = iterator.next();
    System.out.println(obj);
}
// 快捷键提示 ctrl + j
// 3.当退出 while 或，这是iterator 指向最后的元素
//          iterator.next(); // SuchElementException
// 如果希望再次遍历，需要重置迭代器
iterator = col.iterator();


// Collection 接口遍历对象2 -- for 循环增强， 底层依然是迭代器，快捷键 I
for (Object o : col) {
    System.out.println("book=" + o);
}

List 接口和常用方法

List 接口基本介绍

List 接口是 Collection 接口的子接口

List 集合类中元素有序（即添加顺序和取出顺序一致，并且可以重复）
List 集合中的每个元素都有其对应的顺序索引，即支持索引
JDK API 中 List 接口的实现类

List 接口的常用方法

// List 集合里添加了一些根据索引来操作集合元素的方法
void	add(int index, E element)
boolean	addAll(int index, Collection<? extends E> c)
E	get(int index)
int	indexOf(Object o)
int	lastIndexOf(Object o)
E	remove(int index)
E	set(int index, E element)
default void	sort(Comparator<? super E> c)
List<E>	subList(int fromIndex, int toIndex)

List 接口遍历方式（ArrayLIst，LInkedList， Vector）

// 方式一：使用iterator
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    Object obj = iterator.next();
    System.out.println(obj);
}
// 方式二：使用增强for
 for (Object o : list) {
      System.out.println(o);
}
// 方式三：使用for循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

ArrayList 注意事项

permits all elements，includeing null，ArrayList 可以加入null，并且可以加入多个
ArrayList 是由数组来实现数据存储的
ArrayList 基本等同于 Vector，除了 ArrayList 线程是不安全（但是执行效率更高），在多线程情况下，不建议使用ArrayList

ArrayList 的底层操作机制源码分析

ArrayList 中维护了一个Object 类型的数组 elementData transient Object[] elementData;
当创建 ArrayList 对象时，如果使用的时无参构造器，则初始 elementData 容量为0，第一次添加，扩容 elementData 为10，如需要再次扩容，则扩容为 elementData 为1.5 倍
如果使用的是指定大小的构造器，则初始 elementData 的容量为指定大小，如果需要扩容，则直接扩容 elementData 为1.5倍

// 使用无参构造器创建 ArrayList
ArrayList list = new ArrayList();

// 创建了一个空的 elementData 数组
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

  // 使用for 给list结合添加1-10数据
for (int i = 1; i <= 10; i++) {
    list.add(i);
}

// 执行 list.add
// (1) 先确定是否需要扩容
// (2) 然后再执行赋值
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

// 该方法确定 minCapacity
// (1) 第一次扩容为10
private void ensureCapacityInternal(int minCapacity) { // 1
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// (1)modCount++ 记录集合被修改改的次数
// (2)如果 elementData 的大小不够就 调用 grow() 扩容
private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 记录集合被修改的次数

        // overflow-conscious code
        if (minCapacity - elementData.length > 0) // 10-1 > 0 true
            grow(minCapacity); // 扩容为10
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // true
            return Math.max(DEFAULT_CAPACITY, minCapacity); 
            //DEFAULT_CAPACITY=10, minCapacity=1, return 10
        }
        return minCapacity;
 }

// 实现扩容
// (1) 使用扩容机制来确定要扩容到多大
// (2) 第一次 newCapacity = 10
// (3) 第二次及其以后，按照1.5倍扩容
// (4) 扩容使用 Arrays.copyOf()
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; // 0
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
        if (newCapacity - minCapacity < 0) // 0 - 10 < 0, true
            newCapacity = minCapacity; // 10
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity); // 数组拷贝
}

// 使用有参构造器，指定初始容量
// 唯一同的是初始化的elementData 数组大小为参数指定大小
 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);
        }
    }

Vector的基本介绍

Vector 类的定义说明
Vector 底层也是一个对象数组，propected Object[] elementData
Vector 是线程同步的，即线程安全，Vector类的操作方法带有 synchronized
在开发中，需要线程同步安全时，考虑使用Vector

Vector 和 ArrayList 的比较

	底层结构	版本	线程安全、效率	扩容倍数
ArrayList	可变数组	jdk1.2	不安全，效率高	无参构造器，第一次10，第二次开始1.5倍，有参构造器指定大小，每次按照1.5倍扩容
Vector	可变数组	jdk1.0	安全，效率不高	无参构造器，默认是10，满后按照2倍扩容，如果使用参数构造器指定大小，则每次按2倍扩容

LinkedList 介绍

LinkedList是西安了双向链表和双端队列特点
可以添加任意元素（元素可重复），包括null
线程不安全，没有实现同步

LinkedList 的底层操作机制

LinkedList 底层维护了一个双向链表
Linked中维护了两个属性 first 和 last 分别指向首结点和尾结点
每个结点（Node 对象），里面又维护了 prev，next，item 三个属性，其中 prev 指向前一个结点，next 指向后一个结点。最终实现双向链表
所以 LinkedList的元素添加和删除，不是通过数组完成的，效率较高

LinkedList的属性

// LinkedList 的静态内部类 Node 
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;
        }
}