JavaSE-12笔记【集合1（+2024新）】

文章目录

1. 集合概述
2.Collection
- 2.1 Collection继承结构（基于Java21）
- 2.2 Collection接口的常用方法
- 2.3 Collection的遍历（集合的通用遍历方式）
- 2.4 所有的有序集合都实现了SequencedCollection接口
- 2.5 泛型
- - 2.5.1 如何判断是否可以使用泛型？
  - 2.5.2 泛型的擦除与补偿（了解）
  - 2.5.3 泛型的使用
  - - 2.5.3.1 在类上定义泛型
    - 2.5.3.2 在方法上定义泛型（上述示例已有）
    - 2.5.3.3 在接口上定义泛型
  - 2.5.4 泛型通配符（使用泛型）
- 2.6 迭代时删除元素
- - 2.6.1 fail-fast机制
- 2.7 List接口
- - 2.7.1 List接口特有方法
  - 2.7.2 List接口特有迭代
  - 2.7.3 使用Comparable和Comparator定义比较规则
  - - 2.7.3.1 数组的排序使用Comparable接口:
    - 2.7.3.2 List接口的排序使用Comparator接口
  - 2.7.4 ArrayList
  - 2.7.5 Vector
  - 2.7.6 链表
  - - 2.7.6.1 LinkedList
    - 2.7.6.2 手写单向链表：
- 2.8 栈数据结构
- 2.9 队列
- - 2.8.1 单向队列
  - 2.8.2 双端（向）队列

这一章非常重要，每一个点都必须吃透！！！

1. 集合概述

什么是集合，有什么用？
①集合是一种容器，用来组织和管理数据的。非常重要。
②Java的集合框架对应的这套类库其实就是对各种数据结构的实现。
③每一个集合类底层采用的数据结构不同，例如ArrayList集合底层采用了数组，LinkedList集合底层采用了双向链表，HashMap集合底层采用了哈希表，TreeMap集合底层采用了红黑树。
④我们不用写数据结构的实现了。直接用就行了。但我们需要知道的是在哪种场合下选择哪一个集合效率是最高的。
集合中存储的是引用，不是把堆中的对象存储到集合中，是把对象的地址存储到集合中。
默认情况下，如果不使用泛型的话，集合中可以存储任何类型的引用，只要是Object的子类都可以存储。
Java集合框架相关的类都在 java.util 包下。
Java集合框架分为两部分：
①Collection结构：元素以单个形式存储。
②Map结构：元素以键值对的映射关系存储。

