集合重点: 1.知道集合的特点以及作用 2.会使用Collection接口中的方法 3.会使用迭代器迭代集合 4.会ArrayList以及LinkedList的使用 5.会使用增强for遍历集合第一章.集合框架(单列集合)1.之前我们学了保存数据的有:变量,数组,但是数组定长,所以如果添加一个数据或者删除一个数据,数组并不好使,需要创建新数组,所以接下来我们学一个长度可变的容器,集合 2.集合的特点 a.只能存储引用数据类型的数据 b.长度可变 c.集合中有大量的方法,方便我们操作 3.分类: a.单列集合:一个元素就一个组成部分: list.add(张三) b.双列集合:一个元素有两部分构成: key 和 value map.put(涛哥,金莲) - key,value叫做键值对第二章.Collection接口1.概述:单列集合的顶级接口 2.使用: a.创建: CollectionE 对象名 new 实现类对象E() 采用多态进行实现更加灵活 b.E:泛型,决定了集合中能存储什么类型的数据,可以统一元素类型 泛型中只能写引用数据类型,如果不写,默认Object类型,此时什么类型的数据都可以存储了 int 不行 Integer 行 Person 行 c.泛型细节: 我们等号前面的泛型必须写,等号后面的泛型可以不写,jvm会根据前面的泛型推导出后面的泛型是啥 3.常用方法: boolean add(E e) : 将给定的元素添加到当前集合中(我们一般调add时,不用boolean接收,因为add一定会成功) boolean addAll(Collection? extends E c) :将另一个集合元素添加到当前集合中 (集合合并) void clear():清除集合中所有的元素 boolean contains(Object o) :判断当前集合中是否包含指定的元素 boolean isEmpty() : 判断当前集合中是否有元素-判断集合是否为空 boolean remove(Object o):将指定的元素从集合中删除 int size() :返回集合中的元素个数。 Object[] toArray(): 把集合中的元素,存储到数组中public class Demo01Collection { public static void main(String[] args) { CollectionString collection new ArrayList(); //boolean add(E e) : 将给定的元素添加到当前集合中(我们一般调add时,不用boolean接收,因为add一定会成功) collection.add(萧炎); collection.add(萧薰儿); collection.add(彩鳞); collection.add(小医仙); collection.add(云韵); collection.add(涛哥); System.out.println(collection); //boolean addAll(Collection? extends E c) :将另一个集合元素添加到当前集合中 (集合合并) CollectionString collection1 new ArrayList(); collection1.add(张无忌); collection1.add(小昭); collection1.add(赵敏); collection1.add(周芷若); collection1.addAll(collection); System.out.println(collection1); //void clear():清除集合中所有的元素 collection1.clear(); System.out.println(collection1); //boolean contains(Object o) :判断当前集合中是否包含指定的元素 boolean result01 collection.contains(涛哥); System.out.println(result01 result01); //boolean isEmpty() : 判断当前集合中是否有元素-判断集合是否为空 System.out.println(collection1.isEmpty()); //boolean remove(Object o):将指定的元素从集合中删除 collection.remove(涛哥); System.out.println(collection); //int size() :返回集合中的元素个数。 System.out.println(collection.size()); //Object[] toArray(): 把集合中的元素,存储到数组中 Object[] arr collection.toArray(); System.out.println(Arrays.toString(arr)); } }第三章.迭代器1.迭代器基本使用1.概述:Iterator接口 2.主要作用:遍历集合 3.获取:Collection中的方法: IteratorE iterator() 4.方法: boolean hasNext() - 判断集合中有没有下一个元素 E next() -获取下一个元素public class Demo01Iterator { public static void main(String[] args) { ArrayListString list new ArrayList(); list.add(楚雨荨); list.add(慕容云海); list.add(端木磊); list.add(上官瑞谦); list.add(叶烁); //获取迭代器对象 IteratorString iterator list.iterator(); while(iterator.hasNext()){ String element iterator.next(); System.out.println(element); } } }注意:next方法在获取的时候不要连续使用多次public class Demo02Iterator { public static void main(String[] args) { ArrayListString list new ArrayList(); list.add(楚雨荨); list.add(慕容云海); list.add(端木磊); list.add(上官瑞谦); list.add(叶烁); //获取迭代器对象 IteratorString iterator list.iterator(); while(iterator.hasNext()){ String element iterator.next(); System.out.println(element); //String element2 iterator.next(); //System.out.println(element2); } } }NoSuchElementException:没有可操作的元素异常2.迭代器迭代过程int cursor; //下一个元素索引位置 int lastRet -1;//上一个元素索引位置 索引移动首先先利用hasNext判断有没有下一个元素有:cusor i 1,lastRet i;没有则结束。过程如下1、hasNext:2、next():3、直至4、此时cursor 5则结束。3.迭代器底层原理1.获取Iterator的时候怎么获取的: Iterator iterator list.iterator() 我们知道Iterator是一个接口,等号右边一定是它的实现类对象 问题:Iterator接收的到底是哪个实现类对象呢? - ArrayList中的内部类Itr对象总结对于ArrayList集合list.iterator()返回一个Iterator的实现类然后ArrayList定义了一个内部类去实现这个接口实现里面具体的方法。注意只有ArrayList使用迭代器的时候Iterator接口才会指向Itr,其他的集合使用迭代器Iterator就指向的不是Itr了HashSetString set new HashSet(); IteratorString iterator1 set.iterator();4.并发修改异常需求:定义一个集合,存储 唐僧,孙悟空,猪八戒,沙僧,遍历集合,如果遍历到猪八戒,往集合中添加一个白龙马public class Demo03Iterator { public static void main(String[] args) { //需求:定义一个集合,存储 唐僧,孙悟空,猪八戒,沙僧,遍历集合,如果遍历到猪八戒,往集合中添加一个白龙马 ArrayListString list new ArrayList(); list.add(唐僧); list.add(孙悟空); list.add(猪八戒); list.add(沙僧); IteratorString iterator list.iterator(); while(iterator.hasNext()){ String element iterator.next(); if (猪八戒.equals(element)){ list.add(白龙马); } } System.out.println(list); } }String element iterator.next(); private class Itr implements IteratorE { int cursor; // index of next element to return int lastRet -1; // index of last element returned; -1 if no such /* modCount: 实际操作次数 expectedModCount:预期操作次数 */ int expectedModCount modCount; SuppressWarnings(unchecked) public E next() { checkForComodification(); } final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); } }结论:当预期操作次数和实际操作次数不相等了,会出现并发修改异常提问我们干了什么事儿,让实际操作次数和预期操作次数不相等了list.add(白龙马) public boolean add(E e) { modCount;//实际操作次数1 } 最终结论:我们调用了add方法,而add方法底层只给modCount,但是再次调用next方法的时候,并没有给修改后的modCount重新赋值给expectedModCount,导致next方法底层的判断判断出实际操作次数和预期操作次数不相等了,所以抛出了并发修改异常原因如下为了在并发或单线程中错误地修改集合时尽早发现并抛出异常避免程序在错误的数据上继续运行导致更隐蔽、更难排查的问题。主要场景防止“不可预测的行为”想象一下如果没有这个检查你在遍历一个ArrayList的同时又通过list.add()或list.remove()修改了它的结构长度变了会发生什么索引错乱迭代器内部维护着一个cursor下一个要返回元素的索引。你正遍历到第3个元素时突然在前面插入了一个新元素那么原来的第4、5个元素的索引就变成了5、6。迭代器按原计划取第4个元素时实际上取到的是原来的第3个元素导致元素被重复访问或完全遗漏。越界异常如果你删除的是最后一个元素迭代器可能访问到一个已经被删除的、无效的索引位置抛出IndexOutOfBoundsException。无限循环某些修改方式甚至可能导致迭代永远无法结束。这些错误都非常隐蔽产生的错误数据或异常比如越界可能发生在很晚之后离真正的错误修改代码很远调试起来极其痛苦。2. 并发场景的警示虽然ArrayList本身不是线程安全的但即使在单线程中上面的错误也容易发生。在多线程下就更危险了一个线程在遍历另一个线程同时在add。如果没有fail-fast你可能会得到一团乱的数据而没有任何报错仿佛程序正常执行了但计算结果全是错的。“快速失败”的理念就是宁愿程序立刻崩溃也绝不在错误的状态下继续运行。但是我们可以通过迭代器自己的remove、set或add方法修改集合是不会抛出异常的。这是因为迭代器的这些方法在修改集合后会主动重新同步expectedModCount和modCount执行expectedModCount modCount。这意味着迭代器完全知道自己做了什么修改并能正确调整内部游标保证后续遍历依然正确。ArrayList中的方法:ListIterator listIterator()public class Demo03Iterator { public static void main(String[] args) { //需求:定义一个集合,存储 唐僧,孙悟空,猪八戒,沙僧,遍历集合,如果遍历到猪八戒,往集合中添加一个白龙马 ArrayListString list new ArrayList(); list.add(唐僧); list.add(孙悟空); list.add(猪八戒); list.add(沙僧); //IteratorString iterator list.iterator(); ListIteratorString listIterator list.listIterator(); while(listIterator.hasNext()){ String element listIterator.next(); if (猪八戒.equals(element)){ listIterator.add(白龙马); } } System.out.println(list); } }使用迭代器迭代集合的过程中,不要随意修改集合长度,容易出现并发修改异常。第四章.数据结构数据结构是一种具有一定逻辑关系在计算机中应用某种存储结构并且封装了相应操作的数据元素集合。它包含三方面的内容逻辑关系、存储关系及操作。为什么需要数据结构随着应用程序变得越来越复杂和数据越来越丰富几百万、几十亿甚至几百亿的数据就会出现而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢数据结构就是用来解 决这些问题的。数据的逻辑结构指反映数据元素之间的逻辑关系而与他们在计算机中的存储位置无关集合数学中集合的概念数据结构中的元素之间除了“同属一个集合” 的相互关系外别无其他关系线性结构数据结构中的元素存在一对一的相互关系树形结构数据结构中的元素存在一对多的相互关系图形结构数据结构中的元素存在多对多的相互关系。数据的物理结构/存储结构是描述数据具体在内存中的存储如顺序结构、链式结构、索引结构、哈希结构等一种数据逻辑结构可表示成一种或多种物理存储结构。数据结构是一门完整并且复杂的课程那么我们今天只是简单的讨论常见的几种数据结构让我们对数据结构与算法有一个初步的了解。1.栈1.特点: 先进后出 2.好比:手枪压子弹2.队列1.特点:先进先出 2.好比:过安检3.数组1.特点:查询快,增删慢 2.查询快:因为有索引,我们可以直接通过索引操作元素 增删慢:因为数组定长 a.添加元素:创建新数组,将老数组中的元素复制到新数组中去,在最后添加新元素;要是从中间插入就更麻烦了 插入完新元素,后面的元素都要往后移动 b.删除元素:创建新数组,将老数组中的元素复制到新数组中去,被删除的元素就不复制了;如果要是从之间删除 被删除的元素后面的元素都要往前移动4.链表1.在集合中涉及到了两种链表 2.单向链表 a.节点:一个节点分为两部分 第一部分:数据域(存数据) 第二部分:指针域(保存下一个节点地址) b.特点:前面节点记录后面节点的地址,但是后面节点地址不记录前面节点地址 3.双向链表: a.节点:一个节点分为三部分 第一部分:指针域(保存上一个节点地址) 第二部分:数据域(保存的数据) 第三部分:指针域(保存下一个节点地址) b.特点: 前面节点记录后面节点地址,后面节点也记录前面节点地址 4.链表结构特点:查询慢,增删快4.1单向链表a.节点:一个节点分为两部分 第一部分:数据域(存数据) 第二部分:指针域(保存下一个节点地址) b.特点:前面节点记录后面节点的地址,但是后面节点地址不记录前面节点地址4.2双向链表a.节点:一个节点分为三部分 第一部分:指针域(保存上一个节点地址) 第二部分:数据域(保存的数据) 第三部分:指针域(保存下一个节点地址) b.特点: 前面节点记录后面节点地址,后面节点也记录前面节点地址第五章.List接口1.概述:是Collection接口的子接口 2.常见的实现类: ArrayList LinkedList Vector第六章.List集合下的实现类1.ArrayList集合1.概述:ArrayList是List接口的实现类 2.特点: a.元素有序- 按照什么顺序存的,就按照什么顺序取 b.元素可重复 c.有索引- 可以利用索引去操作元素 d.线程不安全 3.数据结构:数组 4.常用方法: boolean add(E e) - 将元素添加到集合中-尾部(add方法一定能添加成功的,所以我们不用boolean接收返回值) void add(int index, E element) -在指定索引位置上添加元素 boolean remove(Object o) -删除指定的元素,删除成功为true,失败为false E remove(int index) - 删除指定索引位置上的元素,返回的是被删除的那个元素 E set(int index, E element) - 将指定索引位置上的元素,修改成后面的element元素 E get(int index) - 根据索引获取元素 int size() - 获取集合元素个数1.1.ArrayList集合使用方法public class Demo01ArrayList { public static void main(String[] args) { ArrayListString list new ArrayList(); //boolean add(E e) - 将元素添加到集合中-尾部(add方法一定能添加成功的,所以我们不用boolean接收返回值) list.add(铁胆火车侠); list.add(喜洋洋); list.add(火影忍者); list.add(灌篮高手); list.add(网球王子); System.out.println(list); //void add(int index, E element) -在指定索引位置上添加元素 list.add(2,涛哥); System.out.println(list); //boolean remove(Object o) -删除指定的元素,删除成功为true,失败为false list.remove(涛哥); System.out.println(list); //E remove(int index) - 删除指定索引位置上的元素,返回的是被删除的那个元素 String element list.remove(0); System.out.println(element); System.out.println(list); //E set(int index, E element) - 将指定索引位置上的元素,修改成后面的element元素 String element2 list.set(0, 金莲); System.out.println(element2); System.out.println(list); //E get(int index) - 根据索引获取元素 System.out.println(list.get(0)); //int size() - 获取集合元素个数 System.out.println(list.size()); } }public class Demo02ArrayList { public static void main(String[] args) { ArrayListString list new ArrayList(); list.add(铁胆火车侠); list.add(喜洋洋); list.add(火影忍者); list.add(灌篮高手); list.add(网球王子); IteratorString iterator list.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } System.out.println(); for (int i 0;ilist.size();i){ System.out.println(list.get(i)); } System.out.println(); /* 遍历带有索引集合的快捷键 集合名.fori */ for (int i 0; i list.size(); i) { System.out.println(list.get(i)); } } }public class Demo03ArrayList { public static void main(String[] args) { ArrayListInteger list new ArrayList(); list.add(2); System.out.println(list); /* 需求:删除2 remove(Object o) - 直接删除指定元素 remove(int index) - 删除指定索引位置上的元素 如果remove中直接传递整数,默认调用按照指定索引删除元素的remove 但是此时list中没有2索引,所以越界 解决:我们可以将2包装成包装类,变成包装类之后,其父类就是Object了, */ //list.remove(2); list.remove(Integer.valueOf(2)); System.out.println(list); } }1.2.底层源码分析1.ArrayList构造方法: a.ArrayList() 构造一个初始容量为十的空列表 b.ArrayList(int initialCapacity) 构造具有指定初始容量的空列表 2.ArrayList源码总结: a.不是一new底层就会创建初始容量为10的空列表,而是第一次add的时候才会创建初始化容量为10的空列表 b.ArrayList底层是数组,那么为啥还说集合长度可变呢? ArrayList底层会自动扩容- Arrays.copyOf就是容量不够了选择一个新的大的数组进行复制数据后返回地址 c.扩容多少倍? 1.5倍ArrayList() 构造一个初始容量为十的空列表 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; Object[] elementData; -ArrayList底层的那个数组 public ArrayList() { this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } list.add(a); public boolean add(E e) { modCount; add(e, elementData, size);// e-要存的元素 elementData-集合数组,长度开始为0,size-0 return true; } private void add(E e-元素, Object[] elementData-集合数组, int s-0) { if (s elementData.length) elementData grow(); elementData[s] e; size s 1; } private Object[] grow() { return grow(size 1); } private Object[] grow(int minCapacity-1) { int oldCapacity elementData.length;//0 if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, /* minimum growth */ oldCapacity 1 /* preferred growth */); return elementData Arrays.copyOf(elementData, newCapacity); } else { return elementData new Object[Math.max(DEFAULT_CAPACITY-10, minCapacity-1)]; } } 假设ArrayList中存了第11个元素,会自动扩容- Arrays.copyOf private Object[] grow(int minCapacity) {//11 int oldCapacity elementData.length;//10 if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity(15) ArraysSupport.newLength(oldCapacity-10, minCapacity - oldCapacity-1, /* minimum growth */ oldCapacity 1 -5 /* preferred growth */); return elementData Arrays.copyOf(elementData, newCapacity); } else { return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)]; } } public static int newLength(int oldLength-10, int minGrowth-1, int prefGrowth-5) { // preconditions not checked because of inlining // assert oldLength 0 // assert minGrowth 0 int prefLength oldLength Math.max(minGrowth, prefGrowth); // 15 if (0 prefLength prefLength SOFT_MAX_ARRAY_LENGTH) { return prefLength; } else { // put code cold in a separate method return hugeLength(oldLength, minGrowth); } }ArrayList(int initialCapacity) 构造具有指定初始容量的空列表ArrayListString list new ArrayList(5); public ArrayList(int initialCapacity-5) { if (initialCapacity 0) { this.elementData new Object[initialCapacity];//直接创建长度为5的数组 } else if (initialCapacity 0) { this.elementData EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException(Illegal Capacity: initialCapacity); } }ArrayList list new ArrayList() - 现在我们想用都是new但是将来开发不会想使用就new集合,都是调用一个方法,查询出很多数据来,此方法返回一个集合,自动将查询出来的数据放到集合中,我们想在页面上展示数据,遍历集合而且将来调用方法,返回的集合类型,一般都是接口类型List泛型 list 对象.查询方法()第七章.LinkedList集合1.概述:LinkedList是List接口的实现类 2.特点: a.元素有序 b.元素可重复 c.有索引 - 这里说的有索引仅仅指的是有操作索引的方法,不代表本质上具有索引 d.线程不安全 3.数据结构:双向链表 4.方法:有大量直接操作首尾元素的方法 - public 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。public class Demo05LinkedList { public static void main(String[] args) { LinkedListString linkedList new LinkedList(); linkedList.add(吕布); linkedList.add(刘备); linkedList.add(关羽); linkedList.add(张飞); linkedList.add(貂蝉); System.out.println(linkedList); linkedList.addFirst(孙尚香); System.out.println(linkedList); linkedList.addLast(董卓); System.out.println(linkedList); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); linkedList.removeFirst(); System.out.println(linkedList); linkedList.removeLast(); System.out.println(linkedList); System.out.println(); IteratorString iterator linkedList.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } System.out.println(); for (int i 0; i linkedList.size(); i) { System.out.println(linkedList.get(i)); } } }public E pop():从此列表所表示的堆栈处弹出一个元素。 public void push(E e):将元素推入此列表所表示的堆栈。public class Demo06LinkedList { public static void main(String[] args) { LinkedListString linkedList new LinkedList(); linkedList.add(吕布); linkedList.add(刘备); linkedList.add(关羽); linkedList.add(张飞); linkedList.add(貂蝉); //public E pop():从此列表所表示的堆栈处弹出一个元素。 linkedList.pop(); System.out.println(linkedList); //public void push(E e):将元素推入此列表所表示的堆栈。 linkedList.push(涛哥); System.out.println(linkedList); } }1.1 LinkedList底层成员解释说明1.LinkedList底层成员 transient int size 0; 元素个数 transient NodeE first; 第一个节点对象 transient NodeE last; 最后一个节点对象 2.Node代表的是节点对象 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; } }1.2 LinkedList中add方法源码分析LinkedListString list new LinkedList(); list.add(a); list.add(b); void linkLast(E e) { final NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; modCount; }1.3.LinkedList中get方法源码分析public E get(int index) { checkElementIndex(index); return node(index).item; } NodeE node(int index) { // assert isElementIndex(index); if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }index (size 1)采用二分思想先将index与长度size的一半比较如果indexsize/2就只从位置0往后遍历到位置index处而如果indexsize/2就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历第八章.增强for1.基本使用1.作用: 遍历集合或者数组 2.格式: for(元素类型 变量名:要遍历的集合名或者数组名){ 变量名就是代表的每一个元素 } 3.快捷键:集合名或者数组名.forpublic class Demo01ForEach { public static void main(String[] args) { ArrayListString list new ArrayList(); list.add(张三); list.add(李四); list.add(王五); list.add(赵六); for (String s : list) { System.out.println(s); } System.out.println(); int[] arr {1,2,3,4,5}; for (int i : arr) { System.out.println(i); } } }2. 性能比较public class Demo02ForEach { public static void main(String[] args) { LinkedListInteger list2 new LinkedList(); for (int i 0; i 100000; i) { list2.add(i); } // 记录开始时间 long start System.currentTimeMillis(); for (int i 0; i list2.size(); i) { int tmp list2.get(i); } long end System.currentTimeMillis(); System.out.println(for耗时 (end - start)); start System.currentTimeMillis(); IteratorInteger it list2.iterator(); while (it.hasNext()) { int tmp it.next(); } end System.currentTimeMillis(); System.out.println(迭代器耗时 (end - start)); start System.currentTimeMillis(); for (Integer i : list2) { int tmp i; } end System.currentTimeMillis(); System.out.println(增强for耗时 (end - start)); } }3.注意1.增强for遍历集合时,底层实现原理为迭代器 2.增强for遍历数组时,底层实现原理为普通for