集合-1 | Running Noob

Collection、List

★★★第十四章集合

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

★★★集合的框架体系图

集合主要是两组：
- **单列集合 Collection**，有两个重要的子接口 List、Set，他们的实现子类都是单列集合，存放的是单个对象。
- **双列集合 Map**，实现子类是双列集合，存放的是键值对 K-V。

Collection接口和常用方法

public interface Collection<E> extends Iterable<E>
1. Collection 实现子类可以存放多个元素，每个元素可以是 Object；
2. 有些 Collection 的实现类可以存放重复的元素，有些不可以；
3. 有些 Collection 的实现类，有些是有序的 List ，有些不是有序的 Set ；
4. Collection 接口没有直接的实现子类，是通过它的子接口 Set 和 List 来实现的。

Collection 接口的常用方法（以实现子类 ArrayList 来演示）：

add：添加单个元素
remove：删除单个元素
- 可以选择删除指定索引位置的元素（返回被删除的该元素），也可以选择删除指定元素（返回boolean值）
  - 注意：由于在 List 中，每个元素都可以是 Object，所以 List 中可能会存在整数对象，例如下面代码中的 “10”
    如果想要在 List 中删除元素 “10”，不应该用 list.remove(10); ，因为这代表要删除索引为 10 的元素，而应该使用 list.remove(Integer.valueOf(10)); 来实现。
contains：查找元素是否存在
size：获取元素的个数
isEmpty：判断是否为空
clear：清空
addAll：添加多个元素
containsAll：查找多个元素是否都存在
removeAll：删除多个元素

package com.f.chapter14.collection;

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

/**
 * @author fzy
 * @date 2023/4/29 14:28
 */
public class CollectionMethod {
    public static void main(String[] args) {
        List list = new ArrayList();
        //1. add：添加单个元素
        list.add("hello");
        list.add(10);   //自动装箱：list.add(Integer.valueOf(10))
        list.add(true);
        System.out.println(list);   //[hello, 10, true]

        //2. remove：删除指定元素
        Object obj = list.remove(0);                            //删除索引为0的元素，并返回该元素
        System.out.println(obj.getClass());                             //class java.lang.String
        System.out.println(obj);                                        //hello
        boolean result1 = list.remove(Integer.valueOf(10));     //删除指定元素，返回boolean值
        System.out.println("删除结果为：" + result1);                     //删除结果为：true
        System.out.println(list);   //[true]

        //3. contains：查找元素是否存在
        boolean result2 = list.contains(10);    //判断 list 中是否含有元素 10
        System.out.println(result2);            //由于此时 list 为 [true]，所以结果为false

        //4. size：获取元素的个数
        System.out.println(list.size());        //1

        //5. isEmpty：判断是否为空
        System.out.println(list.isEmpty());     //false

        //6. clear：清空
        list.clear();
        System.out.println(list);   //[]

        //7. addAll：添加多个元素
        ArrayList novels = new ArrayList();
        novels.add("西游记");
        novels.add("三国演义");
        list.addAll(novels);
        System.out.println("list：" + list + " novels：" + novels);   //list：[西游记, 三国演义] novels：[西游记, 三国演义]

        //8. containsAll：查找多个元素是否都存在
        System.out.println(list.containsAll(novels));   //true

        //9. removeAll：删除多个元素
        list.add("红楼梦");
        list.removeAll(novels);
        System.out.println(list);   //[红楼梦]

    }
}

★Collection接口遍历对象的方式

★迭代器遍历iterator

Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。
所有实现了 Collection 接口的集合类都有一个 iterator() 方法，用以返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器。
Iterator 的结构图：
注意：在调用 iterator.next() 方法之前必须要调用 iterator.hasNext() 进行检测。若不调用，且下一条记录无效时，直接调用 it.next() 会抛出 NoSuchElementException 异常。
Iterator 仅用于遍历集合，本身并不存放对象。

package com.f.chapter14.collection;

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

/**
 * @author fzy
 * @date 2023/4/29 16:32
 */
public class Iterator_ {
    public static void main(String[] args) {
        List books = new ArrayList();
        books.add(new Book("三国演义", 9.9));
        books.add(new Book("西游记", 19.9));
        books.add(new Book("水浒传", 29.9));
        Iterator iterator = books.iterator();   //得到集合对应的迭代器iterator
        while (iterator.hasNext()) {    //判断是否还有元素
            Object obj = iterator.next();   //返回下一个元素，类型为 Object
            System.out.println(obj);
        }
    }
}

