四、ArrayList类
ArrayList类，基于数组算法的列表，通过查看源代码会发现底层其实就是一个Object数组
ArrayList是一个List接口的实现类,实现了可变数组,当添加一个元素时,如果容量足够,直接添加,如果容量不够,按照newCapacity = oldCapacity + oldCapacity/2 原则拓容
由于ArrayList底层数据结构是数组,决定了该实现类在查询的场景下比较适用,添加和删除的场景效率稍低
public class ArrayListDemo1 { /** ArrayList的常用API **/ public static void main(String[] args) { //创建一个默认长度的列表对象 List list = new ArrayList(); //打印集合中元素的个数 System.out.println("元素数量："+list.size());//0 //添加操作：向列表中添加4个元素 list.add("Will"); list.add(100); list.add(true); list.add("Lucy"); //查询操作: System.out.println("列表中所有元素："+list);//输出:[Will, 100, true, Lucy] System.out.println("元素数量："+list.size());//4 System.out.println("第一个元素："+list.get(0));//Will //修改操作：把索引为2的元素，替换为wolfcode list.set(2, "wolfcode"); System.out.println("修改后："+list);//输出:[Will, 100, wolfcode, Lucy] //删除操作：删除索引为1的元素 list.remove(1); System.out.println("删除后："+list);//输出:[Will, wolfcode, Lucy] } } 复制代码
我们画出ArrayList的内存图可以发现集合类中存储的对象,都存储的是对象的引用,而不是对象本身
五、LinkedList类
LinkedList由于底层数据结构是链表,在添加元素和删除元素时效率很高,查询元素效率低。 LinkedList类，底层采用链表算法，实现了链表，队列，栈的数据结构。无论是链表还是队列主要操作的都是头和尾的元素，因此在LinkedList类中除了List接口的方法，还有很多操作头尾的方法。常用的方法如下：
//将指定元素插入此列表的开头。 void addFirst(Object e); //将指定元素添加到此列表的结尾。 void addLast(Object e); //返回此列表的第一个元素。 Object getFirst(); //返回此列表的最后一个元素。 Object getLast(); //移除并返回此列表的第一个元素。 Object removeFirst(); //移除并返回此列表的最后一个元素。 Object removeLast(); //在此列表的开头插入指定的元素。 boolean offerFirst(Object e); //在此列表末尾插入指定的元素。 boolean offerLast(Object e); ////获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 Object peekFirst(); ////获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 Object peekLast(); ////获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 Object pollFirst(); //获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 Object pollLast(); //将元素推入此列表所表示的栈。 void push(Object e); //从此列表所表示的栈处弹出一个元素。 Object pop(); //获取但不移除此列表的头（第一个元素）。 Object peek() 复制代码
import java.util.LinkedList; public class LinkedListDemo { public static void main(String[] args) { LinkedList list = new LinkedList(); //添加元素 list.addFirst("A"); list.addFirst("B"); System.out.println(list); list.addFirst("C"); System.out.println(list); list.addLast("D"); System.out.println(list); //获取元素 System.out.println("获取第一个元素：" + list.getFirst());//C System.out.println("获取最后一个元素：" + list.getLast());//D //删除元素 list.removeFirst(); System.out.println("删除第一个元素后：" + list);//[B, A, D] list.removeLast(); System.out.println("删除最后一个元素后：" + list);//[B, A] } } 复制代码
六、Stack和Vector类
Vector类：基于数组算法实现的列表，其实就是ArrayList类的前身。和ArrayList的区别在于方法使用synchronized修饰，所以相对于ArrayList来说，线程安全，但是效率就低了点。 Stack类：表示栈，是Vector类的子类，具有后进先出(LIFO)的特点，拥有push（入栈），pop（出栈）方法。
七、集合的遍历
List<String> list = new ArrayList<>(); list.add("西施"); list.add("王昭君"); list.add("貂蝉"); list.add("杨玉环"); 复制代码
7.1、for循环
for (int index = 0; index < list.size(); index++) { String ele = list.get(index); System.out.println(ele); } 复制代码
7.2、使用迭代器
在程序开发中，经常需要遍历集合中的所有元素。针对这种需求，JDK专门提供了一个接口java.util.Iterator。
想要遍历Collection集合，那么就要获取该集合迭代器完成迭代操作，下面介绍一下获取迭代器的方法：
public Iterator iterator(): 获取集合对应的迭代器，用来遍历集合中的元素的。
Iterator表示迭代器对象，迭代器中拥有一个指针，默认指向第一个元素之前，有如下几个方法：
public E next()：判断指针后是否存在下一个元素public boolean hasNext()：获取指针位置下一个元素，获取后指针向后移动一位，如果仍有元素可以迭代，则返回 true
Iterator iterator = list.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next()); } 复制代码
注意：
- 在进行集合元素获取时，如果集合中已经没有元素了，还继续使用迭代器的next方法，将会抛出
java.util.NoSuchElementException没有集合元素异常。 - 在进行集合元素获取时，如果添加或移除集合中的元素 , 将无法继续迭代 , 将会抛出
ConcurrentModificationException并发修改异常。
7.3、for-each遍历（增强for循环）
语法：
for(数据类型 迭代变量: 实例对象){ //TODO } 复制代码
for (String ele : list) { System.out.println(ele); } 复制代码
7.4、forEach的函数式编程遍历
list.forEach(object -> System.out.println(object)); 复制代码
7.5、并发修改异常
在迭代集合时删除集合元素，比如删除王昭君
List<String> list = new ArrayList<>(); list.add("西施"); list.add("王昭君"); list.add("貂蝉"); list.add("杨玉环"); for (String ele : list){ if ("王昭君".equals(ele)){ list.remove(ele); } System.out.println(ele); } 复制代码
执行完会发现报错了：
造成该错误的原因是，不允许在迭代过程中改变集合的长度（不能删除和增加）。
如果要在迭代过程中删除元素，就不能使用集合的remove方法，只能使用迭代器的remove方法，此时只能使用迭代器来操作，不能使用foreach。
List<String> list = new ArrayList<>(); list.add("西施"); list.add("王昭君"); list.add("貂蝉"); list.add("杨玉环"); Iterator<String> iterator = list.iterator(); while (iterator.hasNext()){ if ("王昭君".equals(iterator.next())){ iterator.remove(); } } System.out.println(list); 复制代码
八、Set接口
Set是Collection的子接口，Set接口定义了一种规范，也就是说明该容器不记录元素的添加顺序，也不允许元素重复。
8.1、Set集合的特点
- 不允许元素重复
- 不会记录元素添加的先后顺序
set只包含从Collection继承的方法，不过Set无法记住添加的顺序，也不允许元素重复，当将两个相同的元素添加进Set集合的时候，添加操作失败，添加方法（add()）返回false
8.2、Set接口常用的实现类
- HashSet类：底层采用哈希表实现
- TreeSet类：底层采用红黑书实现，可以对集合中的元素排序
8.3、HashSet
8.3.1、HashSet原理
HashSet底层采用哈希表实现，元素对象的HashCode值决定了在哈希表中存储的位置，当往HashSet中添加新元素的时候，先会判断该位置是否有元素：
- 如果没有，直接把该新的对象存储到hashCode指定的位置
- 如果有，再继续判断新对象和集合对象的equals作比较：
- 若equals为true，则视为同一个对象，不保存，add()方法返回false
- 如果equals为false，则存储在之前的对象的同一个位置上开辟一个链表进行存储
每一个存储到哈希表中的对象，都得重写hashCode和equals方法来判断是否是同一个对象，在一般情况下，equals为true的时候，hashCode应该也相等，Idea可以自动生成这些方法
8.3.2、HashSet常用方法
package day14_ArrayList2.classing; import java.util.HashSet; import java.util.Iterator; import java.util.Set; /** * @author Xiao_Lin * @version 1.0 * @date 2020/12/17 19:38 */ public class SetApi { public static void main(String[] args) { Set<String> set = new HashSet<>(); //添加操作，向列表中添加元素 set.add("will"); set.add("wolf"); set.add("code"); set.add("lucy"); //查询操作 System.out.println("集合中的所有元素为："+set); System.out.println("元素数量："+set.size()); System.out.println("是否存在某个元素："+set.contains("111")); System.out.println("是否存在某个元素："+set.contains("code")); //删除元素 set.remove("code"); System.out.println("删除后的集合为："+set); //增强for循环遍历 for (String ele : set){ System.out.println(ele); } //迭代器遍历 Iterator<String> it = set.iterator(); while (it.hasNext()){ System.out.println( it.next()); } } } 复制代码
package day14_ArrayList2.classing; /** 重写equals和hashCode方法 * @author Xiao_Lin * @version 1.0 * @date 2020/12/17 11:34 */ public class Student { private String name; private Integer sn; private String classname; @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Student student = (Student) o; if (name != null ? !name.equals(student.name) : student.name != null) { return false; } if (sn != null ? !sn.equals(student.sn) : student.sn != null) { return false; } return classname != null ? classname.equals(student.classname) : student.classname == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + (sn != null ? sn.hashCode() : 0); result = 31 * result + (classname != null ? classname.hashCode() : 0); return result; } public Student(String name, Integer sn, String classname) { this.name = name; this.sn = sn; this.classname = classname; } public Student(){ } public String getName() { return name; } public void setName(String name) { this.name = name; } public Integer getSn() { return sn; } public void setSn(Integer sn) { this.sn = sn; } public String getClassname() { return classname; } public void setClassname(String classname) { this.classname = classname; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", sn=" + sn + ", classname='" + classname + '\'' + '}'; } } 复制代码
8.4、TreeSet
TreeSet底层采用了红黑树算法，会对存储的元素对象默认使用自然排序（升序）
| 数据类型 | 排序规则 |
| BigDecimal、BigInteger、Byte、Double、Float、Integer、Long、Short | 按照数字大小排序 |
| Character | 按照字符的Unicode值的数字大小排序 |
| String | 按照字符串中字符的Unicode值排序 |
必须保证TreeSet集合中的元素对象是相同的数据类型，否则报错
import java.util.Set; import java.util.TreeSet; public class TreeSetDemo{ public static void main(String[] args) { Set<String> set = new TreeSet<>(); set.add("wolf"); set.add("will"); set.add("sfef"); set.add("allen"); System.out.println(set);//[allen, sfef, will, wolf] } } 复制代码
8.4.1、TreeSet底层数据结构详解
第一步
插入第一个节点，无需比较，直接作为根节点
第二步
插入第二个节点，和wolf根节点比较，如果小于根节点就作为左子树，如果大于根节点就放在右边，作为右子树
第三步
插入第三个节点，先和wolf根节点比较，较小，左移动作为左子树，因为左边已经有了一颗左子树，所以再和will节点进行比较，较小，继续放在左边作为左子树
第四步
由于TreeSet是平衡二叉树，如果树不平衡（左右子树差值大于1），会对节点进行调整
第五步
插入第四个节点，先和根节点will进行比较，较小，左移，再和sfef节点作比较，依然较小，左移
8.4.2、Comparable接口
在缺省的情况下，TreeSet中的元素会采用自然排序（从小到大），此时要求元素对象必须实现java.util.Comparable接口，大多数的JDK自带的类都实现了该接口，比如说最常见的八大包装类和String TreeSet会调用元素的comparaTo()方法来比较元素的大小关系，然后将集合元素按照升序排列
public interface Comparable<T> { public int compareTo(T o); } 复制代码
比较规则
- 当前元素大于传进来的元素，返回正整数1，优先级较高
- 当前元素小于传进来的元素，返回负整数-1，优先级较低
- 当前元素等于传进来的元素，返回0，此时认为两个对象是同一个对象
如果我们自定义一个类，且需要存储到TreeSet中，此时我们需要让该类实现Comparable接口，并且覆盖compareTo()方法，在该方法中编写比较规则
package day14_ArrayList2.classing; /** * @author Xiao_Lin * @version 1.0 * @date 2020/12/17 11:34 */ public class Student implements Comparable<Student>{ private String name; private Integer sn; private String classname; //比较规则 @Override public int compareTo(Student student) { //当前对象大于传进来的对象 if (this.sn > student.sn){ return 1; }else if (this.sn < student.sn){ return -1; } return 0; //可以简化为; //return this.sn - student.sn; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Student student = (Student) o; if (name != null ? !name.equals(student.name) : student.name != null) { return false; } if (sn != null ? !sn.equals(student.sn) : student.sn != null) { return false; } return classname != null ? classname.equals(student.classname) : student.classname == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + (sn != null ? sn.hashCode() : 0); result = 31 * result + (classname != null ? classname.hashCode() : 0); return result; } public Student(String name, Integer sn, String classname) { this.name = name; this.sn = sn; this.classname = classname; } } 复制代码
8.4.3、Comparator接口
TreeSet除了支持默认的自然排序外，还支持自定义排序，此时需要在构建TreeSet对象时传递java.util.Comparator接口的实现类对象，Comparator表示比较器，里面封装了比较规则。
此时compare方法返回0，则认为两个对象是同一个对象，返回正数排前面，返回负数排后面。
public interface Comparator<T> { int compare(T o1, T o2); } 复制代码
示范
class User { private String name; import java.util.TreeSet; private int age; public User(String name, int age) { this.name = name; this.age = age; } public int getAge() { return age; } public String getName() { return name; } public String toString() { return "User [name=" + name + ", age=" + age + "]"; } } public class App { public static void main(String[] args) { Set<User> set = new TreeSet<>(new NameLengthComparator()); set.add(new User("James", 30)); set.add(new User("Bryant", 22)); set.add(new User("Allen", 28)); set.add(new User("Will", 17)); System.out.println(set);// } } //封装了比较规则 class NameLengthComparator implements java.util.Comparator<User> { public int compare(User o1, User o2) { int ret = o1.getName().length() - o2.getName().length(); if (ret > 0) { return 1; } else if (ret < 0) { return -1; } else { if (o1.getAge() > o2.getAge()) { return 1; } else if (o1.getAge() < o2.getAge()) { return -1; } else { return 0; } } } }
