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集合对象 ListString list new ArrayListString(); // 往 尾部添加 指定元素 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;ilist.size();i){ System.out.println(list.get(i)); } //还可以使用增强for for (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) { LinkedListString link new LinkedListString(); //添加元素 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集合 HashSetString set new HashSetString(); //添加元素 set.add(new String(cba)); set.add(abc); set.add(bac); set.add(cba); //遍历 for (String name : set) { System.out.println(name); } } }输出结果如下说明集合中不能存储重复元素cbaabcbac4.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; } Override public 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); } Override public int hashCode() { return Objects.hash(name, age); } Override public String toString() { return Student{ name name \ , age age }; } }public class HashSetDemo2 { public static void main(String[] args) { //创建集合对象 该集合中存储 Student类型对象 HashSetStudent stuSet new HashSetStudent(); //存储 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郭德纲, age44] Student [name于谦, age43] Student [name郭麒麟, age23]4.4LinkedHashSet我们知道HashSet保证元素唯一可是元素存放进去是没有顺序的那么我们要保证有序怎么办呢在HashSet下面有一个子类java.util.LinkedHashSet它是链表和哈希表组合的一个数据存储结构。演示代码如下:public class LinkedHashSetDemo { public static void main(String[] args) { SetString set new LinkedHashSetString(); set.add(bbb); set.add(aaa); set.add(abc); set.add(bbc); IteratorString it set.iterator(); while (it.hasNext()) { System.out.println(it.next()); } } } 结果 bbb aaa abc bbc4.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 2121 int 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; } }五、Collections5.1常用功能java.utils.Collections是集合工具类用来对集合进行操作。部分方法如下public static T boolean addAll(CollectionT c, T... elements):往集合中添加一些元素。public static void shuffle(List? list) 打乱顺序:打乱集合顺序。public static T void sort(ListT list):将集合中元素按照默认规则排序。public static T void sort(ListT listComparator? super T ):将集合中元素按照指定规则排序。代码演示public class CollectionsDemo { public static void main(String[] args) { ArrayListInteger list new ArrayListInteger(); //原来写法 //list.add(12); //list.add(14); //list.add(15); //list.add(1000); //采用工具类 完成 往集合中添加元素 Collections.addAll(list, 5, 222, 12); System.out.println(list); //排序方法 Collections.sort(list); System.out.println(list); } } 结果 [5, 222, 1, 2] [1, 2, 5, 222]代码演示之后 发现我们的集合按照顺序进行了排列可是这样的顺序是采用默认的顺序如果想要指定顺序那该怎么办呢我们发现还有个方法没有讲public static T void sort(ListT listComparator? super T ):将集合中元素按照指定规则排序。接下来讲解一下指定规则的排列5.2Comparator比较器我们还是先研究这个方法public static T void sort(ListT list):将集合中元素按照默认规则排序。不过这次存储的是字符串类型。public class CollectionsDemo2 { public static void main(String[] args) { ArrayListString list new ArrayListString(); 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(ListT list)这个方法完成的排序实际上要求了被排序的类型需要实现Comparable接口完成比较的功能在String类型上如下public final class String implements java.io.Serializable, ComparableString, CharSequence {String类实现了这个接口并完成了比较规则的定义但是这样就把这种规则写死了那比如我想要字符串按照第一个字符降序排列那么这样就要修改String的源代码这是不可能的了那么这个时候我们可以使用public static T void sort(ListT listComparator? super T )方法灵活的完成这个里面就涉及到了Comparator这个接口位于位于java.util包下排序是comparator能实现的功能之一,该接口代表一个比较器比较器具有可比性顾名思义就是做排序的通俗地讲需要比较两个对象谁排在前谁排在后那么比较的方法就是public int compare(String o1, String o2)比较其两个参数的顺序。两个对象比较的结果有三种大于等于小于。如果要按照升序排序 则o1 小于o2返回负数相等返回001大于02返回正数 如果要按照降序排序 则o1 小于o2返回正数相等返回001大于02返回负数例public class CollectionsDemo3 { public static void main(String[] args) { ArrayListString list new ArrayListString(); list.add(cba); list.add(aba); list.add(sba); list.add(nba); //排序方法 按照第一个单词的降序 Collections.sort(list, new ComparatorString() { Override public 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; } Override public String toString() { return Student{ name name \ , age age }; } }测试类public class Demo { public static void main(String[] args) { // 创建四个学生对象 存储到集合中 ArrayListStudent list new ArrayListStudent(); 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 ComparableStudent*/{ 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; } Override public 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); } Override public int hashCode() { return Objects.hash(name, age); } Override public String toString() { return Student{ name name \ , age age }; } /* 比较规则 */ /* Override public int compareTo(Student o) { return -Integer.compare(this.age,o.getAge()); }*/ }测试import java.util.Comparator; import java.util.TreeSet; public class Demo7 { /* 集合排序TreeSet TreeSet() : 使用自然排序进行排序。 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给自定义对象排序 TreeSetStudent treeSet new TreeSet(new ComparatorStudent() { Override public 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 ComparableStudent{ .... Override public int compareTo(Student o) { return this.age-o.age;//升序 } }再次测试代码就OK 了效果如下Student{namejack, age16}Student{nameabc, age16}Student{namemark, age16}Student{nameace, age17}Student{namerose, age18}如果在使用的时候想要独立的定义规则去使用 可以采用Collections.sort(List list,ComparetorT c)方式自己定义规则Collections.sort(list, new ComparatorStudent() {Overridepublic int compare(Student o1, Student o2) {return o2.getAge()-o1.getAge();//以学生的年龄降序}});效果Student{namerose, age18}Student{nameace, age17}Student{namejack, age16}Student{nameabc, age16}Student{namemark, age16}