class Book {
    private String name;
    private double price;

    public Book(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

注意：当退出 while 循环后，这时的 iterator 迭代器指针指向了最后的元素，此时如果再使用 iterator.next() 就会抛出 NoSuchElementException 异常。如果希望再次遍历集合，则需要重置迭代器：iterator = books.iterator();，即重置了迭代器的指针位置。

在 IDEA 中，使用 itit 快捷键可以快速导出迭代器模板。

while (iterator.hasNext()) {
	Object next =  iterator.next();

}

★增强for

增强 for 循环，可以代替 iterator 迭代器。
特点 : 增强 for 就是简化版的 iterator ，本质一样。但只能用于遍历集合或数组。
- 增强 for 底层仍然是迭代器。

基本语法：

1
2
3

for(元素类型 元素名 : 集合名或数组名){
    //访问元素
}

//将“迭代器遍历”小节中的 while 部分代码改为下面这个即可
for (Object obj : books) {
	System.out.println(obj);
}

在 IDEA 中，使用 I 快捷键可以快速导出增强for模板。
1
2
3
for (Object o :) {

}

★List接口和常用方法

List 接口是 Collection 接口的子接口。public interface List<E> extends Collection<E>
1. List 集合类中的元素是有序的（即添加顺序和取出顺序一致），且可以重复；
2. List 容器中的元素都对应一个整数型的序号（索引），记载其在容器中的位置，可以根据序号存取容器中的元素；
  注意：索引从 0 开始。
3. JDK API 中 List 接口的常用实现类有 ArrayList、LinkedList、Vector。

List 接口的常用方法：

add(int index, Object element)：在index位置插入element元素。 -> 增
addAll(int index, Collection elements)：从index位置开始，插入elements所有元素。
get(int index)：获取指定索引位置的元素。 -> 查
indexOf(Object obj)：返回obj在集合中首次出现的位置，如果没有则返回-1。
lastIndexOf(Object obj)：返回obj在当前集合中末次出现的位置，如果没有则返回-1。
remove(int index)：移除指定index位置的元素，并返回此元素。 -> 删
set(int index, Object element)：设置指定index位置的元素为element，相当于是替换。 -> 改
subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集和，注意是左闭右开 [fromIndex, toIndex)。

package com.f.chapter14.list;

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

/**
 * @author fzy
 * @date 2023/4/30 14:13
 */
public class ListMethod {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("hello");
        list.add(10);
        list.add(true);
        System.out.println(list);   //[hello, 10, true]

        //1. add：在index位置插入ele元素
        list.add(1, "world!");  //在索引为1的地方插入字符串"world!"
        System.out.println(list);   //[hello, world!, 10, true]

        //2. addAll：从index位置开始，插入eles所有元素
        Collection collection = new ArrayList();
        collection.add(80);
        collection.add("java");
        list.addAll(1, collection); //从索引为1的地方开始，插入collection的所有元素
        System.out.println(list);   //[hello, 80, java, world!, 10, true]

        //3. get：获取指定索引位置的元素
        System.out.println(list.get(0));    //hello

        //4. indexOf：返回obj在集合中首次出现的位置，如果没有则返回-1
        list.add("hello");
        System.out.println(list);   //[hello, 80, java, world!, 10, true, hello]
        System.out.println(list.indexOf("hello"));  //0

        //5. lastIndexOf：返回obj在当前集合中末次出现的位置，如果没有则返回-1
        System.out.println(list.lastIndexOf("hello"));  //6

        //6. remove：移除指定index位置的元素，并返回此元素
        System.out.println(list.remove(1)); //80（类型为Integer）

        //7. set：设置指定index位置的元素为ele，相当于是替换
        System.out.println(list);   //[hello, java, world!, 10, true, hello]
        list.set(3,"三体");
        System.out.println(list);   //[hello, java, world!, 三体, true, hello]

        //8. subList：返回从fromIndex到toIndex位置的子集和，[fromIndex, toIndex)
        List subList = list.subList(1, 4);
        System.out.println(subList);    //[java, world!, 三体]
    }
}

ArrayList

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

ArrayList注意事项

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

★★★ArrayList底层结构和源码分析

ArrayList 中维护了一个 Object 类型的数组 elementData ：transient Object[] elementData; 。

当创建 ArrayList 对象时，如果使用的是无参构造器，则初始 elementData 的容量为 0，

1
2
3

public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

1	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

第一次添加元素时，会扩容 elementData 的容量到 10，

public boolean add(E e) {
    //判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!
    elementData[size++] = e;
    return true;
}

1
2
3

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

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

如果需要再次扩容，则扩容 elementData 的容量到原来的 1.5 倍。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)	//存储元素所需的容量已经超过ArrayList对象的容量
        grow(minCapacity);	//就使用grow函数扩容
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);	//新容量扩容为旧容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