一个代码示例：如果不使用泛型的话，集合中可以存储任何类型的引用，只要是Object的子类都可以存储。

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class CollectionTest01 {public static void main(String[] args) {//创建一个CollectionCollection c = new ArrayList();//添加任意类型的元素c.add("String");c.add(false);c.add(1);c.add(22.3);c.add(new Dog());//获取其迭代器，遍历Iterator iterator = c.iterator();while (iterator.hasNext()) {Object object = iterator.next();System.out.println(object);}}
}class Dog{}

运行结果：
在这里插入图片描述

2.Collection

2.1 Collection继承结构（基于Java21）

SequencedCollection和SequencedSet接口都是Java21新增的接口。
上图中蓝色的是实现类。其它的都是接口。
6个实现类中只有HashSet是无序集合。剩下的都是有序集合。
①有序集合：集合中存储的元素有下标或者集合中存储的元素是可排序的。
②无序集合：集合中存储的元素没有下标并且集合中存储的元素也没有排序。
每个集合实现类对应的数据结构如下：
①LinkedList：双向链表（不是队列数据结构，但使用它可以模拟队列）
②ArrayList：数组
③Vector：数组（线程安全的）
④HashSet：哈希表
⑤LinkedHashSet：双向链表和哈希表结合体
⑥TreeSet：红黑树
List集合中存储的元素可重复。Set集合中存储的元素不可重复。

Java21新版UML图：
旧版（没有SequencedCollection和SequencedSet）：

2.2 Collection接口的常用方法

①boolean add(E e); 向集合中添加元素 （对于普通数据类型，其会自动装箱）
②int size(); 获取集合中元素个数
③boolean addAll(Collection c); 将参数集合中所有元素全部加入当前集合
④boolean contains(Object o); 判断集合中是否包含对象o （底层会调用equals方法进行比对）
⑤boolean remove(Object o); 从集合中删除对象o （底层也会调用equals方法进行删除）
⑥void clear(); 清空集合
⑦boolean isEmpty(); 判断集合中元素个数是否为0
⑧Object[] toArray(); 将集合转换成一维数组

示例代码：

package collectiontest;import java.util.ArrayList;
import java.util.Collection;public class CollectionTest02 {public static void main(String[] args) {Collection c = new ArrayList();//添加元素c.add(100);  //自动装箱c.add(2.34); //自动装箱c.add(false); //自动装箱c.add("字符串");c.add(new Object());//查看集合中元素个数System.out.println("集合中元素个数：" + c.size());//再创建一个集合对象Collection c2 = new ArrayList();//添加元素c.add(101);  //自动装箱c.add(true); //自动装箱c.add(new Object());//一次添加多个，将一个集合中的所有元素添加打当前集合对象中c.addAll(c2);//查看集合中元素个数System.out.println("集合中元素个数：" + c.size());//判断集合中是否包含某个元素System.out.println(c.contains(101)); //trueSystem.out.println(c.contains(200)); //falseString str1 = new String("字符串");System.out.println(c.contains(str1)); //true//判断集合是否为空System.out.println("当前集合是否为空：" + c.isEmpty());//删除集合中指定元素System.out.println("-----------删除一个元素-----------");String str2 = new String("字符串");c.remove(str2);System.out.println("集合中元素个数：" + c.size());//将集合转换为数组Object[] objects = c.toArray();for (Object o:objects) {System.out.println(o);}//清空集合c.clear();//判断集合是否为空System.out.println("集合中元素个数：" + c.size());}
}

运行结果：
在这里插入图片描述

2.3 Collection的遍历（集合的通用遍历方式）

第一步：获取当前集合依赖的迭代器对象：
Iterator it = collection.iterator();
第二步：编写循环，循环条件是：当前光标指向的位置是否存在元素：
while(it.hasNext()){}
第三步：如果有，将光标指向的当前元素返回，并且将光标向下移动一位：
Object obj = it.next();
原理说明：
在这里插入图片描述
示例代码：

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** Collection下所有类都通用的遍历方式*/
public class CollectionTest03 {public static void main(String[] args) {Collection c = new ArrayList();c.add(100);c.add(false);c.add(2.34);c.add("string");System.out.println("使用while循环遍历：");Iterator iterator = c.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}System.out.println("============================");System.out.println("使用for循环遍历：");//或者使用for循环for (Iterator iterator1 = c.iterator(); iterator1.hasNext();) {System.out.println(iterator1.next());}}
}

运行结果：
在这里插入图片描述

2.4 所有的有序集合都实现了SequencedCollection接口

SequencedCollection接口是Java21版本新增的。
SequencedCollection接口中的方法：
①void addFirst(Object o)：向头部添加
②void addLast(Object o)：向末尾添加
③Object removeFirst()：删除头部
④Object removeLast()：删除末尾
⑤Object getFirst()：获取头部节点
⑥Object getLast()：获取末尾节点
⑦SequencedCollection reversed(); 反转集合中的元素
ArrayList，LinkedList，Vector，LinkedHashSet，TreeSet，Stack 都可以调用这个接口中的方法。

示例代码：

package collectiontest;import java.util.ArrayList;
import java.util.Iterator;
import java.util.SequencedCollection;/*** 有序集合的祖宗接口*/
public class SequencedCollectionTest {public static void main(String[] args) {SequencedCollection c = new ArrayList();c.add(1);c.add(2);c.add(3);c.add(4);//向头部添加一个元素c.addFirst(0);//向尾部添加一个元素c.addLast(5);//获取头部元素System.out.println("头部元素：" + c.getFirst());//获取尾部元素System.out.println("尾部元素：" + c.getLast());//遍历Iterator iterator = c.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}//从头部删除一个元素c.removeFirst();//从尾部删除一个元素c.removeLast();//再次遍历Iterator iterator1 = c.iterator();while (iterator1.hasNext()){System.out.println(iterator1.next());}//倒置SequencedCollection reversedc = c.reversed();//遍历Iterator iterator2 = c.iterator();while (iterator2.hasNext()){System.out.println(iterator2.next());}}
}

运行结果：无（因为用的是java8，所以运行不了）

2.5 泛型

泛型是Java5的新特性，属于编译阶段的功能。
泛型可以让开发者在编写代码时指定集合中存储的数据类型。
泛型作用：
①类型安全：指定了集合中元素的类型之后，编译器会在编译时进行类型检查，如果尝试将错误类型的元素添加到集合中，就会在编译时报错，避免了在运行时出现类型错误的问题。
②代码简洁：使用泛型可以简化代码，避免了繁琐的类型转换操作。比如，在没有泛型的时候，需要使用 Object 类型来保存集合中的元素，并在使用时强制类型转换成实际类型，而有了泛型之后，只需要在定义集合时指定类型即可。
在集合中使用泛型
Collection<String> strs = new ArrayList<String>();
这就表示该集合只能存储字符串，存储其它类型时编译器报错。
并且以上代码使用泛型后，避免了繁琐的类型转换，集合中的元素可以直接调用String类特有的方法。
Java7的新特性：钻石表达式（省略后面<>中的类型）
Collection<String> strs = new ArrayList<>();

示例代码（不使用泛型）：

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.UUID;/*** 当前程序不使用泛型缺点：* 代码写得比较多，每一次从集合中取出的元素要想访问子类中特有的方法，必须向下转型* 而实际大部分都是需要写向下转型的吗，因为Object类中的方法肯定是不够用的，一定会调用子类方法*/
public class GenericTest01 {public static void main(String[] args) {//创建集合Collection c = new ArrayList();//创建User对象User user1 = new User("Li");User user2 = new User("Wang");User user3 = new User("Zhao");//向集合中添加User对象c.add(user1);c.add(user2);c.add(user3);//遍历Iterator it = c.iterator();while (it.hasNext()){Object o = it.next();if(o instanceof User){User user = (User)o; //必须向下转型才能调用User中的pay方法user.pay();}}}
}

示例代码（使用泛型）：

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** 使用泛型*/
public class GenericTest02 {public static void main(String[] args) {//创建集合，要求其只能存放User类型的对象，不能存储其他类型Collection<User> c = new ArrayList<>();//创建User对象User user1 = new User("Li");User user2 = new User("Wang");User user3 = new User("Zhao");//向集合中添加User对象c.add(user1);c.add(user2);c.add(user3);//编译器报错，不能添加其他类型
//        c.add("ada");//遍历Iterator<User> it = c.iterator();while (it.hasNext()){User u = it.next(); //获取到的就是User类型的对象u.pay(); //不用转型，直接调用}}
}

运行结果：
在这里插入图片描述

2.5.1 如何判断是否可以使用泛型？

看帮助文档中对应类、方法上是否有“<>”符号，有这个符号的就都可以使用泛型。

2.5.2 泛型的擦除与补偿（了解）

泛型的出现提高了编译时的安全性，正因为编译时对添加的数据做了检查，则程序运行时才不会抛出类型转换异常。因此泛型本质上是编译时期的技术，是专门给编译器用的。加载类的时候，会将泛型擦除掉（擦除之后的类型为Object类型），这个称为泛型擦除。
为什么要有泛型擦除呢？其本质是为了让JDK1.4和JDK1.5能够兼容同一个类加载器。在JDK1.5版本中，程序编译时期会对集合添加的元素进行安全检查，如果检查完是安全的、没有错误的，那么就意味着添加的元素都属于同一种数据类型，则加载类时就可以把这个泛型擦除掉，将泛型擦除后的类型就是Object类，这样擦除之后的代码就与JDK1.4的代码一致。
由于加载类的时候，会默认将类中的泛型擦除为Object类型，所以添加的元素就被转化为Object类型，同时取出的元素也默认为Object类型。而我们获得集合中的元素时，按理说取出的元素应该是Object类型，为什么取出的元素却是实际添加的元素类型呢？
这里又做了一个默认的操作，我们称之为泛型的补偿。在程序运行时，通过获取元素的实际类型进行强转，这就叫做泛型补偿（不必手动实现强制转换）。获得集合中的元素时，虚拟机会根据获得元素的实际类型进行向下转型，也就是会恢复获得元素的实际类型，因此我们就无需手动执行向下转型操作，从本质上避免了抛出类型转换异常。

2.5.3 泛型的使用

2.5.3.1 在类上定义泛型

class 类名<泛型1,泛型2,泛型3...>{}

示例代码：

package collectiontest;/*** 在类上定义泛型* @param <NameType>* @param <AgeType>*/
public class MyClass<NameType, AgeType> { //在类声明的时候，给类声明/定义一个泛型private NameType name;private AgeType age;public MyClass() {}public MyClass(NameType name, AgeType age) {this.name = name;this.age = age;}public NameType getName() {return name;}public void setName(NameType name) {this.name = name;}public AgeType getAge() {return age;}public void setAge(AgeType age) {this.age = age;}public static void main(String[] args) {MyClass<String,Integer> myClass = new MyClass<>("lulu",24);
//        MyClass<String,Integer> myClass = new MyClass<>("lulu","24"); //类型检查不通过，编译报错System.out.println(myClass.getName());System.out.println(myClass.getAge());}
}

运行结果：
在这里插入图片描述

2.5.3.2 在方法上定义泛型（上述示例已有）

在类上定义的泛型，在静态方法中无法使用。
如果在静态方法中使用泛型，则需要再方法返回值类型前面进行泛型的声明。语法格式：static <泛型1, 泛型2, 泛型3, ...> 返回值类型方法名(形参列表) {}。
示例代码：

package collectiontest;public class Customer {public static <E> void print(E[] elts){ //在静态方法处使用泛型，需要在返回值前面先声明泛型for (E e: elts) {System.out.println(e);}}public static void main(String[] args) {String[] str = {"li","wang"};Customer.print(str);}
}

运行结果：在这里插入图片描述

2.5.3.3 在接口上定义泛型

语法格式：interface 接口名<泛型1,泛型2,...> {}
例如：public interface Flayable<T>{}

实现接口时，如果知道具体的类型，则：public class MyClass implements Flyable<Bird>{}
实现接口时，如果不知道具体的类型，则：public class MyClass<T> implements Flyable<T>{}

示例代码：

package collectiontest;public interface MyComparable<T> { //接口上定义泛型int compareTo(T o);
}

package collectiontest;public class Product implements MyComparable<Product>{ //继承自定义接口，并指定泛型对应的类private int price;public Product() {}public Product(int price) {this.price = price;}@Overridepublic int compareTo(Product o) {int flag = this.price - o.price;if (flag > 0){return 1;}else if(flag == 0){return 0;}return -1;}public static void main(String[] args) {Product product1 = new Product(101);Product product2 = new Product(10);System.out.println(product1.compareTo(product2)); }
}

2.5.4 泛型通配符（使用泛型）

泛型是在限定数据类型，当在集合或者其他地方使用到泛型后，那么这时一旦明确泛型的数据类型，那么在使用的时候只能给其传递和数据类型匹配的类型，否则就会报错。
有的情况下，我们在定义方法时，根本无法确定集合中存储元素的类型是什么。为了解决这个“无法确定集合中存储元素类型”问题，那么Java语言就提供了泛型的通配符。
通配符的几种形式：

无限定通配符，<?>，此处“？”可以为任意引用数据类型。
上限通配符，<? extends Number>，此处“？”必须为Number及其子类。
下限通配符，<? super Number>，此处“？”必须为Number及其父类。

示例代码：

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;/*** 使用泛型*/
public class GenericTest03 {public static void print(ArrayList<?> list){}public static void print1(ArrayList<? extends Number> list){}public static void print2(ArrayList<? super String> list){}public static void print3(ArrayList<? super B> list){}public static void main(String[] args) {print(new ArrayList<String>());print(new ArrayList<Integer>());print(new ArrayList<Object>());print(new ArrayList<A>());print1(new ArrayList<Float>());print1(new ArrayList<Double>());print1(new ArrayList<Integer>());//编译报错
//        print1(new ArrayList<A>());print2(new ArrayList<String>());print2(new ArrayList<Object>());//编译报错
//        print2(new ArrayList<Number>());print3(new ArrayList<A>());print3(new ArrayList<B>());//编译报错
//        print3(new ArrayList<C>());}
}class A{}class B extends A{}class C extends B{}

2.6 迭代时删除元素

迭代时，使用集合带的remove方法（集合对象.remove(元素)）删除元素

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class CollectionTest04 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("Mili");c.add("Dahuang");c.add("Yuanbao");c.add("Qiuqiu");System.out.println("当前集合元素个数：" + c.size());Iterator<String> iterator = c.iterator();//迭代集合时删除集合中的某个元素while (iterator.hasNext()){String name = iterator.next(); //java.util.ConcurrentModificationException并发修改异常if("Dahuang".equals(name)){//使用集合带的remove方法删除元素c.remove(name);}}System.out.println("当前集合元素个数：" + c.size());}
}

运行结果：
在这里插入图片描述

迭代时，使用迭代器带的remove方法（迭代器对象.remove()）删除元素

package collectiontest;import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;public class CollectionTest04 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("Mili");c.add("Dahuang");c.add("Yuanbao");c.add("Qiuqiu");System.out.println("当前集合元素个数：" + c.size());Iterator<String> iterator = c.iterator();//迭代集合时删除集合中的某个元素while (iterator.hasNext()){String name = iterator.next();if("Dahuang".equals(name)){//使用迭代器带的remove方法删除元素，可以正常删除iterator.remove();}}System.out.println("当前集合元素个数：" + c.size());}
}

运行结果：
在这里插入图片描述

2.6.1 fail-fast机制

如何解决并发修改问题：fail-fast机制
fail-fast机制又被称为：快速失败机制。也就是说只要程序发现了程序对集合进行了并发修改。就会立即让其失败，以防出现错误。
fail-fast机制是如何实现的？以下是源码中的实现原理：
1）集合中设置了一个modCount属性，用来记录修改次数，使用集合对象执行增，删，改中任意一个操作时，modCount就会自动加1。
2）获取迭代器对象的时候，会给迭代器对象初始化一个expectedModCount属性。并且将expectedModCount初始化为modCount，即：int expectedModCount = modCount;
3）当使用集合对象删除元素时：modCount会加1。但是迭代器中的expectedModCount不会加1。而当迭代器对象的next()方法执行时，会检测expectedModCount和modCount是否相等，如果不相等，则抛出：ConcurrentModificationException异常。
4）当使用迭代器删除元素的时候：modCount会加1，并且expectedModCount也会加1。这样当迭代器对象的next()方法执行时，检测到的expectedModCount和modCount相等，则不会出现ConcurrentModificationException异常。

注意：虽然我们当前写的程序是单线程的程序，并没有使用多线程，但是通过迭代器去遍历的同时使用集合去删除元素，这个行为将被认定为并发修改。

结论：迭代集合时，删除元素要使用迭代器对象.remove()方法来删除，避免使用集合对象.remove(元素)。主要是为了避免ConcurrentModificationException异常的发生。

注意：迭代器的remove()方法删除的是next()方法的返回的那个数据。remove()方法调用之前一定是先调用了next()方法，如果不是这样的，就会报错。

2.7 List接口

List集合存储元素特点：有序可重复。
1）有序：List集合中的元素都是有下标的，从0开始，以1递增。
2）可重复：存进去1，还可以再存一个1。
List接口下常见的实现类有：
ArrayList：数组
Vector、Stack：数组（线程安全的）
LinkedList：双向链表

2.7.1 List接口特有方法

在Collection和SequencedCollection中没有的方法，只适合List家族使用的方法，这些方法都和下标有关系：

void add(int index, E element) 在指定索引处插入元素
E set(int index, E element); 修改索引处的元素
E get(int index); 根据索引获取元素（通过这个方法List集合具有自己特殊的遍历方式：根据下标遍历）
E remove(int index); 删除索引处的元素
int indexOf(Object o); 获取对象o在当前集合中第一次出现时的索引。
int lastIndexOf(Object o); 获取对象o在当前集合中最后一次出现时的索引。
List subList(int fromIndex, int toIndex); 截取子List集合生成一个新集合（对原集合无影响）。[fromIndex, toIndex)
static List of(E… elements); 静态方法，返回包含任意数量元素的不可修改列表。（获取的集合是只读的，不可修改的。）

示例代码：

package collectiontest;import java.util.ArrayList;
import java.util.List;/*** List家族：有序（每个元素有下标，从0开始，以1递增），可重复（可存储相同元素）*/
public class ListTest01 {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(1);//获取list中指定元素第一次出现的位置System.out.println(list.indexOf(1));//获取list中指定元素最后一次出现的位置System.out.println(list.lastIndexOf(1));//修改指定下标的元素list.set(0, -1); //将下标0处的元素修改为-1//移除指定下标处的元素list.remove(5);//List家族特有的遍历方法for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("-------------------------------------");//获取指定下标范围的list，返回新的子listList<Integer> subList = list.subList(2, 4); //[2,4)for (int i = 0; i < subList.size(); i++) {System.out.println(subList.get(i));}//获取一个不可修改的集合，只读的集合（这里因为jdk版本不够，无法运行）
//        List<Integer> nums = List.of(1,2,4,56,7);}
}

运行结果：
在这里插入图片描述

2.7.2 List接口特有迭代

特有的迭代方式

ListIterator listIterator(); 获取List集合特有的迭代器（该迭代器功能更加强大，但只适合于List集合使用）
ListIterator listIterator(int index); 从列表中的指定位置开始，返回列表中元素的列表迭代器

ListIterator接口中的常用方法：

boolean hasNext(); 判断光标当前指向的位置是否存在元素。
E next(); 将当前光标指向的元素返回，然后将光标向下移动一位。
void remove(); 删除上一次next()方法返回的那个数据(删除的是集合中的)。remove()方法调用的前提是：你先调用next()或previous()方法。不然会报错。
void add(E e); 添加元素（将元素添加到光标指向的位置，然后光标向下移动一位。）
boolean hasPrevious(); 判断当前光标指向位置的上一个位置是否存在元素。
E previous(); 获取上一个元素（将光标向上移动一位，然后将光标指向的元素返回）
int nextIndex(); 获取光标指向的那个位置的下标
int previousIndex(); 获取光标指向的那个位置的上一个位置的下标
void set(E e); 修改的是上一次next()方法返回的那个数据（修改的是集合中的）set()方法调用的前提是：你先调用了next()或previous()方法。不然会报错。

示例代码：

package collectiontest;import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;public class ListTest02 {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("Mili");list.add("Dahuang");list.add("Yuanbao");list.add("Qiuqiu");//使用List特有的迭代器进行遍历System.out.println("使用List特有的迭代器进行遍历：");ListIterator<String> ListIterator1 = list.listIterator();while (ListIterator1.hasNext()){String name = ListIterator1.next();System.out.println(name);}System.out.println("------------------------");//测试List特有的add方法ListIterator<String> ListIterator2 = list.listIterator();while (ListIterator2.hasNext()){String name = ListIterator2.next();if("Dahuang".equals(name)){ListIterator2.add("小圆"); //不能使用从Collection继承过来的add方法，会出现ConcurrentModificationException异常}}for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("------------------------");//测试hasPrevious，判断是否有上一个//判断当前光标指向位置的上一个位置是否存在元素ListIterator<String> ListIterator3 = list.listIterator();System.out.println("当前光标指向位置的上一个位置是否存在元素：" + ListIterator3.hasPrevious());while (ListIterator3.hasNext()){String name = ListIterator3.next();System.out.println(name);}System.out.println("当前光标指向位置的上一个位置是否存在元素：" + ListIterator3.hasPrevious());System.out.println("------------------------");//测试previous，获取上一个元素（将光标向上移动一位，然后将光标指向的元素返回）ListIterator<String> ListIterator4 = list.listIterator();while (ListIterator4.hasNext()){String name = ListIterator4.next();System.out.println(name);}System.out.println("当前光标指向元素的上一个元素：" + ListIterator4.previous()); //调用一次，光标向上移动一次System.out.println("当前光标指向元素的上一个元素：" + ListIterator4.previous());System.out.println("当前光标指向元素的上一个元素：" + ListIterator4.previous());System.out.println("当前光标指向元素的上一个元素：" + ListIterator4.previous());System.out.println("当前光标指向元素的上一个元素：" + ListIterator4.previous());
//        System.out.println("当前光标指向元素的上一个元素：" + ListIterator4.previous()); //“越界”：java.util.NoSuchElementExceptionSystem.out.println("------------------------");//测试nextIndex(): 获取光标指向的那个位置的下标ListIterator<String> ListIterator5 = list.listIterator();while (ListIterator5.hasNext()){String name = ListIterator5.next(); //取出当前元素后，光标已下移if("Yuanbao".equals(name)){System.out.println(ListIterator5.nextIndex()); //4//previousIndex():获取光标指向的那个位置的上一个位置的下标System.out.println(ListIterator5.previousIndex()); //3}System.out.println(name);}System.out.println("------------------------");//测试set(E e): 修改的是前面next()方法返回的那个数据（修改的是集合中的），前提是前面有调用next()方法或者previous()方法，否则报错ListIterator<String> ListIterator6 = list.listIterator();while (ListIterator6.hasNext()){String name = ListIterator6.next();if("Yuanbao".equals(name)){ListIterator6.set("元宝");}}for (int i = 0; i < list.size(); i++) {System.out.println(list.get(i));}System.out.println("------------------------");}
}

运行结果：
在这里插入图片描述

2.7.3 使用Comparable和Comparator定义比较规则

2.7.3.1 数组的排序使用Comparable接口:

所有自定义类型排序时必须指定排序规则。（int不需要指定，String不需要指定，因为他们都有固定的排序规则。int按照数字大小。String按照字典中的顺序）
如何给自定义类型指定排序规则？让自定义类型实现java.lang.Comparable接口，然后重写compareTo方法，在该方法中指定比较规则。

package collectiontest;import java.util.Arrays;public class ListTest03 {public static void main(String[] args) {Person[] people = new Person[4];Person person1 = new Person(23,"nini");Person person2 = new Person(16,"jingjing");Person person3 = new Person(34,"yingying");Person person4 = new Person(14,"huanhuan");people[0] = person1;people[1] = person2;people[2] = person3;people[3] = person4;Arrays.sort(people);System.out.println(Arrays.toString(people));}
}/*** Person实现Comparable接口，Comparable接口可以使用泛型*/
class Person implements Comparable<Person>{int age;String name;public Person() {}public Person(int age, String name) {this.age = age;this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return "Person{" +"age=" + age +", name='" + name + '\'' +'}';}//重写compareTo方法@Overridepublic int compareTo(Person p) {return this.age - p.age ; //按年龄升序}
}

运行结果：
在这里插入图片描述

2.7.3.2 List接口的排序使用Comparator接口

default void sort(Comparator<? super E> c)：对List集合中元素排序可以调用此方法。sort方法需要一个参数: java.util.Comparator。我们把这个参数叫做比较器。这是一个接口。

如何给自定义类型指定比较规则？

可以对Comparator提供一个实现类，并重写compare方法来指定比较规则。
Comparator接口的实现类也可以采用匿名内部类的方式。
方法一：创建一个类实现Comparator接口:

package collectiontest;public class Person {int age;String name;public Person() {}public Person(int age, String name) {this.age = age;this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return "Person{" +"age=" + age +", name='" + name + '\'' +'}';}
}

package collectiontest;import java.util.Comparator;/*** PeopleComparator定义Person的比较规则，实现Comparator接口，可以使用泛型*/
public class PeopleComparator implements Comparator<Person> {@Overridepublic int compare(Person o1, Person o2) {return o1.age - o2.age; //按年龄升序排序}
}

package collectiontest;import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;public class ListTest03 {public static void main(String[] args) {List<Person> people = new ArrayList<>();Person person1 = new Person(23,"nini");Person person2 = new Person(16,"jingjing");Person person3 = new Person(34,"yingying");Person person4 = new Person(14,"huanhuan");people.add(person1);people.add(person2);people.add(person3);people.add(person4);people.sort(new PeopleComparator()); //创建PeopleComparator对象并传入sort方法for (int i = 0; i < people.size(); i++) {System.out.println(people.get(i));}}
}

方法二：使用匿名内部类：

package collectiontest;import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;public class ListTest03 {public static void main(String[] args) {List<Person> people = new ArrayList<>();Person person1 = new Person(23,"nini");Person person2 = new Person(16,"jingjing");Person person3 = new Person(34,"yingying");Person person4 = new Person(14,"huanhuan");people.add(person1);people.add(person2);people.add(person3);people.add(person4);people.sort(new Comparator<Person>() { //使用匿名内部类@Overridepublic int compare(Person o1, Person o2) {return o1.age - o2.age;}});for (int i = 0; i < people.size(); i++) {System.out.println(people.get(i));}}
}

运行结果：
在这里插入图片描述

2.7.4 ArrayList

ArrayList集合底层采用了数组这一数据结构。
ArrayList集合优点：底层是数组，因此根据下标查找元素的时间复杂度是O(1)。因此检索效率高。
ArrayList集合缺点：随机增删元素效率较低。不过只要数组的容量还没满，对末尾元素进行增删，效率不受影响。
ArrayList集合适用场景：
需要频繁的检索元素，并且很少的进行随机增删元素时建议使用。
ArrayList默认初始化容量：从源码角度可以看到，当调用无参数构造方法时，初始化容量0；当第一次调用add方法时将ArrayList容量初始化为10个长度。
ArrayList集合扩容策略：底层扩容会创建一个新的数组，然后使用数组拷贝。扩容之后的新容量是原容量的1.5倍。

（使用ArrayList集合时最好也是预测大概数量，给定初始化容量，减少扩容次数。）

2.7.5 Vector

Vector底层也是数组，和ArrayList相同。
不同的是Vector几乎所有的方法都是线程同步的（被synchronized修饰：线程排队执行，不能并发），因此Vector是线程安全的，但由于效率较低，很少使用。因为控制线程安全有新方式。
Vector初始化容量：10
Vector扩容策略：扩容之后的容量是原容量的2倍。

2.7.6 链表

单向链表：
双向链表
环形链表

环形单链表
环形双链表

链表优点：因为链表节点在空间存储上，内存地址不是连续的。因此删除某个节点时不需要涉及到元素位移的问题。因此链表随机增删元素效率较高。时间复杂度O(1)。
链表缺点：链表中元素在查找时，只能从某个节点开始顺序查找，因为链表节点的内存地址在空间上不是连续的。链表查找元素效率较低，时间复杂度O(n)。
链表的适用场景：需要频繁进行随机增删，但很少的查找的操作时。

2.7.6.1 LinkedList

LinkedList是一个双向链表，创建时调用无参构造方法是创建一个空链表。
简单示例代码：

package collectiontest;import java.util.LinkedList;public class LinkedListTest01 {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<>();//新增linkedList.add("1");linkedList.add("3");linkedList.add("5");linkedList.add("4");//修改String oldValue = linkedList.set(2, "110");System.out.println(oldValue);//删除String removeValue = linkedList.remove(1);System.out.println(removeValue);//根据下标查询元素System.out.println(linkedList.get(1));}
}

运行结果：
在这里插入图片描述

2.7.6.2 手写单向链表：

package collectiontest;public class SingleLinkedList<E> {//链表长度private int size = 0;//单向链表的头结点private Node<E> first;public SingleLinkedList() {}//结点类：内部类/*** 单向链表的结点（建议定义成静态内部类）*/private static class Node<E>{/*** 数据*/E item;/*** 下一个结点的内存地址*/Node<E> next;/*** 构造一个结点对象* @param item 结点中的数据* @param next 下一个结点的内存地址*/public Node(E item, Node<E> next){this.item = item;this.next = next;}}/*** 增加元素到末尾* @param data 数据*/public void add(E data){Node<E> newNode = new Node<>(data,null);//如果当前为空链表if(first == null){first = newNode;size++;return;}Node<E> last = findLast();last.next = newNode;size++;}/*** 找到末尾结点* @return 末尾结点*/private Node<E> findLast() {//first为空，即为空链表if(first == null){return null;}//假设第一个结点就是最后一个结点Node<E> last = first;while (last.next != null){last = last.next;}return last;}/*** 在指定位置增加元素* @param index 下标* @param data 数据*/public void add(int index, E data){//按理应该先进行下标检查//创建新的结点对象Node<E> newNode = new Node<>(data,null);//找到需要插入位置的前一个结点Node<E> prev = node(index -1);newNode.next = prev.next;prev.next = newNode;size++;}/*** 返回索引处的结点对象* @param index 索引* @return 结点对象*/private Node<E> node(int index) {//假设头结点是下一个结点Node<E> next = first;for (int i = 0; i < index; i++) {next = next.next;}return next;}/*** 删除指定位置结点* @param index 下标*/public void remove(int index){//按理应该先进行下标检查//假设删除头结点if(index == 0){Node<E> oldFirst = first;first = first.next;oldFirst.next = null;oldFirst.item = null;size--;return;}//删除的不是头结点//获取被删除节点的上一个结点Node<E> prev = node(index-1);//获取被删除节点Node<E> removedNode = node(index);prev.next = removedNode.next;removedNode.next = null;removedNode.item = null;size--;}/*** 修改指定位置结点* @param index 下标* @param data 数据*/public void set(int index, E data){//按理应该先进行下标检查Node<E> node = node(index);node.item = data;}///*** 查询指定位置结点* @param index 下标* @return 数据*/public E get(int index){//按理应该先进行下标检查Node<E> node = node(index);return node.item;}//获取链表长度public int size(){return this.size;}
}

测试代码：

package collectiontest;/*** 手写单向链表*/
public class SingleLinkedListTest01 {public static void main(String[] args) {SingleLinkedList linkedList = new SingleLinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);linkedList.add(4);linkedList.add(2,5);linkedList.remove(1);for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i));}}
}

运行结果：

在这里插入图片描述

2.8 栈数据结构

LIFO原则（Last In，First Out）：后进先出。
实现栈数据结构，可以用数组来实现，也可以用双向链表来实现。

用数组实现的代表是：Stack、ArrayDeque

Stack：Vetor的子类，实现了栈数据结构，除了具有Vetor的方法，还扩展了其它方法，完成了栈结构的模拟。不过在JDK1.6（Java6）之后就不建议使用了，因为它是线程安全的，太慢了。Stack中的方法如下：
①E push(E item)：压栈
②E pop()：弹栈（将栈顶元素删除，并返回被删除的引用）
③int search(Object o)：查找栈中元素（返回值的意思是：以1为开始，从栈顶往下数第几个）
④E peek()：窥视栈顶元素（不会将栈顶元素删除，只是看看栈顶元素是什么。注意：如果栈为空时会报异常。）
ArrayDeque：实现了Deque接口
①E push(E item)
②E pop()

用链表实现的代表是：LinkedList
①E push(E item)
②E pop()

示例代码：

package collectiontest;import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Stack;/*** java.util.Stack：底层是数组，线程安全的，jdk1.6不建议用了* java.util.LinkedList：底层是双向链表（实现LIFO的同时，又实现了双向队列）* java.util.ArrayDeque：底层是数组（实现LIFO的同时，又实现了双向队列）* 以上三个类都实现了栈数据结构，都实现了LIFO*/
public class StackTest {public static void main(String[] args) {//创建栈Stack<String> stack1 = new Stack<>();LinkedList<String> stack2 = new LinkedList<>();ArrayDeque<String> stack3 = new ArrayDeque<>();//压栈stack1.push("1");stack1.push("2");stack1.push("3");stack1.push("4");//查看栈顶元素System.out.println("栈顶元素为：" + stack1.peek());//搜索栈中元素（返回位置，从栈顶开始计数，没有对应元素返回-1）System.out.println("1的位置：" + stack1.search("1"));//弹栈System.out.println(stack1.pop());System.out.println(stack1.pop());System.out.println(stack1.pop());System.out.println(stack1.pop());System.out.println("================================");// 压栈stack2.push("1");stack2.push("2");stack2.push("3");stack2.push("4");//弹栈System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println(stack2.pop());System.out.println("================================");// 压栈stack3.push("1");stack3.push("2");stack3.push("3");stack3.push("4");//弹栈System.out.println(stack3.pop());System.out.println(stack3.pop());System.out.println(stack3.pop());System.out.println(stack3.pop());}
}

运行结果：
在这里插入图片描述

2.9 队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。进行插入操作（入口）的端称为队尾，进行删除操作（出口）的端称为队头。
队列的插入操作只能在队尾操作，队列的删除操作只能在队头操作，因此队列是一种先进先出（First In First Out）的线性表，简称FIFO表。
Queue接口是一种基于FIFO（先进先出）的数据结构，而Deque接口则同时支持FIFO和LIFO（后进先出）两种操作。因此Deque接口也被称为“双端（向）队列”。
Java集合框架中队列的实现：
①链表实现方式：LinkedList
②数组实现方式：ArrayDeque
LinkedList和ArrayDeque都实现了Queue、Deque接口，因此这两个类都具备队列和双端队列的特性。

LinkedList底层是基于双向链表实现的，因此它天然就是一个双端队列，既支持从队尾入队，从队头出队，也支持从队头入队，从队尾出队。用Deque的实现方式来说，就是它既实现了队列的offer()和poll()方法，也实现了双端队列的offerFirst()、offerLast()、pollFirst()和pollLast()方法等。
ArrayDeque底层是使用环形数组实现的，也是一个双端队列。它比LinkedList更加高效，因为在数组中随机访问元素的时间复杂度是O(1)，而链表中需要从头或尾部遍历链表寻找元素，时间复杂度是O(N)。环形数组并不是说数组是环形的结构，而是在逻辑上环形，或者说循环，循环数组下标：index = (start + i) % capacity

示例代码：

package collectiontest;import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;/*** java.util.ArrayQueue* java.util.LinkedList* 以上两个类都实现队列的FIFO结构*/
public class QueueTest {public static void main(String[] args) {//创建队列对象Queue<String> queue1 = new ArrayDeque<>();//入队queue1.offer("1");queue1.offer("2");queue1.offer("3");queue1.offer("4");//出队System.out.println(queue1.poll());System.out.println(queue1.poll());System.out.println(queue1.poll());System.out.println(queue1.poll());System.out.println("=====================");//创建队列对象Queue<String> queue2 = new LinkedList<>();//入队queue2.offer("a");queue2.offer("b");queue2.offer("c");queue2.offer("d");//出队System.out.println(queue2.poll());System.out.println(queue2.poll());System.out.println(queue2.poll());System.out.println(queue2.poll());}
}

运行结果：
在这里插入图片描述

2.8.1 单向队列

Queue接口基于Collection扩展的方法包括：
①boolean offer(E e); 入队。
②E poll(); 出队，如果队列为空，返回null。
③E remove(); 出队，如果队列为空，抛异常。
④E peek(); 查看队头元素，如果为空则返回null。
⑤E element(); 查看对头元素，如果为空则抛异常。

2.8.2 双端（向）队列

Deque接口基于Queen接口扩展的方法包括：
以下2个方法可模拟队列：
①boolean offerLast(E e); 从队尾入队
②E pollFirst(); 从队头出队
以下4个方法可模拟双端队列：
①boolean offerLast(E e); 从队尾入队
②E pollFirst(); 从队头出队
③boolean offerFirst(E e); 从队头入队
④E pollLast(); 从队尾出队
另外，offerLast+pollLast或者pollFirst+offerFirst可以模拟栈数据结构。或者也可以直接调用push/pop方法。

示例代码：

package collectiontest;import java.util.ArrayDeque;
import java.util.Deque;public class DequeTest {public static void main(String[] args) {//创建双端队列对象Deque<String> deque1 = new ArrayDeque<>();//队尾进，队头出System.out.println("队尾进，队头出：");deque1.offerLast("1");deque1.offerLast("2");deque1.offerLast("3");deque1.offerLast("4");System.out.println(deque1.pollFirst());System.out.println(deque1.pollFirst());System.out.println(deque1.pollFirst());System.out.println(deque1.pollFirst());System.out.println("队头进，队尾出：");//队头进，队尾出deque1.offerFirst("a");deque1.offerFirst("b");deque1.offerFirst("c");deque1.offerFirst("d");System.out.println(deque1.pollLast());System.out.println(deque1.pollLast());System.out.println(deque1.pollLast());System.out.println(deque1.pollLast());}
}