学习目标
- 能够说出常见得数据结构有哪些及其特点
- 能够说出数组结构特点
- 能够说出栈结构特点
- 能够说出数组结构特点
- 能够说出单向链表结构特点
- 能够说出红黑树特点
- 能够说出list集合特点
- 能够说出Set集合的特点
- 能够说出哈希表的特点
- 使用HashSet集合存储自定义元素
- 能够说出可变参数的格式
- 能够使用集合工具类
- 能够使用Comparator比较器进行排序
1.栈结构特点
栈又称堆栈，它是运算受限得线性表，只允许一端进行插入和删除（只有一个口，先进后出，类似弹夹）
2.队列结构特点
队列只允许一端插入一端删除（两个口，先进先出，类似安检）
3.数组结构特点
数组，在内存中开辟一段连续的内存空间。特点是查询快，增删慢。原因是查询数组中长度固定并连续，知道开头位置和偏移量就能知道元素具体地址；增删慢是因为需要重新创建新数组，复制删除或增加的其他元素到新数组中，在指定位置进行添加和删除操作。
4.链表结构特点
链表，查询慢，增删快。因为链表地址非连续，必须重头开始查询，当增加/删除元素对链表结构没有影响，所以增删快。
单向列表：链表中只有一个链子，不能保证元素顺序
-
双向列表：链表中有两条链子，专门纪录元素顺序，是一个有序集合。
image
image
5.红黑树特点
红黑树，趋近于平衡树，查询得速度非常快，查询叶子节点最大次数和最小次数不能超过2倍
6.list接口特点
list，是一个存取有序得集合，允许出现重复元素，可以通过索引访问指定元素。
public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。
public E get(int index) :返回集合中指定位置的元素。
public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
- ArrayList集合 底层是一个数组结构，查询快，增删慢。
- LinkedList集合 底层是链表结构，查询慢，增删快。
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。
- Vector集合单线程集合
7.Set接口的特点
无序集合，不允许重复元素。没有索引，没有带索引得方法，不能for循环遍历
- HashSet是 Set 接口的一个实现类，不允许重复元素，存取顺序可能不一致。
- hash值：是一个十进制整数，系统随机给出（是逻辑地址，不是真实得存储物理地址）
HashSet存储数据结构（哈希表），jdk>=1.8 哈希表=数组+红黑树 ，jdk<1.8 哈希表=数组+链表。
1.Hashset存储数据步骤：
- 第一步，开辟数组空间，先计算元素得hash值
- 第二步，不同哈希值放在数组空间内，相同hash值形成链表（红黑树）==【当链表长度超过8位，会把链表转成红黑树】==
2.set元素不允许存储重复元素原理
set元素在调用add()方法时，add()方法会调用元素得hashcode方法和equals方法，判断是否重复。
3.HashSet存储自定义类型元素
需求：同名同年龄，视为同一个人，只能存储一次。
回答：重写equals()和hashCode()方法。
代码如下：
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);
}
}
public class HashSetDemo2 {
public static void main(String[] args) {
//创建集合对象 该集合中存储 Student类型对象
HashSet<Student> stuSet = new HashSet<Student>();
//存储
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=郭德纲, age=44]
Student [name=于谦, age=43]
Student [name=郭麒麟, age=23]
4.LinkedHashSet集合特点
继承Hashset集合,不重复，底层是哈希表（数组+链表/红黑树）+链表（纪录元素得存储位置）,保证元素有序。
5.可变参数
jdk1.5之后出现的新特性，方法类型已知，个数未知.（数据类型 ...）,其原理底层是一个数组，根据传递参数不同，创建不同长度数组来存储参数个数。
8.Collections集合工具类
public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。
public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序。
public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序。
public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排 序。
1.Comparator比较器
public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序。
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.charAt(0) ‐o1.charAt(0);
}
});
public class Student implements Comparable<Student> {
@Override
public int compareTo(Student o) {
return this.age‐o.age;//升序 } }
}
}