( 0 -> 10 -> 15 -> 22 -> 33 -> ······ )

如果使用的是指定大小的构造器（有参构造器），则初始 elementData 容量为指定大小，如果需要扩容，则直接扩容 elementData 的容量到原来的 1.5 倍。

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);
    }
}

1	private static final Object[] EMPTY_ELEMENTDATA = {};

有参构造器创建的 ArrayList 对象扩容使用的代码和无参构造器中使用的一样。

Vector

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

Vector注意事项

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

Vector源码解读

当创建 Vector 对象时，如果使用的是无参构造器，则会调用 this(10); 方法，创建一个初始容量为 10 的 Vector 对象。

1
2
3

public Vector() {
    this(10);
}

1
2
3

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

扩容机制和 ArrayList 大同小异：

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

//确定是否需要扩容
private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)	//存储元素所需的容量已经超过Vector对象的容量
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);	//新容量扩容为旧容量的2倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Vector和ArrayList的比较

	底层结构	版本	线程安全(同步)、效率	扩容倍数
ArrayList	可变数组	JDK 1.2	线程不安全、效率高	如果有参，1.5 倍扩；如果无参，第一次 10，满后就按 1.5 倍扩容
Vector	可变数组	JDK 1.0	线程安全、效率不高	如果有参，2 倍扩；如果无参，第一次10，满后就按 2 倍扩容

LinkedList

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

LinkedList底层结构

LinkedList 底层维护了一个双向链表。
LinkedList 中维护了两个属性 first 和 last ，分别指向首节点和尾节点。
每个节点 (Node对象) 里面又维护了 prev、next、item 三个属性，其中通过 prev 指向前一个节点，通过 next 指向后一个节点。最终实现双向链表。
![](../../../../../Running Noob/计算机/Typora笔记/笔记-git仓库/Java-notebook/img/Java/C14-4.jpg)
LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

★★★LinkedList源码解读

首先创建 LinkedList 对象，调用的是下面的代码，所以只是创建了一个空的 LinkedList 对象，其 size 为 0，first 和 last 都为 null。
1
2
public LinkedList() {
}

当向 LinkedList 中添加元素 add 时，调用方法如下：

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

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

就将新的节点，加入到双向链表的最后。

当从 LinkedList 中删除元素 remove 时，调用方法如下：

1
2
3

public E remove() {
    return removeFirst();
}

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;	//第一个节点的后一个节点
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

所以 remove 默认删除的是第一个节点，即实现了队列的 “FIFO” 特点。

当在 LinkedList 对象中修改元素 set 时，调用方法如下：

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

注意： LinkedList 对象中节点元素的下标是从 0 开始的。

当在 LinkedList 对象中查找元素 get 时，调用方法如下：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

注意：因为 LinkedList 是实现了 List 接口，所以它的遍历方式也可以用迭代器iterator 或增强for。

List集合的选择

ArrayList 和 LinkedList 的比较：
底层结构增删的效率改查的效率
ArrayList 可变数组较低、数组扩容较高
LinkedList 双向链表较高、通过链表节点实现较低
如何选择 ArrayList 和 LinkedList ：
1. 如果我们**改查的操作多，选择 ArrayList**。
2. 如果我们**增删的操作多，选择LinkedList**。
3. 一般来说，在程序中，80% - 90% 都是查询，因此大部分情况下会选择 ArrayList。
4. 在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是 ArrayList，另外一个模块是LinkedList。
注意：ArrayList 和 LinkedList 都是线程不安全的。

	底层结构	增删的效率	改查的效率
ArrayList	可变数组	较低、数组扩容	较高
LinkedList	双向链表	较高、通过链表节点实现	较低

★★★第十四章 集合