java学习笔记——集合

一、集合概述1.1 为什么需要集合数组的局限性长度固定不能动态改变只能存储同一种类型的数据增删操作不方便集合的优势长度可变自动扩容提供丰富的操作方法增删改查、排序等支持多种数据结构链表、树、哈希表等1.2 集合的分类单列集合Collection一次存一个元素双列集合Map一次存一对元素键值对二、Collection接口Collection 常用方法import java.util.ArrayList; import java.util.Collection; CollectionString coll new ArrayList(); // 1. 添加元素 coll.add(张三); coll.add(李四); coll.add(王五); System.out.println(coll); // [张三, 李四, 王五] // 2. 删除元素 coll.remove(李四); // 删除指定元素 System.out.println(coll); // [张三, 王五] // 3. 判断 System.out.println(coll.contains(张三)); // true System.out.println(coll.isEmpty()); // false // 4. 获取长度 System.out.println(coll.size()); // 2 // 5. 清空 coll.clear(); System.out.println(coll.isEmpty()); // true // 6. 转数组 coll.add(A); coll.add(B); Object[] arr coll.toArray(); String[] strArr coll.toArray(new String[0]);三、迭代器3.1定义迭代器是遍历集合的通用工具不依赖索引。3.2 基本使用import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; CollectionString coll new ArrayList(); coll.add(A); coll.add(B); coll.add(C); // 1. 获取迭代器 IteratorString it coll.iterator(); // 2. 遍历 while (it.hasNext()) { // 判断是否有下一个元素 String s it.next(); // 获取下一个元素 System.out.println(s); }3.3 迭代过程原理3.4 迭代中删除元素// 使用迭代器的 remove() 方法不能用集合的 remove() IteratorString it coll.iterator(); while (it.hasNext()) { String s it.next(); if (B.equals(s)) { it.remove(); // 正确用迭代器的remove // coll.remove(B); // 错误会抛出ConcurrentModificationException } }3.5 迭代器源码分析// ArrayList 内部类 Itr 简化版 private class Itr implements IteratorE { int cursor; // 下一个要返回元素的索引 int expectedModCount modCount; // 期望的修改次数 public boolean hasNext() { return cursor ! size; // cursor不等于size说明还有元素 } public E next() { checkForComodification(); // 检查并发修改 int i cursor; E element elementData[i]; cursor i 1; return element; } // 检查是否在迭代中使用了集合的增删方法 final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); } }ps:为什么集合的remove会报错集合有个 modCount 记录修改次数迭代器记录 expectedModCount集合的remove会修改 modCount导致两者不一致 → 抛异常迭代器的remove会同步更新两者所以安全四、数据结构基础4.1 常见数据结构4.2 数组 vs 链表数组链表五、ArrayList集合5.1 基本使用import java.util.ArrayList; ArrayListString list new ArrayList(); // 增 list.add(张三); list.add(李四); list.add(1, 王五); // 在索引1处插入 System.out.println(list); // [张三, 王五, 李四] // 删 list.remove(1); // 按索引删除 list.remove(李四); // 按元素删除 // 改 list.set(0, 张三丰); // 修改指定索引的元素 // 查 String s list.get(0); // 按索引查询 int index list.indexOf(张三丰); // 查找元素索引 boolean has list.contains(张三丰); // 是否包含5.2 遍历方式ArrayListString list new ArrayList(); list.add(A); list.add(B); list.add(C); // 方式1普通for循环 for (int i 0; i list.size(); i) { System.out.println(list.get(i)); } // 方式2增强for循环 for (String s : list) { System.out.println(s); } // 方式3迭代器 IteratorString it list.iterator(); while (it.hasNext()) { System.out.println(it.next()); } // 方式4forEachJDK8 list.forEach(s - System.out.println(s));5.3 ArrayList源码分析// ArrayList 底层是 Object[] 数组 public class ArrayListE { private Object[] elementData; // 存储元素的数组 private int size; // 实际元素个数 // 空参构造初始为空数组 public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // {} } // add 方法 public boolean add(E e) { ensureCapacityInternal(size 1); // 检查容量不够就扩容 elementData[size] e; // 添加元素size1 return true; } // 扩容机制 private void grow(int minCapacity) { int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍扩容 elementData Arrays.copyOf(elementData, newCapacity); } }核心要点底层结构Object[] 数组初始容量JDK7 空参构造初始为空数组第一次add时扩容为10扩容机制每次扩容为原来的 1.5倍查询快O(1)通过索引直接定位增删慢O(n)需要移动元素六、LinkedList集合6.1 基本使用import java.util.LinkedList; LinkedListString list new LinkedList(); // 基本操作同ArrayList list.add(A); list.add(B); list.addFirst(开头); // 头部添加LinkedList特有 list.addLast(结尾); // 尾部添加LinkedList特有 // 获取 String first list.getFirst(); String last list.getLast(); // 删除 list.removeFirst(); list.removeLast(); // 模拟栈和队列 list.push(入栈); // 压栈 String pop list.pop(); // 弹栈 list.offer(入队); // 入队 String poll list.poll(); // 出队6.2 LinkedList特有方法6.3 LinkedList源码分析// LinkedList 底层是双向链表 public class LinkedListE { private NodeE first; // 头节点 private NodeE last; // 尾节点 private int size; // 元素个数 // 内部类链表节点 private static class NodeE { E item; // 存储的数据 NodeE next; // 下一个节点 NodeE prev; // 上一个节点 Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } } // add方法尾部添加 public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { NodeE l last; NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; } }核心要点底层结构双向链表查询慢O(n)需要从头/尾遍历增删快O(1)只需修改前后节点的指针实现了 Deque 接口可以当栈或队列使用6.4 ArrayList vs LinkedList七、增强for循环7.1 语法for (元素类型 变量名 : 数组或集合) { // 使用变量名 }7.2 基本使用// 遍历数组 int[] arr {1, 2, 3, 4, 5}; for (int num : arr) { System.out.println(num); } // 遍历集合 ArrayListString list new ArrayList(); list.add(A); list.add(B); for (String s : list) { System.out.println(s); }7.3 注意事项// 增强for不能修改原数组/集合 int[] arr {1, 2, 3}; for (int num : arr) { num 100; // 只改了临时变量num不影响arr } System.out.println(arr[0]); // 1没变 // 要修改元素用普通for for (int i 0; i arr.length; i) { arr[i] 100; // 直接修改数组元素 }7.4 增强for底层原理增强for遍历集合时底层是迭代器// 增强for for (String s : list) { System.out.println(s); } // 等价于 IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); System.out.println(s); }