【Java】集合与数据结构

一、数据结构

1、栈

1. 压栈 / 弹栈
2. 栈顶元素、栈底元素
3. 先进后出

2、队列

1. 入队列 / 出队列
2. 前端、后端
3. 先进先出

3、数组

查询效率高，增删效率低

4、链表

查询效率低(必须从头找)，增删效率高

5、哈希表

1. 比较方法
   1. 哈希值
   2. equals
2. 结构：数组 + 链表
   1. 元素位置：“hashCode % 位置”
   2. 相同位置的元素通过链表形式连接

二、集合类体系结构

1. Collection：单列
   1. List：可重复
      1. ArrayList
      2. LinkedList
         1. Set：不可重复
      3. HashSet
      4. TreeSet
2. Map：双列
   1. HashMap

三、Collection

1、概述

单例集合的顶层接口，无直接实现

2、创建对象

多态：利用ArrayList

Collection<String> c = new ArrayList<String>();

3、成员方法

（1）add()：添加元素

boolean add(E e)     // 永远返回true,重写了`toString()`方法

（2）remove()：移除元素

boolean remove(Object o)

（3）clear()：清空集合

void clear()

（4）contains()：判断是否存在

boolean contains(Object o)

（5）isEmpty()：判空

boolean isEmpty()

（6）size()：元素个数

int size()

4、快捷键补充

A/t + 7 ：查看结构框架

四、迭代器Iterator

1、概述

Iterator：迭代器用于集合遍历

Iterator<E> iterator();：返回集合元素的迭代器

迭代器依赖于集合存在

2、常用方法

1. `E next()`：返回迭代器下一元素
2. `boolean hasNext()`：是否存在下一元素

while(it.hasNext()){
   
    String s = it.next();
    sout(s);
}

五、List及其子类

1、List

List：有序集合，可以控制每个元素的插入位置，可以索引访问元素

2、List特有方法

（1）add(index, e)：指定插入

//定义
void add(int index, E e)

（2）remove(index)：指定删除

//定义
E remove(int index)        //返回老元素

（3）set(index, e)：指定修改

//定义
E set(int index, E e)    //返回老元素

（4）get(index)：指定获取

//定义
E get(int index)        //返回老元素

3、ListIterator

（1）概述

ListIterator：列表迭代器，是List集合特有的

（2）特点

1. 可以任意方向遍历
2. 可以迭代时修改集合

（3）方法

1. `E previous()`：返回迭代器上一元素
2. `boolean hasPrevious()`：是否存在上一元素
3. `void add(E e)`：插入指定元素

List<String> list = new ArrayList<String>();
ListIterator<String> it = list.listiterator();
while(it.hasNext()){
   
    String s = it.next();
    if(s.equals("world")){
   
        it.add("javaee");
    }
}

4、ArrayList

数组实现：查询快，增删慢

5、LinkedList

（1）概述

链表实现：查询慢，增删快

（2）特有功能

1. `void addFirst()`
2. `void addLast()`
3. `E getFirst()`
4. `E getLast()`
5. `E removeFirst()`
6. `E removeLast()`

六、并发修改异常

1、异常原因

遍历时修改了集合元素长度

List<String> list = new ArrayList<String>();
Iterator<String> it = list.iterator();
while(it.hasNext()){
   
    String s = it.next();
    if(s.equals("world")){
   
        list.add("javaee");
    }
}

2、修改办法

（1）不用迭代器，用for循环索引元素

List<String> list = new ArrayList<String>();
for(int i = 0; i < list.size(); i++){
   
    String s = list.get(i);
    if(s.equals("world")){
   
        list.add("javaee");
    }
}

（2）用列表迭代器添加元素

List<String> list = new ArrayList<String>();
ListIterator<String> it = list.listiterator();
while(it.hasNext()){
   
    String s = it.next();
    if(s.equals("world")){
   
        it.add("javaee");
    }
}

七、增强for

增强for循环：简化数组和Collection集合的遍历

1. 实现Iterable接口的类允许其对象成为增强型for循环的目标
2. 原理是Iterator迭代器 --> 会触发“并发修改异常”

for(元素数据类型 变量名 : 数组/Collection集合){
   
    //变量就是元素
}

//示例
int[] arr = {
   1,2,3,4,5};
for(int i : arr){
   
    sout(i);
}

八、Set及其子类

1、Set

1. 不包含重复元素
2. 没有索引，不能用普通for循环遍历
3. 迭代顺序随机

2、HashSet

（1）哈希值

1. 根据对象的地址/字符串/数字算出来的int类型的数值
2. `public int hashCode`
1. 返回对象的哈希值
2. Object类

（2）HashSet概述

1. 底层为哈希表(HashMap)
2. 迭代顺序无保障
3. 没有索引，不能用不同for循环遍历
4. Set集合没有重复元素 --> **需要重写对象的hashCode与equal方法**

（3）HashSet存储特点

1. 比较方法
   1. 哈希值
   2. equals
2. 结构：数组 + 链表
   1. 元素位置：“hashCode % 位置”
   2. 相同位置的元素通过链表形式连接

3、LinkedHashSet

1. 底层：链表 + 哈希表
2. 可预测的迭代次序
3. HashSet集合没有重复元素

4、TreeSet

1. 元素有序
   1. 自然排序：无参构造TreeSet()
   2. 比较器排序：带参构造TreeSet(Comparator comparator)
