List、Set、数据结构、Collections

一、数据结构

1.1 常用的数据结构

栈

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

简单的说：采用该结构的集合，对元素的存取有如下的特点

先进后出（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。例如，子弹压进弹夹，先压进去的子弹在下面，后压进去的子弹在上面，当开枪时，先弹出上面的子弹，然后才能弹出下面的子弹。
栈的入口、出口的都是栈的顶端位置。

这里两个名词需要注意：

压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

简单的说，采用该结构的集合，对元素的存取有如下的特点：

先进先出（即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。例如，小火车过山洞，车头先进去，车尾后进去；车头先出来，车尾后出来。
队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口。

数组

数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。

简单的说,采用该结构的集合，对元素的存取有如下的特点：

查找元素快：通过索引，可以快速访问指定位置的元素

增删元素慢

指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置

指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中

链表

链表:linked list,由一系列节点node（链表中每一个元素称为结点）组成，节点可以在运行时i动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表，那么这里给大家介绍的是单向链表。

简单的说，采用该结构的集合，对元素的存取有如下的特点：

多个结点之间，通过地址进行连接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。

查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素
增删元素快：
- 增加元素：只需要修改连接下个元素的地址即可。

删除元素：只需要修改连接下个元素的地址即可。

红黑树

二叉树：binary tree ,是每个结点不超过2的有序树（tree） 。

简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点。

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。

如图：

我们要说的是二叉树的一种比较有意思的叫做红黑树，红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。

红黑树的约束:

节点可以是红色的或者黑色的

根节点是黑色的

叶子节点(特指空节点)是黑色的
每个红色节点的子节点都是黑色的
任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点:

速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍

二、List集合

List接口特点：

它是一个元素存取有序的集合。
它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

常用方法：

public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
public E get(int index):返回集合中指定位置的元素。
public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

