Java基础十七：数据结构

数据结构数据结构 存放数据的容器 数据的排列存取规则java日常开发只用两大类数组集合List、Set、Map1. 数组 Array特点长度固定一旦定义不能更改只能存储同一种数据类型基本类型/引用类型在内存中占用连续的存储空间通过索引快速访问元素属于引用类型//数据一旦初始化长度就已经定死了无法更改 public class ArrayDemo { public static void main(String[] args) { // 声明并创建长度为 3 的 int 数组 int[] arr new int[3]; // 可以赋值 arr[0] 10; arr[1] 20; arr[2] 30; // 报错数组越界因为长度固定为3不能访问索引3 // arr[3] 40; System.out.println(数组长度 arr.length); // 输出3 } } //数组是类型安全的容器只能存好定义好的类型 public class ArrayType { public static void main(String[] args) { // int 数组只能存整数 int[] nums {1,2,3}; // nums[0] Java; 报错不能存字符串 // String 数组只能存字符串 String[] names new String[2]; names[0] 张三; // names[1] 100; 报错 } } //通过数组名【索引】快速读写效率极高 public class ArrayIndex { public static void main(String[] args) { // 静态初始化 String[] fruits {苹果, 香蕉, 橙子}; // 访问索引 0 是第一个元素 System.out.println(fruits[0]); // 苹果 System.out.println(fruits[2]); // 橙子 // 修改元素 fruits[1] 葡萄; System.out.println(fruits[1]); // 葡萄 } } //创建数组时未手动赋值的元素会自动赋默认值 int → 0 double → 0.0 boolean → false 引用类型String / 对象→ null public class ArrayDefault { public static void main(String[] args) { // 只指定长度不赋值 int[] arr new int[3]; System.out.println(arr[0]); // 0 System.out.println(arr[1]); // 0 boolean[] boolArr new boolean[2]; System.out.println(boolArr[0]); // false String[] strArr new String[2]; System.out.println(strArr[0]); // null } } //数组变量是引用指向堆内存中的数组对象 public class ArrayRef { public static void main(String[] args) { // arr1 是引用指向堆内存的数组对象 int[] arr1 {10,20}; // 把引用赋值给 arr2两个引用指向同一个数组 int[] arr2 arr1; arr2[0] 100; // 修改 arr2arr1 也会变 System.out.println(arr1[0]); // 100 } } //因为长度固定用for/增强for遍历最方便 public class ArrayLoop { public static void main(String[] args) { int[] arr {1,2,3,4,5}; // 普通 for 循环通过索引 for(int i0; iarr.length; i){ System.out.print(arr[i] ); } System.out.println(); // 增强 for 循环直接取元素 for(int num : arr){ System.out.print(num ); } } }缺点长度固定不够用只能新建数组复制很麻烦 → 所以有ArrayList2. List 列表有序、可重复List 核心特点有序存入顺序和取出顺序一致可重复允许存放重复元素有索引可以通过下标0,1,2...操作元素长度可变动态扩容不用像数组一样固定长度支持泛型可以限制存放指定类型避免类型转换异常常用实现类ArrayList查询快、增删慢日常最常用LinkedList增删快、查询慢适合频繁插入删除Vector线程安全效率低基本不用常用List实现类区别类底层结构查询增删线程安全ArrayList动态数组快慢不安全LinkedList双向链表慢快不安全Vector动态数组一般慢安全开发 90% 场景直接用 ArrayList基础使用代码举例//1. 创建 List、添加元素 import java.util.ArrayList; import java.util.List; public class ListDemo1 { public static void main(String[] args) { // 泛型String只能存字符串 ListString list new ArrayList(); // 添加元素 list.add(张三); list.add(李四); list.add(王五); list.add(张三); // List允许重复 System.out.println(list); // [张三, 李四, 王五, 张三] } } //2. 常用增删改查方法 import java.util.ArrayList; import java.util.List; public class ListDemo2 { public static void main(String[] args) { ListInteger list new ArrayList(); // 1. 添加 list.add(10); list.add(20); list.add(30); System.out.println(添加后 list); // 2. 根据索引插入 list.add(1, 99); System.out.println(索引1插入99 list); // 3. 根据索引获取元素 Integer num list.get(2); System.out.println(索引2元素 num); // 4. 修改元素 list.set(2, 88); System.out.println(修改索引2 list); // 5. 根据索引删除 list.remove(1); System.out.println(删除索引1 list); // 6. 根据元素删除 list.remove(Integer.valueOf(30)); System.out.println(删除元素30 list); // 7. 获取集合大小 System.out.println(元素个数 list.size()); // 8. 判断是否包含元素 System.out.println(是否包含10 list.contains(10)); // 9. 清空集合 // list.clear(); } } //list四种遍历方式比掌握 import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class ListForEach { public static void main(String[] args) { ListString list new ArrayList(); list.add(Java); list.add(Python); list.add(C); // 方式1普通for循环带索引 System.out.println( 普通for ); for (int i 0; i list.size(); i) { System.out.println(list.get(i)); } // 方式2增强for循环最常用 System.out.println( 增强for ); for (String s : list) { System.out.println(s); } // 方式3迭代器 Iterator System.out.println( 迭代器 ); IteratorString it list.iterator(); while (it.hasNext()) { System.out.println(it.next()); } // 方式4Lambda 表达式JDK8 System.out.println( Lambda ); list.forEach(System.out::println); } } //LinkedList 特有用法 import java.util.LinkedList; public class LinkedListDemo { public static void main(String[] args) { LinkedListString link new LinkedList(); // 首尾添加 link.addFirst(第一个); link.addLast(最后一个); link.add(中间); System.out.println(link); // 获取首尾元素 System.out.println(首元素 link.getFirst()); System.out.println(尾元素 link.getLast()); // 删除首尾 link.removeFirst(); link.removeLast(); System.out.println(删除首尾后 link); } } //list存放自定义对象 import java.util.ArrayList; import java.util.List; // 自定义实体类 class User { private String name; private int age; public User(String name, int age) { this.name name; this.age age; } Override public String toString() { return User{name name , age age }; } } public class ListObject { public static void main(String[] args) { ListUser userList new ArrayList(); // 添加自定义对象 userList.add(new User(小明, 20)); userList.add(new User(小红, 18)); // 遍历 for (User user : userList) { System.out.println(user); } } }Set集合特点set是java.util下的集合接口继承collecttion三大核心特征无序存取顺序不一致部分实现类例外LinkedHashSet有序不可重复不能存储重复元素自动去重无索引没有下标不能用普通for循环根据索引遍历常用三大实现类HashSet底层哈希表无序、不重复、查询最快开发最常用LinkedHashSet底层哈希表 链表有序存取顺序一致、不重复TreeSet底层红黑树自然排序 / 自定义排序、不重复1.HashSet//1.HashSet开发最常用 //特点无序不可重复无索引 import java.util.HashSet; import java.util.Set; public class HashSetTest { public static void main(String[] args) { // 创建集合 SetString set new HashSet(); // 添加元素 set.add(张三); set.add(李四); set.add(王五); // 添加重复元素 set.add(张三); // 打印无序 自动去重 System.out.println(set); } } //打印结果为[李四, 张三, 王五] //HashSet 常用方法 import java.util.HashSet; import java.util.Set; public class HashSetMethod { public static void main(String[] args) { SetInteger set new HashSet(); // 添加 set.add(10); set.add(20); set.add(10); // 重复无效 // 集合元素个数 System.out.println(元素个数 set.size()); // 判断是否包含某个元素 System.out.println(是否包含20 set.contains(20)); // 删除元素 set.remove(10); System.out.println(删除后 set); // 判断是否为空 System.out.println(是否为空 set.isEmpty()); // 清空所有元素 // set.clear(); } } //Set遍历方式 import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class SetForeach { public static void main(String[] args) { SetString set new HashSet(); set.add(Java); set.add(MySQL); set.add(Vue); // 1. 增强for循环最常用 for (String s : set) { System.out.println(s); } System.out.println(--------); // 2. 迭代器遍历 IteratorString it set.iterator(); while (it.hasNext()) { System.out.println(it.next()); } System.out.println(--------); // 3. Lambda 遍历JDK8 set.forEach(System.out::println); } }2.LinkedHashSet特点保留添加顺序不可重复适合既要去重又要保证存入顺序和取出顺序一致import java.util.LinkedHashSet; import java.util.Set; public class LinkedHashSetTest { public static void main(String[] args) { SetString set new LinkedHashSet(); set.add(苹果); set.add(香蕉); set.add(橙子); set.add(苹果); // 重复自动忽略 // 输出顺序 添加顺序 System.out.println(set); } } //输出 [苹果, 香蕉, 橙子]3.TreeSet 自动排序集合特点不重复默认升序排序import java.util.TreeSet; import java.util.Set; public class TreeSetTest { public static void main(String[] args) { SetInteger set new TreeSet(); set.add(5); set.add(1); set.add(9); set.add(1); // 自动从小到大排序 System.out.println(set); } } //输出[1, 5, 9]Map 键值对特点键唯一值可重复通过key快速找value无索引不能用普通for循环遍历开发用得最多接口传参存配置字典下拉选项常用实现类HashMap无序、键唯一、效率最高日常最常用LinkedHashMap有序、键唯一TreeMap按键自动排序实现类特点HashMap存取无序、键不重复、效率高LinkedHashMap存取有序、键不重复TreeMap按键自然排序、键不重复HashMap//map基础使用增删改查 import java.util.HashMap; import java.util.Map; public class MapDemo1 { public static void main(String[] args) { // Map键类型, 值类型 MapString, Integer map new HashMap(); // 1. 添加键值对 put(key,value) map.put(张三, 20); map.put(李四, 22); map.put(王五, 19); // 键重复会覆盖原来的值 map.put(张三, 25); // 打印整个Map System.out.println(map); // 2. 根据键获取值 get(key) Integer age map.get(李四); System.out.println(李四年龄 age); // 3. 根据键删除键值对 remove(key) map.remove(王五); System.out.println(删除王五后 map); // 4. 判断是否包含指定键 / 值 System.out.println(是否包含键 张三 map.containsKey(张三)); System.out.println(是否包含值 22 map.containsValue(22)); // 5. 获取键值对个数 System.out.println(元素个数 map.size()); // 6. 清空集合 // map.clear(); // 7. 判断是否为空 System.out.println(是否为空 map.isEmpty()); } } //Map三种遍历方式(必掌握) //方式1先获取所有键再通过键取值 import java.util.HashMap; import java.util.Map; import java.util.Set; public class MapLoop1 { public static void main(String[] args) { MapString, Integer map new HashMap(); map.put(Java, 80); map.put(Python, 90); map.put(C, 70); // 获取所有键放到 Set 集合 SetString keySet map.keySet(); // 遍历所有键 for (String key : keySet) { // 通过键拿值 Integer value map.get(key); System.out.println(key value); } } } //方式2:键值对对象遍历推荐 import java.util.HashMap; import java.util.Map; import java.util.Set; public class MapLoop2 { public static void main(String[] args) { MapString, Integer map new HashMap(); map.put(语文, 95); map.put(数学, 98); map.put(英语, 92); // 获取所有键值对对象 SetMap.EntryString, Integer entrySet map.entrySet(); for (Map.EntryString, Integer entry : entrySet) { String key entry.getKey(); Integer value entry.getValue(); System.out.println(key : value); } } } //Lambda 遍历JDK8 简洁写法 import java.util.HashMap; import java.util.Map; public class MapLoop3 { public static void main(String[] args) { MapString, String map new HashMap(); map.put(001, 小明); map.put(002, 小红); // 一行遍历 map.forEach((k, v) - System.out.println(k - v)); } }LinkedHashMap保留添加顺序键不重复import java.util.LinkedHashMap; import java.util.Map; public class LinkedHashMapDemo { public static void main(String[] args) { MapString, Integer map new LinkedHashMap(); map.put(A, 1); map.put(B, 2); map.put(C, 3); // 输出顺序和添加顺序一致 System.out.println(map); } }TreeMap按键默认升序排列import java.util.TreeMap; import java.util.Map; public class TreeMapDemo { public static void main(String[] args) { MapString, Integer map new TreeMap(); map.put(b, 2); map.put(a, 1); map.put(c, 3); // 按键字典顺序自动排序 System.out.println(map); } }Map 存储自定义对象示例import java.util.HashMap; import java.util.Map; class User { private String name; private int age; public User(String name, int age) { this.name name; this.age age; } Override public String toString() { return User{name name , age age }; } } public class MapUserDemo { public static void main(String[] args) { MapString, User userMap new HashMap(); userMap.put(user1, new User(张三, 20)); userMap.put(user2, new User(李四, 22)); // 遍历 userMap.forEach((k, v) - System.out.println(k : v)); } }链表 LinkedList由一个个节点连起来每个节点存【数据 下一个节点地址】内存不连续不用固定长度插入删除极快。数组内存连续靠下标访问。链表内存不连续每个节点存数据下一个节点地址常见链表分类单向链表只能从头往后走双向链表可以向前、向后遍历JavaLinkedList就是双向链表循环链表最后一个节点指向头节点特性数组链表内存连续不连续查询快按索引 O (1)慢从头遍历 O (n)增删慢要移动元素快只改引用指向长度固定不可变动态不限长度浪费空间可能浪费每个节点多占指针空间一句话查多用数组 / ArrayList频繁增删用链表 / LinkedList//基本使用代码 import java.util.LinkedList; public class LinkTest { public static void main(String[] args) { // 创建链表 LinkedListString list new LinkedList(); // 普通添加 list.add(A); list.add(B); list.add(C); // 头部、尾部添加 list.addFirst(开头); list.addLast(结尾); System.out.println(list); // 获取首尾 System.out.println(第一个 list.getFirst()); System.out.println(最后一个 list.getLast()); // 删除首尾 list.removeFirst(); list.removeLast(); System.out.println(操作后 list); } } //常用方法 add() // 尾部加 addFirst() // 头部加 addLast() // 尾部加 getFirst() // 拿第一个 getLast() // 拿最后一个 removeFirst() // 删第一个 removeLast() // 删最后一个 size() // 元素个数 //遍历链表 // 增强for遍历 for (String s : list) { System.out.println(s); }栈 Stack / 队列 Queue栈 Stack特点最后进去的最先出来常用场景函数调用递归括号匹配浏览器后退撤销操作。import java.util.LinkedList; // 用 LinkedList 当栈用 public class StackDemo { public static void main(String[] args) { LinkedListString stack new LinkedList(); // 入栈压栈 stack.push(第1个); stack.push(第2个); stack.push(第3个); System.out.println(stack); // 出栈后进先出 System.out.println(stack.pop()); // 第3个 System.out.println(stack.pop()); // 第2个 // 查看栈顶元素不删除 System.out.println(stack.peek()); // 第1个 } }队列先进先出import java.util.Queue; import java.util.LinkedList; public class QueueDemo { public static void main(String[] args) { QueueString queue new LinkedList(); queue.offer(一号); queue.offer(二号); System.out.println(queue.poll()); // 先出一号 } }