2. 存储引用类/包装类类型

自然排序 --> 重写compareTo方法

@Override
public int compareTo(Stu s){
   
    return this.age - s.age == 0 ? this.name.compareTo(s.name) : this.age - s.age;
}

比较器排序 --> 匿名内部类

TreeSet<Stu> ts = new TreeSet<>(new Comparator<Stu>(){
   
    @Override
    public int compare(Stu s1, Stu s2){
   
        return s1.getAge() - s2.getAge() == 0 ? s1.getName().compareTo(s2.getName()) : s1.getAge() - s2.getAge();
    }
});

九、泛型

1、泛型概述

1. 将类型由原来的具体的类型参数化，然后在使用/调用时传入具体的类型
2. 本质：参数化类型
3. 实参类型只能是引用数据类型
4. 泛型定义格式
   1. <类型>
   2. <类型1, 类型2...>

2、泛型类定义格式

1. 修饰符 class 类名<类型>{...}
2. 类型可以是随便写的任意标识
   1. T：type
   2. E：element
   3. K：key
   4. V：value

3、泛型方法

1. 泛型方法 --> 不限制类型的万金油
2. 泛型方法定义格式 --> 修饰符 <类型> 返回值类型 方法名(类型 变量名){...}

4、泛型接口

修饰符 interface 接口名<类型>{...}

5、类型通配符

1. 类型通配符：<?>
   1. 表示各种泛类List的父类
   2. 元素可以匹配任何类型
   3. 不能添加元素
2. 类型通配符的上限：<? extends 类型>
   1. 表示此类型及其子类
3. 类型通配符的下限：<? super 类型>
   1. 表示此类型及其父类

6、可变参数

（1）可变参数的定义格式

修饰符 返回值类型 方法名(数据类型...变量名){}

public static int sum(int...a){
   
    int sum = 0;
    for(int i : a){
   
        sum += i;
    }
    return sum;
}

（2）特点

1. 变量其实是数组
2. 多个参数要把可变参数放最后

（3）可变参数的应用

1. Arrays工具类的静态方法

// 定义
public static <T> List<T> asList(T...a)
// 使用
List<String> list = Arrays.asList("wc","wmh");

返回有指定数组支持的固定大小的列表 --> 不能增删可以改

2. List接口的静态方法

// 定义
public static <E> List<E> of(E...elements)
// 使用
List<String> list = List.of("wc","wmh");

返回包含任意数量元素的不可变列表 --> 不能增删改

3. Set接口的静态方法

// 定义
public static <E> Set<E> of(E...elements)
// 使用
Set<String> s = Set.of("wc","wmh");

返回一个包含任意数量元素的不可变集合 --> 不能增删改

十、Map

1、概述

Interface Map<K, V>

K：键 V：值

将key映射到value的对象

key不可以重复 && 每个key只对应一个value

2、创建Map集合的方式

多态

3、具体实现类：HashMap

1. 添加元素：V put(K key, V value)

2. 删除：V remove(Object key)

3. 清空：void clear()

4. 判键存在：boolean containsKey(Object key)

5. 判值存在：boolean containsValue(Object key)

6. 判空：boolean isEmpty()

7. 集合长度：int size()

1. Map的获取方法

   1. 根据键获取值

      // 定义
      V get(Object key)
      // 使用
      Map<String,String> map = new Map<>();
      map.put("1","wmh");
      sout(map.get("1"));
      

   2. 获取所有键的集合

      // 定义
      Set<K> keySet()
      // 使用
      Set<String> keySet = map.keySet();
      for(String key : keySet){
             
       sout(key);
      }
      

   3. 获取所有值的集合

      // 定义
      Collection<V> values()
      // 使用
      Collection<String> values = map.values();
      for(String value : values){
             
       sout(value);
      }
      

   4. 获取所有键值对对象的集合

      // 定义
      Set<Map.Entry<K, V>> entrySet()
      // 使用
      Set<Map.Entry<String,String>> entrySet = map.entrySet();
      for(Map.Entry<String,String> me : entrySet){
             
       sout(me.getKey() + "," + me.getValue());
      }
      

2. Map集合的遍历

   // 方式1
   Set<String> keySet = map.keySet();
   for(String key : keySet){
        
   sout(key + "," + map.get(key));
   }
   // 方式2
   Set<Map.Entry<String,String>> entrySet = map.entrySet();
   for(Map.Entry<String,String> me : entrySet){
        
   sout(me.getKey() + "," + me.getValue());
   }
   

十一、Collections工具类

常用方法(类要重写compareTo方法)

1、列表升序排列

// 定义
public static <T extends Comparable<? superT>> void sort(List<T> list)
// 使用:普通集合
Collections.sort(list);
// 使用:类的集合 --> 比较器排序 --> 匿名内部类/类内重写
ArrayList<Stu> array = new ArrayList<>();
Collections.sort(array, new Comparator<Stu>(){
   
    @Override
    public int compare(Stu s1, Stu s2){
   
        return s1.getAge() - s2.getAge() == 0 ? s1.getName().compareTo(s2.getName()) : s1.getAge() - s2.getAge();
    }
});

2、反转列表顺序

// 定义
public static void reverse(List<?> list)
// 使用
Collections.reverse(list);

3、列表随机排列

// 定义
public static void reverse(List<?> list)
// 使用
Collections.reverse(list);