[集合]-java
·
一.什么是集合
1.0特殊的容器--数组
数组也是一种集合，可以装基本数据类型，也可以用来装对象。在实际开发中，如果是一组对象，优先使用集合而不是数组当容器，而不是集合，因为集合的长度是可以伸缩的。
1.1什么是容器
集合是很多容器的总称，专门用来装Java对象的。如果基本数据类型的值，放到集合中，会自动装箱位对应的包装类对象。
1.2容器的存储结构
数组的元素是相邻的，连续的，内存中开辟一整块完整的存储空间。而集合的类型很丰富，底层可能是数组，可能是链表，也可能是树结构等。有的集合是有序的，有的是无序的，有点是允许元素重复的，有的是不允许元素重复的。
1.3分类
1.3.1Collection
用途：用于存储一组对象
1.3.2Map
用途：用于存储一组（key,value）键值对/映射关系
1.4关注点
（1）增删查改，遍历等操作
（2）不同集合的特点
（3）底层的实现原理
二.Set
2.1知识点
/**
* 1. HashSet：追求极致性能的去重选择
*
* - 底层结构：哈希表 (Hash Table)
* - 存储规律：无序（不保证插入顺序，也不保证自然顺序）。
* - 核心特点：
* 1. 查询、插入、删除效率极高，平均时间复杂度 O(1)。
* 2. 允许存储一个 null 元素。
* 3. 内存占用相对较小。
* - 迭代顺序：不可预测，随扩容可能改变。
*
* 适用场景：仅需去重，对顺序无任何要求时的默认首选。
*/
/**
* 2. LinkedHashSet：兼顾性能与插入顺序
*
* - 底层结构：哈希表 + 双向链表 (Hash Table + Doubly LinkedList)
* - 存储规律：严格按插入顺序存储。
* - 核心特点：
* 1. 查询效率接近 HashSet (O(1))，但略慢。
* 2. 额外维护链表指针，内存开销略高于 HashSet。
* 3. 允许存储一个 null 元素。
*
* 适用场景：需要去重，且必须按插入顺序遍历时。
*/
/**
* 3. TreeSet：需要排序与范围查询的选择
*
* - 底层结构：红黑树 (Red-Black Tree，一种自平衡二叉搜索树)
* - 存储规律：按元素的自然顺序（升序）或自定义比较器排序。
* - 核心特点：
* 1. 支持排序、获取最值（first/last）、范围查询（subSet）等操作。
* 2. 查询、插入、删除效率为 O(log n)。
* 3. 默认不允许 null 元素（会抛出 NullPointerException）。
* *注：若使用自定义 Comparator 且显式处理 null，则可存入 null。
*
* 适用场景：需要自动排序、查找最值或范围数据时。
*/
/**
* 3.1 HashSet 与 LinkedHashSet 的去重原理
*
* 依赖于元素对象的两个方法：hashCode() 和 equals()。
*
* 1. 哈希定位：首先调用元素的 hashCode() 方法。
* - 如果哈希值不同，直接判定元素不重复，放入集合。
* - 如果哈希值相同，进入下一步（可能存在哈希冲突）。
* 2. 内容比对：调用 equals() 方法比较内容。
* - 如果 equals() 返回 true，判定为重复元素，添加失败。
* - 如果 equals() 返回 false，判定为不同元素，放入集合。
*
* 注意：重写 equals() 时，必须重写 hashCode()，以保证逻辑一致。
*/
/**
* 3.2 TreeSet 的去重原理
*
* 依赖于元素的比较结果。
*
* 1. 判定标准：当比较结果返回 0 时，判定元素重复。
* 2. 优先策略：元素类实现 Comparable 接口，重写 compareTo() 方法。
* 3. 灵活策略：创建 TreeSet 时传入 Comparator 接口实现，自定义 compare() 方法。
*
* 注意：如果两个对象通过比较器判断为相等（返回0），TreeSet 视为同一元素。
*/
/**
* 自定义对象用于测试去重
*/
/**
* 总结：如何选择？
*
* 1. 需要排序 / 范围查询？ -> 选 TreeSet
* 2. 需要保持插入顺序？ -> 选 LinkedHashSet
* 3. 什么都不需要，只要最快的去重？ -> 选 HashSet (默认首选)
*
* 线程安全提示：以上三种 Set 实现均非线程安全。
* 多线程环境下需使用 Collections.synchronizedSet() 或并发包下的类。
*/
2.2 coding
package Collection.Set;
import Collection.Student;
import Collection.Teacher;
import org.junit.jupiter.api.Test;
import java.util.Comparator;
import java.util.HashSet;
public class HashSet_ {
/**
* 1. HashSet：追求极致性能的去重选择
*
* - 底层结构：哈希表 (Hash Table)
* - 存储规律：无序（不保证插入顺序，也不保证自然顺序）。
* - 核心特点：
* 1. 查询、插入、删除效率极高，平均时间复杂度 O(1)。
* 2. 允许存储一个 null 元素。
* 3. 内存占用相对较小。
* - 迭代顺序：不可预测，随扩容可能改变。
*
* 适用场景：仅需去重，对顺序无任何要求时的默认首选。
*/
/**
* 2. LinkedHashSet：兼顾性能与插入顺序
*
* - 底层结构：哈希表 + 双向链表 (Hash Table + Doubly LinkedList)
* - 存储规律：严格按插入顺序存储。
* - 核心特点：
* 1. 查询效率接近 HashSet (O(1))，但略慢。
* 2. 额外维护链表指针，内存开销略高于 HashSet。
* 3. 允许存储一个 null 元素。
*
* 适用场景：需要去重，且必须按插入顺序遍历时。
*/
/**
* 3. TreeSet：需要排序与范围查询的选择
*
* - 底层结构：红黑树 (Red-Black Tree，一种自平衡二叉搜索树)
* - 存储规律：按元素的自然顺序（升序）或自定义比较器排序。
* - 核心特点：
* 1. 支持排序、获取最值（first/last）、范围查询（subSet）等操作。
* 2. 查询、插入、删除效率为 O(log n)。
* 3. 默认不允许 null 元素（会抛出 NullPointerException）。
* *注：若使用自定义 Comparator 且显式处理 null，则可存入 null。
*
* 适用场景：需要自动排序、查找最值或范围数据时。
*/
/**
* 3.1 HashSet 与 LinkedHashSet 的去重原理
*
* 依赖于元素对象的两个方法：hashCode() 和 equals()。
*
* 1. 哈希定位：首先调用元素的 hashCode() 方法。
* - 如果哈希值不同，直接判定元素不重复，放入集合。
* - 如果哈希值相同，进入下一步（可能存在哈希冲突）。
* 2. 内容比对：调用 equals() 方法比较内容。
* - 如果 equals() 返回 true，判定为重复元素，添加失败。
* - 如果 equals() 返回 false，判定为不同元素，放入集合。
*
* 注意：重写 equals() 时，必须重写 hashCode()，以保证逻辑一致。
*/
/**
* 3.2 TreeSet 的去重原理
*
* 依赖于元素的比较结果。
*
* 1. 判定标准：当比较结果返回 0 时，判定元素重复。
* 2. 优先策略：元素类实现 Comparable 接口，重写 compareTo() 方法。
* 3. 灵活策略：创建 TreeSet 时传入 Comparator 接口实现，自定义 compare() 方法。
*
* 注意：如果两个对象通过比较器判断为相等（返回0），TreeSet 视为同一元素。
*/
/**
* 自定义对象用于测试去重
*/
/**
* 总结：如何选择？
*
* 1. 需要排序 / 范围查询？ -> 选 TreeSet
* 2. 需要保持插入顺序？ -> 选 LinkedHashSet
* 3. 什么都不需要，只要最快的去重？ -> 选 HashSet (默认首选)
*
* 线程安全提示：以上三种 Set 实现均非线程安全。
* 多线程环境下需使用 Collections.synchronizedSet() 或并发包下的类。
*/
@Test
public void testHashSetAdd() {
HashSet hashSet = new HashSet();
hashSet.add("Hello");
hashSet.add("World");
hashSet.add("Hello");// 重复元素,自动去重，即添加失败
System.out.println(hashSet);
}
@Test
public void testHashSetAddStudentAndCheckEqual() {
HashSet set = new HashSet();
set.add(new Student("张三",89));
set.add(new Student("张三",89));
set.add(new Student("李四",78));
set.add(new Student("王五",91));
for(Object o:set){
System.out.println(o);
}
Student s1 = new Student("张三",89);
Student s2 = new Student("张三",89);
System.out.println(s1 == s2);//false
System.out.println(s1.equals(s2));//true
}
}
三.List
3.1List接口的方法
package Collection.List;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.function.Predicate;
public class List_ {
/*
* List接口：继承自Collection接口
* 1.List特点和子类:
* - 所有List接口的实现类有共同点：有序、元素可重复
- 所有List接口的实现类有相同的API：在List接口中定义
* List接口的实现类有：ArrayList、LinkedList、Vector，Stack继承自Vector
ArrayList：jdk1.2开始出现的，底层是数组实现
LinkedList：jdk1.2开始出现的，底层是链表实现
Vector：jdk1.0开始出现的，底层是数组实现
* Stack：jdk1.0开始出现的，底层是数组实现
2.List的方法:
* 2.1 增
* 2.1.1 boolean add(ElementType e) : 添加一个元素
* 2.1.2 void add(int index, ElementType e) : 添加一个元素，指定位置
* 2.1.3 boolean addAll(Collection<? extends ElementType> c) : 添加一个集合
* 2.1.4 boolean addAll(int index, Collection<? extends ElementType> c) : 添加一个集合，指定位置
* 2.2 删
* 2.2.1 ElementType remove(int index) : 删除指定位置的元素
* 2.2.2 boolean remove(Object o) : 删除一个元素
* 2.2.3 void clear() : 删除所有元素
* 2.2.4 boolean removeAll(Collection<?> c) : 删除一个集合
* 2.2.5 boolean retainAll(Collection<?> c) : 保留一个集合
* 2.2.6 removeIf(Predicate<? super ElementType> filter) : 删除满足条件的元素
* 2.3 查
* 2.3.1 ElementType get(int index) : 获取指定位置的元素
* 2.3.2 int indexOf(Object o) : 获取指定元素的索引
* 2.3.3 int lastIndexOf(Object o) : 获取指定元素的索引，从后往前找
* 2.3.4 List<ElementType> subList(int fromIndex, int toIndex) : 获取指定范围的子列表
* 2.4 改
* 2.4.1 ElementType set(int index, ElementType element) : 修改指定位置的元素
* 2.4.2 void replaceAll(UnaryOperator<ElementType> operator) : 替换所有元素
* 2.5 遍历
* 2.5.1 forEach(Consumer<? super ElementType> action) : 遍历
* 2.5.2 Iterator<ElementType> iterator() : 获取迭代器
* 2.5.3 for循环 + size() + get(index)
* 2.5.4 ListIterator<ElementType> listIterator() : 获取列表迭代器
* *boolean hasNext() : 判断是否还有下一个元素
* *boolean hasPrevious() : 判断是否还有上一个元素
* *ElementType next() : 获取下一个元素
* *int nextIndex() : 获取下一个元素的索引
* *ElementType previous() : 获取上一个元素
* *int previousIndex() : 获取上一个元素的索引
* */
@Test
public void testListCreateAndAdd() {
/*2.1 增
* 2.1.1 boolean add(ElementType e) : 添加一个元素
* 2.1.2 void add(int index, ElementType e) : 添加一个元素，指定位置
* 2.1.3 boolean addAll(Collection<? extends ElementType> c) : 添加一个集合
* 2.1.4 boolean addAll(int index, Collection<? extends ElementType> c) : 添加一个集合，指定位置*/
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Orange");
list.add("Pear");
//System.out.println(list);
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
@Test
public void testListRemove() {
/*2.2 删
* 2.2.1 ElementType remove(int index) : 删除指定位置的元素
* 2.2.2 boolean remove(Object o) : 删除一个元素
* 2.2.3 void clear() : 删除所有元素
* 2.2.4 boolean removeAll(Collection<?> c) : 删除一个集合
* 2.2.5 boolean retainAll(Collection<?> c) : 保留一个集合
* 2.2.6 removeIf()*/
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Orange");
list.add("Pear");
System.out.println("原始列表为 : " + list);
ListIterator<String> iterator = list.listIterator();
/*while (iterator.hasNext()) {
System.out.println(iterator.next());
}*/
list.remove("Pear");
System.out.println("删除后的列表为 : " + list);
list.remove(1);
System.out.println("删除后的列表为 : " + list);
list.add("Apple");
list.add("Orange");
list.add("Pear");
System.out.println("添加后的列表为 : " + list);
Predicate<String> predicate = new Predicate<String>() {
@Override
public boolean test(String s) {
return s.startsWith("A");
}
};
list.removeIf(predicate);
System.out.println("removeIf删除后的列表为 : " + list);
}
@Test
public void testQuery(){
/* 2.3 查
* 2.3.1 ElementType get(int index) : 获取指定位置的元素
* 2.3.2 int indexOf(Object o) : 获取指定元素的索引
* 2.3.3 int lastIndexOf(Object o) : 获取指定元素的索引，从后往前找
* 2.3.4 List<ElementType> subList(int fromIndex, int toIndex) : 获取指定范围的子列表*/
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Orange");
list.add("Pear");
list.add("Watermaloon");
list.add("Banana");
list.add("Apple");
list.add("Apple");
list.add("Banana");
System.out.println("原始列表为 : " + list);
System.out.println("Apple的索引为 : " + list.indexOf("Apple"));
System.out.println("索引1的元素为 : " + list.get(1));
System.out.println("最后一个Apple的索引为 : " + list.lastIndexOf("Apple"));
System.out.println("子列表为 : " + list.subList(2,5));
}
@Test
public void testTraverse(){
/*2.5 遍历
* 2.5.1 forEach(Consumer<? super ElementType> action) : 遍历
* 2.5.2 Iterator<ElementType> iterator() : 获取迭代器
* 2.5.3 for循环 + size() + get(index)
* 2.5.4 ListIterator<ElementType> listIterator() : 获取列表迭代器
* *boolean hasNext() : 判断是否还有下一个元素
* *boolean hasPrevious() : 判断是否还有上一个元素*/
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Orange");
list.add("Pear");
list.add("Watermaloon");
list.add("Banana");
list.add("Apple");
list.add("Apple");
list.add("Banana");
System.out.println("遍历方法1 : ");
for(String s:list){
System.out.println(s);
}
System.out.println("遍历方法2 : ");
for(int i = 0; i < list.size(); i++){
System.out.println(list.get(i));
}
System.out.println("遍历方法3 : ");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
3.2ArrayList和Verctor
3.2.1ArrayList和Vector的区别
/* * 各种数组的区别 : * 1.List接口的子类 * Vector : 古老的动态数组 * Stack : 古老的栈结构容器 * ArrayList : jdk1.2开始出现的较新的动态数组 * LinkedList : jdk1.2开始出现的较新的链表（同时可以当栈节后，队列使用） * 2.动态数组ArrayList和Vector的区别 : * - ArrayList : * 1.线程不安全，速度更快 * 2.new ArrayList()的底层的数组长度默认是0，首次添加元素时，会自动扩容为10 * 3.扩容机制 : 数组扩容为原来的1.5倍 * 4.优点 : 空间利用率高 * 5.缺点 : 扩容频率高，搬家次数多，无法手动指定扩容的数量 * * - Vector : * 1.线程安全，速度更慢 * 2.new Vector()的底层的数组长度默认是10 * 3.优点 : 扩容频率少，搬家次数少 * 4.缺点 : 空间浪费的可能性大 * 5.Vector考虑到自己扩容太快，一次变为原来的2倍长度，就提供了另一种扩容的方式，你可以手动指定扩容多少空间。 * * */
3.2.2ArrayList最初容量为0，首次添加后长度变为10，扩容机制为原来的1.5倍
创建伊始：
添加10个元素
package Collection.List;
import org.junit.jupiter.api.Test;
import java.util.ArrayList;
import java.util.Vector;
public class ArrayList_ {
/*
* 各种数组的区别 :
* 1.List接口的子类
* Vector : 古老的动态数组
* Stack : 古老的栈结构容器
* ArrayList : jdk1.2开始出现的较新的动态数组
* LinkedList : jdk1.2开始出现的较新的链表（同时可以当栈节后，队列使用）
* 2.动态数组ArrayList和Vector的区别 :
* - ArrayList :
* 1.线程不安全，速度更快
* 2.new ArrayList()的底层的数组长度默认是0，首次添加元素时，会自动扩容为10
* 3.扩容机制 : 数组扩容为原来的1.5倍
* 4.优点 : 空间利用率高
* 5.缺点 : 扩容频率高，搬家次数多，无法手动指定扩容的数量
*
* - Vector :
* 1.线程安全，速度更慢
* 2.new Vector()的底层的数组长度默认是10
* 3.优点 : 扩容频率少，搬家次数少
* 4.缺点 : 空间浪费的可能性大
* 5.Vector考虑到自己扩容太快，一次变为原来的2倍长度，就提供了另一种扩容的方式，你可以手动指定扩容多少空间。
*
* */
@Test
public void testArrayList() {
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add("hello" + i);
System.out.println("第" + i + "次添加元素");
}
}
@Test
public void testVector() {
Vector<String> v = new Vector<>(10,2);//创建一个容量为10，每次扩容2倍
for(int i = 0; i < 10; i++){
v.add("hello" + i);
}
System.out.println(v);
v.add("hello10李");
System.out.println(v.size());
}
}
3.3Stack
3.3.1Stack功能
Stack是栈结构的容器，它遵循 先进后出 的原则。
注意：Stack同时也是List接口的实现类，所以List之前的方法，它也有。
Stack提供了几个特殊的方法，来满足 先进后出的操作原则：
（1）push(元素)：入栈
（2）pop()：弹出栈顶元素，然后返回
（3）peek()：查看栈顶元素
（4）search(元素)：从栈顶数这个元素是第几个
3.3.2code
package Collection.List;
import org.junit.jupiter.api.Test;
import java.util.Stack;
public class Stack_ {
/*
* Stack是栈结构的容器，它遵循 先进后出 的原则。
注意：Stack同时也是List接口的实现类，所以List之前的方法，它也有。
Stack提供了几个特殊的方法，来满足 先进后出的操作原则：
（1）push(元素)：入栈
（2）pop()：弹出栈顶元素，然后返回
（3）peek()：查看栈顶元素
（4）search(元素)：从栈顶数这个元素是第几个
* */
@Test
public void testStackCreateAndAdd() {
Stack<String> s = new Stack<>();
s.push("Apple");
s.push("Orange");
s.push("Pear");
System.out.println(s);
}
@Test
public void testStackRemove() {
Stack<String> s = new Stack<>();
s.push("Apple");
s.push("Orange");
s.push("Pear");
System.out.println("原始栈为 : " + s);
System.out.println("弹出的栈顶元素为 : " + s.pop());
System.out.println("弹出的栈顶元素为 : " + s.pop());
}
@Test
public void testStackQuery() {
Stack<String> s = new Stack<>();
s.push("Apple");
s.push("Orange");
s.push("Pear");
System.out.println("原始栈为 : " + s);
System.out.println(s.search("Apple"));
}
@Test
public void testPeek(){
Stack<String> s = new Stack<>();
s.push("Apple");
s.push("Orange");
s.push("Pear");
System.out.println("原始栈为 : " + s);
System.out.println("栈顶元素为 : " + s.peek());
}
@Test
public void testStackTraverse() {
Stack<String> s = new Stack<>();
s.push("Apple");
s.push("Orange");
s.push("Pear");
System.out.println("原始栈为 : " + s);
while (!s.empty()) {
System.out.println(s.pop());
}
}
}
3.4LinkList
3.4.1创建顺序
调用 LinkedList 对象的核心内存流程：先加载类（方法区）→ 执行 main 方法（虚拟机栈）→ 在堆中创建 LinkedList 对象 → 虚拟机栈中存储对象引用
3.4.2LinkList方法
package Collection.List;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.LinkedList;
public class LinkedList_ {
/*
1 LinkedList 的核心特性
1.1 底层结构：双向链表，每个节点包含前驱、后继指针，无固定容量，无需扩容
1.2 核心优势：首尾元素增删效率高（O (1)），支持双端操作
1.3 核心劣势：随机访问效率低（O (n)），需遍历链表
2 List 接口通用方法（LinkedList 实现）
这类方法是所有 List 集合的通用方法，LinkedList 完全支持，核心用于 “通用的增删改查”。
2.1 新增元素
2.1.1 boolean add (E e)：将元素添加到链表末尾，返回是否成功（始终返回 true）
2.1.2 void add (int index, E element)：在指定索引位置插入元素（需遍历到指定位置，效率低）
2.1.3 boolean addAll (Collection<? extends E> c)：将集合中所有元素添加到链表末尾
2.1.4 boolean addAll (int index, Collection<? extends E> c)：从指定索引开始插入集合中所有元素
2.2 删除元素
2.2.1 E remove (int index)：删除指定索引位置的元素，返回被删除的元素
2.2.2 boolean remove (Object o)：删除第一个匹配的指定元素，返回是否删除成功
2.2.3 void clear ()：清空链表中所有元素
2.3 修改元素
2.3.1 E set (int index, E element)：替换指定索引位置的元素，返回原元素
2.4 查询元素
2.4.1 E get (int index)：获取指定索引位置的元素（需遍历链表，随机访问效率低）
2.4.2 int size ()：返回链表中元素的个数
2.4.3 boolean isEmpty ()：判断链表是否为空
2.4.4 boolean contains (Object o)：判断链表是否包含指定元素
2.4.5 int indexOf (Object o)：返回第一个匹配元素的索引，无则返回 - 1
2.4.6 int lastIndexOf (Object o)：返回最后一个匹配元素的索引，无则返回 - 1
2.5 遍历相关
2.5.1 Iterator<E> iterator ()：获取普通迭代器，正向遍历
2.5.2 ListIterator<E> listIterator ()：获取 List 迭代器，支持双向遍历
2.5.3 ListIterator<E> listIterator (int index)：从指定索引开始的 List 迭代器
3 LinkedList 特有方法（双端队列 / 链表专属）
这类方法是 LinkedList 作为双端队列（Deque）的特有方法，专门优化 “首尾操作”，效率为 O (1)，是 LinkedList 的核心优势。
3.1 首尾新增元素（队列 / 栈操作）
3.1.1 void addFirst (E e)：将元素添加到链表头部
3.1.2 void addLast (E e)：将元素添加到链表尾部（等同于 add (E e)）
3.1.3 boolean offerFirst (E e)：添加元素到头部，返回是否成功（始终返回 true）
3.1.4 boolean offerLast (E e)：添加元素到尾部，返回是否成功（始终返回 true）
3.1.5 void push (E e)：将元素压入栈顶（等同于 addFirst (E e)，栈操作）
3.2 首尾删除元素
3.2.1 E removeFirst ()：删除并返回头部元素，链表为空时抛 NoSuchElementException
3.2.2 E removeLast ()：删除并返回尾部元素，链表为空时抛 NoSuchElementException
3.2.3 E pollFirst ()：删除并返回头部元素，链表为空时返回 null（更安全）
3.2.4 E pollLast ()：删除并返回尾部元素，链表为空时返回 null（更安全）
3.2.5 E pop ()：弹出栈顶元素（等同于 removeFirst ()，栈操作）
3.3 首尾查询元素（不删除）
3.3.1 E getFirst ()：获取头部元素，链表为空时抛 NoSuchElementException
3.3.2 E getLast ()：获取尾部元素，链表为空时抛 NoSuchElementException
3.3.3 E peekFirst ()：获取头部元素，链表为空时返回 null（更安全）
3.3.4 E peekLast ()：获取尾部元素，链表为空时返回 null（更安全）
*/
/*
*Vector和ArrayList的区别:
1.ArrayList底层是一个数组。
数组的元素是连续存储的，开辟一整块连续的存储空间，如果通过下标访问元素，效率非常高，时间复杂度是O(1)。
O(1)是一个固定值，代表无论数组长度是多长，根据下标查找元素的效率是一样的，都是一步到位。
比喻：大家出去住酒店，房间号是连续的，你告诉我房间号，我直接奔这个房间就可以了。
数组的长度是固定的，不过存了就要扩容。需要频繁的搬家。
数组如果中间插入或删除元素，后面的元素需要移动，因为要保证连续性。
2.LinkedList：它的底层是一个双向链表。
链表的元素不一定是连续的，需要前后元素记录对方的地址。比喻：大家出去住酒店，房间号不是连续的，甚至不在一个酒店。每个人需要记前后同学住在哪里。
如果要找第5个人，需要从第1个开始，陆续拿到下一个同学的地址，找到第5个。如果通过下标访问元素，效率较低，时间复杂度是O(n)。
链表不需要扩容，不需要搬家。
问：动态数组效率高，还是链表效率高？
（1）如果根据下标访问元素，动态数组高。
（2）如果是非末尾位置插入和删除，理论上是链表高，因为不需要扩容移动元素，也不需要扩容。
如果是在Java中，双向链表的效率不见得高，因为双向链表需要结点对象，而创建结点，回收结点也是一个麻烦的事情。
* */
@Test
public void testLinkedListCreateAndAdd() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
list.add("hello4");
System.out.println("添加后的列表为 : " + list);
LinkedList<String> list2 = new LinkedList<>(Arrays.asList("hello5", "hello6", "hello7"));
System.out.println("添加后的列表为 : " + list2);
}
@Test
public void testAddAsInsert(){
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
list.add(1,"hello4");
System.out.println("修改后的列表为 : " + list);
}
@Test
public void testAddFirst() {
LinkedList<String> list = new LinkedList<>();
list.addFirst("hello1");
list.addFirst("hello2");
list.addFirst("hello3");
System.out.println("添加后的列表为 : " + list);
}
@Test
public void testAddLast() {
LinkedList<String> list = new LinkedList<>();
list.addLast("hello1");
list.addLast("hello2");
list.addLast("hello3");
System.out.println("添加后的列表为 : " + list);
}
@Test
public void testRemoveFirst() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
System.out.println("删除前的列表为 : " + list);
list.removeFirst();
System.out.println("删除后的列表为 : " + list);
}
@Test
public void testRemoveLast() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
System.out.println("删除前的列表为 : " + list);
list.removeLast();
System.out.println("删除后的列表为 : " + list);
}
@Test
public void testRemoveMediumElem(){
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
list.add("hello4");
list.remove("hello2");
list.remove(2);
System.out.println("删除后的列表为 : " + list);
}
@Test
public void testGetFirst() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
System.out.println("获取的元素为 : " + list.getFirst());
}
@Test
public void testGetLast() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
System.out.println("获取的元素为 : " + list.getLast());
}
@Test
public void testSet() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
list.set(1, "hello4");
System.out.println("修改后的列表为 : " + list);
}
@Test
public void testContains() {
LinkedList<String> list = new LinkedList<>();
list.add("hello1");
list.add("hello2");
list.add("hello3");
System.out.println("列表中是否包含hello2 : " + list.contains("hello4"));
}
}
3.4Queue
package Collection.Queue;
import org.junit.jupiter.api.Test;
import java.util.LinkedList;
import java.util.Queue;
public class Queue_ {
/*
* 普通队列方法:
* 1. 插入
* 1.1 add(E e)：将元素添加到队列末尾，返回是否成功（始终返回 true） 队列满时抛出异常
* 1.2 offer(E e)：将元素添加到队列末尾，返回是否成功（始终返回 true） 不抛出异常，返回特殊值
*
* 2. 删除
* 2.1 remove()：删除并返回队列头部元素，队列为空时抛 NoSuchElementException
* 2.2 poll()：删除并返回队列头部元素，队列为空时返回 null（更安全）
*
* 3.检查
* 3.1 element()：返回队列头部元素，队列为空时抛 NoSuchElementException
* 3.2 peek()：返回队列头部元素，队列为空时返回 null（更安全）
*
* 4. 查询
* 4.1 size()：返回队列元素个数
* 4.2 isEmpty()：判断队列是否为空
* 4.3 contains(Object o)：判断队列是否包含指定元素
* 4.4 toArray()：返回队列元素
*
* 5. 遍历
* 5.1 迭代器：iterator()
* 5.2 增强for：for (E e : queue)
* 5.3 普通for：for (int i = 0; i < queue.size(); i++)
* */
@Test
public void testQueueCreateAndOffer(){
Queue<String> queue = new LinkedList<>();
queue.offer("hello1");
queue.offer("hello2");
queue.offer("hello3");
System.out.println("添加后的队列为 : " + queue);
}
@Test
public void testQueueRemoveAndPoll(){
Queue<String> queue = new LinkedList<>();
queue.offer("hello1");
queue.offer("hello2");
queue.offer("hello3");
System.out.println("删除前的队列为 : " + queue);
queue.remove();
System.out.println("删除后的队列为 : " + queue);
queue.poll();
System.out.println("删除后的队列为 : " + queue);
}
@Test
public void testQueueElementAndPeek(){
Queue<String> queue = new LinkedList<>();
queue.offer("hello1");
queue.offer("hello2");
queue.offer("hello3");
System.out.println("队首元素为 : " + queue.element());
System.out.println("队首元素为 : " + queue.peek());
}
@Test
public void testQueueSizeIsEmptyContains(){
Queue<String> queue = new LinkedList<>();
queue.offer("hello1");
queue.offer("hello2");
queue.offer("hello3");
System.out.println("队列元素个数为 : " + queue.size());
System.out.println("队列是否为空 : " + queue.isEmpty());
System.out.println("队列是否包含 hello1 : " + queue.contains("hello1"));
System.out.println("队列是否包含 hello4 : " + queue.contains("hello4"));
}
@Test
public void testQueueToArray(){
Queue<String> queue = new LinkedList<>();
queue.offer("hello1");
queue.offer("hello2");
queue.offer("hello3");
Object[] list = queue.toArray();
for(Object o : list){
System.out.println(o);
}
}
@Test
public void testQueueIterator(){
Queue<String> queue = new LinkedList<>();
queue.offer("hello1");
queue.offer("hello2");
queue.offer("hello3");
for(String s : queue){
System.out.println(s);
}
}
}
四.Map
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
22
0- 0
已为社区贡献14条内容
所有评论(0)