集合、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();
-
-
集合
- 可以动态保存任意多个对象，使用比较方便
- 提供了一系列方便操作对象的方法：add、remove、set、get等
- 使用集合添加、删除新元素的代码简洁明了
集合框架体系
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;
}
}
ArrayList 和 LinkedList的比较
| 底层结构 | 增删的效率 | 改查的效率 | |
|---|---|---|---|
| ArrayList | 可变数组 | 较低，数组扩容 | 较高 |
| LinkedList | 双向链表 | 较高，通过链表追加 | 较低 |
如何选择 ArrayList 和 LinkedList:
- 如果改查的操作多，选择ArrayList
- 如果增删的操作多，选择LinkedList
- 一般来说，程序中80%以上都是查询，因此大部分情况下都会先择ArrayList
- 在一个项目中，根据业务灵活选择，可能一个模块使用ArrayList，另一个模块是LinkedList