List、Set、数据结构、Collections

学习目标

• 能够说出常见得数据结构有哪些及其特点
• 能够说出数组结构特点
• 能够说出栈结构特点
• 能够说出数组结构特点
• 能够说出单向链表结构特点
• 能够说出红黑树特点
• 能够说出list集合特点
• 能够说出Set集合的特点
• 能够说出哈希表的特点
• 使用HashSet集合存储自定义元素
• 能够说出可变参数的格式
• 能够使用集合工具类
• 能够使用Comparator比较器进行排序

1.栈结构特点

栈又称堆栈，它是运算受限得线性表，只允许一端进行插入和删除（只有一个口，先进后出，类似弹夹）

2.队列结构特点

队列只允许一端插入一端删除（两个口，先进先出，类似安检）

3.数组结构特点

数组，在内存中开辟一段连续的内存空间。特点是查询快，增删慢。原因是查询数组中长度固定并连续，知道开头位置和偏移量就能知道元素具体地址；增删慢是因为需要重新创建新数组，复制删除或增加的其他元素到新数组中，在指定位置进行添加和删除操作。

image

4.链表结构特点

链表，查询慢，增删快。因为链表地址非连续，必须重头开始查询，当增加/删除元素对链表结构没有影响，所以增删快。

• 单向列表：链表中只有一个链子，不能保证元素顺序

• 双向列表：链表中有两条链子，专门纪录元素顺序，是一个有序集合。

  image
  image

5.红黑树特点

红黑树，趋近于平衡树，查询得速度非常快，查询叶子节点最大次数和最小次数不能超过2倍

image

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方法，判断是否重复。

image

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;//升序 } }
        }
    }