public class ListDemo {public static void main(String[] args) {// 创建List集合对象List<String> list = new ArrayList<String>();// 往 尾部添加 指定元素list.add("图图");list.add("小美");list.add("不高兴");System.out.println(list);// add(int index,String s) 往指定位置添加list.add(1,"没头脑");System.out.println(list);// String remove(int index) 删除指定位置元素  返回被删除元素// 删除索引位置为2的元素 System.out.println("删除索引位置为2的元素");System.out.println(list.remove(2));System.out.println(list);// String set(int index,String s)// 在指定位置 进行 元素替代（改） // 修改指定位置元素list.set(0, "三毛");System.out.println(list);// String get(int index)  获取指定位置元素// 跟size() 方法一起用  来 遍历的 for(int i = 0;i<list.size();i++){System.out.println(list.get(i));}//还可以使用增强forfor (String string : list) {System.out.println(string);}  	}
}

三、List的子类

3.1ArrayList集合

数据结构特点

数据结构: ArrayList 是基于对象数组实现。它可以存储对象的可变大小列表。
特点:
- 动态大小: ArrayList 可以根据需要自动调整大小，不需要事先定义容量。
- 随机访问比较快: 由于底层是数组，ArrayList 支持快速的随机访问，时间复杂度为 O(1)。
- 插入和删除的效率比较低: 在数组中间插入或删除元素时，可能会导致后续元素的移动，时间复杂度为 O(n)。
- 非同步: ArrayList 是非线程安全的，如果在多线程环境下使用，需要手动同步。

底层实现原理

ArrayList 底层使用一个 Object 数组来存储元素。创建一个 ArrayList 时，会初始化一个默认的空数组。
当元素被添加到 ArrayList 中，首先会检查当前数组的容量是否足够。如果容量不足，就会触发扩容。

扩容原理

默认情况下，ArrayList 会初始化一个大小为 10 的数组。
当添加新元素超过当前数组的大小时，会进行扩容。扩容的过程是：
- 创建一个新的数组，通常是原数组大小的 1.5 倍（或者是 2 倍，具体实现可能有所不同）。
- 将原数组中的元素复制到新创建的数组中。
- 重新管理元素的索引。

3.2 LinkedList集合

LinkedList集合数据存储的结构是链表结构。方便元素添加、删除的集合

特点：

动态大小: 与 ArrayList 不同，LinkedList 的大小是动态的，不需要事先设置容量，节点的增加和删除操作不会涉及其他节点的移动。
插入和删除: 在链表中，插入和删除操作非常高效（时间复杂度为 O(1)），只需调整相关节点的指针即可，而不需要移动元素。
迭代性能: 由于链表的节点分布在内存中，随机访问（使用索引访问元素）效率较低，时间复杂度为 O(n)，适合于顺序访问和动态变化的场景。
LinkedList是非线程安全的

②、底层原理

双向链表: LinkedList 是通过双向链表实现的，允许从链表的任意一端快速插入和删除元素。
头指针和尾指针: LinkedList 通常维护一个指向第一个节点的头指针和指向最后一个节点的尾指针，使得在链表的两端进行添加和删除操作更加高效。

③、没有扩容的

④、常用方法

ublic void addFirst(E e):将指定元素插入此列表的开头。
public void addLast(E e):将指定元素添加到此列表的结尾。
public E getFirst():返回此列表的第一个元素。
public E getLast():返回此列表的最后一个元素。
public E removeFirst():移除并返回此列表的第一个元素。
public E removeLast():移除并返回此列表的最后一个元素。
public E pop():从此列表所表示的堆栈处弹出一个元素。
public void push(E e):将元素推入此列表所表示的堆栈。
public boolean isEmpty()：如果列表不包含元素，则返回true。

LinkedList是List的子类，List中的方法LinkedList都是可以使用，这里就不做详细介绍，我们只需要了解LinkedList的特有方法即可。在开发时，LinkedList集合也可以作为堆栈，队列的结构使用。（了解）

public class LinkedListDemo {public static void main(String[] args) {LinkedList<String> link = new LinkedList<String>();//添加元素link.addFirst("abc1");link.addFirst("abc2");link.addFirst("abc3");System.out.println(link);// 获取元素System.out.println(link.getFirst());System.out.println(link.getLast());// 删除元素System.out.println(link.removeFirst());System.out.println(link.removeLast());while (!link.isEmpty()) { //判断集合是否为空System.out.println(link.pop()); //弹出集合中的栈顶元素}System.out.println(link);“重地 通话”} 
}

四、Set接口

Set接口和jList接口一样，同样继承自Collection接口，它与Collection接口中的方法基本一致，并没有对Collection接口进行功能上的扩充，只是比Collection接口更加严格了。与List接口不同的是，Set接口中元素无序，并且都会以某种规则保证存入的元素不出现重复。

4.1 HashSet集合

HashSet是Set接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。HashSet底层的实现其实是一个HashMap支持。HashSet是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于：hashCode与equals方法。

public class HashSetDemo {public static void main(String[] args) {//创建 Set集合HashSet<String>  set = new HashSet<String>();//添加元素set.add(new String("cba"));set.add("abc");set.add("bac"); set.add("cba");  //遍历for (String name : set) {System.out.println(name);}}
}

输出结果如下，说明集合中不能存储重复元素

cba
abc
bac

4.2 HashSet集合存储数据的结构（哈希表）

HashSet(哈希表实现)

哈希表（HashMap），也被称为散列表，是一种高效的数据结构，它支持快速查找、插入和删除操作。哈希表的核心思想是通过一个称为哈希函数的映射机制，将存储的数据（通常是键值对形式）转换成一个数组索引，从而可以直接访问存储位置。

主要特点：
快速存取：理想情况下，哈希表的平均时间复杂度为O(1)，意味着无论是查找、插入还是删除操作，理论上都能在常数时间内完成。
哈希函数：这是决定哈希表性能的关键因素之一。一个好的哈希函数应该能够均匀地分布数据，减少哈希冲突的发生。
哈希冲突：由于哈希函数产生的索引范围有限，当两个不同的键通过哈希函数得到相同的索引时，就会发生哈希冲突。解决哈希冲突的方法包括开放寻址法、拉链法等。
动态调整：随着哈希表中数据量的变化，为了保持良好的性能，可能需要对哈希表的大小进行动态调整。

JDK1.8 HashMap:

底层数据结构: 数组 + 链表 + 红黑树

扩容原理
初始容量与加载因子：
初始容量是指 HashMap 创建时的默认大小，默认值为16。
加载因子决定了 HashMap 在多满的情况下开始扩容，默认值为0.75。这意味着当 HashMap 中的元素数量达到容量的75%时，就会触发扩容操作。
扩容时机：
当 HashMap 中的元素数量达到 capacity * load factor 时，会触发扩容。
扩容后的容量通常是原来的两倍。
扩容过程：
创建一个新的数组，其长度为原数组长度的两倍。
将原有的每个键值对重新计算哈希值，并根据新的数组长度确定它们在新数组中的位置。
将所有键值对从旧数组迁移到新数组中。这一步可能涉及大量的数据迁移工作，因此扩容是一个相对耗时的操作。
如果存在哈希碰撞（即多个键值对被分配到了同一个位置），这些键值对会形成一个链表或红黑树（当链表长度超过8且数组长度大于等于64时，链表会转换为红黑树以提高查找效率）。
迁移过程中的性能影响：
扩容操作需要遍历整个 HashMap，因此这是一个O(n)的操作。
在多线程环境下，扩容操作可能会导致竞争条件，因为多个线程可能同时尝试扩容同一个 HashMap。为了解决这个问题，Java 8 引入了 ConcurrentHashMap，它通过分段锁来减少并发修改时的竞争。

4.3 HashSet存储自定义类型元素

给HashSet中存放自定义类型元素时，需要重写对象中的hashCode和equals方法，建立自己的比较方式，才能保证HashSet集合中的对象唯一

创建自定义Student类

package exercise;import java.util.Objects;public class Student {private String name;private int age;public Student() {}public Student(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o)return true;if (o == null || getClass() != o.getClass())return false;Student student = (Student) o;return age == student.age &&Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}
}

public class HashSetDemo2 {public static void main(String[] args) {//创建集合对象   该集合中存储 Student类型对象HashSet<Student> stuSet = new HashSet<Student>();//存储 Student stu = new Student("于谦", 43);stuSet.add(stu);stuSet.add(new Student("郭德纲", 44));stuSet.add(new Student("于谦", 43));stuSet.add(new Student("郭麒麟", 23));stuSet.add(stu);for (Student stu2 : stuSet) {System.out.println(stu2);}}
}
执行结果：
Student [name=郭德纲, age=44]
Student [name=于谦, age=43]
Student [name=郭麒麟, age=23]

4.4LinkedHashSet

我们知道HashSet保证元素唯一，可是元素存放进去是没有顺序的，那么我们要保证有序，怎么办呢？

在HashSet下面有一个子类java.util.LinkedHashSet，它是链表和哈希表组合的一个数据存储结构。

演示代码如下:

public class LinkedHashSetDemo {public static void main(String[] args) {Set<String> set = new LinkedHashSet<String>();set.add("bbb");set.add("aaa");set.add("abc");set.add("bbc");Iterator<String> it = set.iterator();while (it.hasNext()) {System.out.println(it.next());}}
}
结果：bbbaaaabcbbc

4.5 可变参数

在JDK1.5之后，如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，我们可以对其简化成如下格式：

修饰符返回值类型方法名(参数类型... 形参名){ }

其实这个书写完全等价与

修饰符返回值类型方法名(参数类型[] 形参名){ }

只是后面这种定义，在调用时必须传递数组，而前者可以直接传递数据即可。

JDK1.5以后。出现了简化操作。... 用在参数上，称之为可变参数。

同样是代表数组，但是在调用这个带有可变参数的方法时，不用创建数组(这就是简单之处)，直接将数组中的元素作为实际参数进行传递，其实编译成的class文件，将这些元素先封装到一个数组中，在进行传递。这些动作都在编译.class文件时，自动完成了。

代码演示：

public class ChangeArgs {public static void main(String[] args) {int[] arr = { 1, 4, 62, 431, 2 };int sum = getSum(arr);System.out.println(sum);//  6  7  2 12 2121// 求 这几个元素和 6  7  2 12 2121int sum2 = getSum(6, 7, 2, 12, 2121);System.out.println(sum2);}/** 完成数组  所有元素的求和 原始写法public static int getSum(int[] arr){int sum = 0;for(int a : arr){sum += a;}return sum;}*///可变参数写法public static int getSum(int... arr) {int sum = 0;for (int a : arr) {sum += a;}return sum;}
}

五、Collections

5.1常用功能

java.utils.Collections是集合工具类，用来对集合进行操作。部分方法如下：

public static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素。
public static void shuffle(List<?> list) 打乱顺序:打乱集合顺序。
public static <T> void sort(List<T> list):将集合中元素按照默认规则排序。
public static <T> void sort(List<T> list，Comparator<? super T> ):将集合中元素按照指定规则排序。

代码演示：

public class CollectionsDemo {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<Integer>();//原来写法//list.add(12);//list.add(14);//list.add(15);//list.add(1000);//采用工具类 完成 往集合中添加元素  Collections.addAll(list, 5, 222, 1，2);System.out.println(list);//排序方法 Collections.sort(list);System.out.println(list);}
}
结果：
[5, 222, 1, 2]
[1, 2, 5, 222]

代码演示之后，发现我们的集合按照顺序进行了排列，可是这样的顺序是采用默认的顺序，如果想要指定顺序那该怎么办呢？

我们发现还有个方法没有讲，public static <T> void sort(List<T> list，Comparator<? super T> ):将集合中元素按照指定规则排序。接下来讲解一下指定规则的排列

5.2Comparator比较器

我们还是先研究这个方法

public static <T> void sort(List<T> list):将集合中元素按照默认规则排序。

不过这次存储的是字符串类型。

public class CollectionsDemo2 {public static void main(String[] args) {ArrayList<String>  list = new ArrayList<String>();list.add("cba");list.add("aba");list.add("sba");list.add("nba");//排序方法Collections.sort(list);System.out.println(list);}
}结果：
[aba, cba, nba, sba]

我们使用的是默认的规则完成字符串的排序，那么默认规则是怎么定义出来的呢？

说到排序了，简单的说就是两个对象之间比较大小，那么在JAVA中提供了两种比较实现的方式，一种是比较死板的采用java.lang.Comparable接口去实现，一种是灵活的当我需要做排序的时候在去选择的java.util.Comparator接口完成。

那么我们采用的public static <T> void sort(List<T> list)这个方法完成的排序，实际上要求了被排序的类型需要实现Comparable接口完成比较的功能，在String类型上如下：

public final class String implements java.io.Serializable, Comparable<String>, CharSequence {

String类实现了这个接口，并完成了比较规则的定义，但是这样就把这种规则写死了，那比如我想要字符串按照第一个字符降序排列，那么这样就要修改String的源代码，这是不可能的了，那么这个时候我们可以使用

public static <T> void sort(List<T> list，Comparator<? super T> )方法灵活的完成，这个里面就涉及到了Comparator这个接口，位于位于java.util包下，排序是comparator能实现的功能之一,该接口代表一个比较器，比较器具有可比性！顾名思义就是做排序的，通俗地讲需要比较两个对象谁排在前谁排在后，那么比较的方法就是：

public int compare(String o1, String o2)：比较其两个参数的顺序。

两个对象比较的结果有三种：大于，等于，小于。

如果要按照升序排序，则o1 小于o2，返回（负数），相等返回0，01大于02返回（正数）如果要按照降序排序则o1 小于o2，返回（正数），相等返回0，01大于02返回（负数

例：

public class CollectionsDemo3 {public static void main(String[] args) {ArrayList<String> list = new ArrayList<String>();list.add("cba");list.add("aba");list.add("sba");list.add("nba");//排序方法  按照第一个单词的降序Collections.sort(list, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return o2.charAt(0) - o1.charAt(0);}});System.out.println(list);}
}结果：
[sba, nba, cba, aba]

5.3简述Comparable和Comparator两个接口的区别。

Comparable：强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的compareTo方法被称为它的自然比较方法。只能在类中实现compareTo()一次，不能经常修改类的代码实现自己想要的排序。实现此接口的对象列表（和数组）可以通过Collections.sort（和Arrays.sort）进行自动排序，对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。

Comparator强行对某个对象进行整体排序。可以将Comparator 传递给sort方法（如Collections.sort或 Arrays.sort），从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构（如有序set或有序映射）的顺序，或者为那些没有自然顺序的对象collection提供排序。

创建一个学生类，存储到ArrayList集合中完成指定排序操作。

Student 初始类

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

测试类：

public class Demo {public static void main(String[] args) {// 创建四个学生对象 存储到集合中ArrayList<Student> list = new ArrayList<Student>();list.add(new Student("rose",18));list.add(new Student("jack",16));list.add(new Student("abc",16));list.add(new Student("ace",17));list.add(new Student("mark",16));/*让学生 按照年龄排序 升序*/
//        Collections.sort(list);//要求 该list中元素类型  必须实现比较器Comparable接口for (Student student : list) {System.out.println(student);}}
}

使用TreeSet对自定义对象进行排序：

import java.util.Objects;public class Student/* implements  Comparable<Student>*/{private String name;private int age;public Student() {}public Student(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}public void setAge(int age) {this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return age == student.age &&Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}/*比较规则*//* @Overridepublic int compareTo(Student o) {return  -Integer.compare(this.age,o.getAge());}*/
}

测试：

import java.util.Comparator;
import java.util.TreeSet;public class Demo7 {/*集合排序：TreeSetTreeSet() : 使用自然排序进行排序。TreeSet(Comparator<? super E> comparator):使用比较器*/public static void main(String[] args) {Student s1 = new Student("典韦", 28);Student s2 = new Student("张飞", 20);Student s3 = new Student("孙权", 17);Student s4 = new Student("刘备", 22);//使用TreeSet给自定义对象排序TreeSet<Student> treeSet = new TreeSet<>(new Comparator<Student>() {@Overridepublic int compare(Student o1, Student o2) {return -Integer.compare(o1.getAge(),o2.getAge());}});treeSet.add(s1);treeSet.add(s2);treeSet.add(s3);treeSet.add(s4);System.out.println(treeSet);}
}

发现，当我们调用Collections.sort()方法的时候程序报错了。

原因：如果想要集合中的元素完成排序，那么必须要实现比较器Comparable接口。

于是我们就完成了Student类的一个实现，如下：

public class Student implements Comparable<Student>{....@Overridepublic int compareTo(Student o) {return this.age-o.age;//升序}
}

再次测试，代码就OK 了效果如下：

Student{name='jack', age=16}
Student{name='abc', age=16}
Student{name='mark', age=16}
Student{name='ace', age=17}
Student{name='rose', age=18}

如果在使用的时候，想要独立的定义规则去使用可以采用Collections.sort(List list,Comparetor<T> c)方式，自己定义规则：

Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()-o1.getAge();//以学生的年龄降序
}
});

效果：