Java基础02-数据结构、List和Set集合

1. 数据结构基础篇

1.1 什么是数据结构？

数据结构

? 数据结构就是计算机存储、组织数据的方式。

? 指的是相互之间存在着特定关系的一种或多种的数据元素集合。

1.2 为什么要学习数据结构？

? 通常情况下，精心选择合适的数据结构可以带来更高的运行或存储的效率。

? 数据结构往往同高效的检索算法和索引技术有关。

1.3 数据结构-栈

栈：栈（stack）又名堆栈，是一种运算受限的线性表。
受限：限定仅在表尾进行插入和删除操作的线性表（这一端被称为栈顶，另一端称为栈底）。

栈底和栈顶
特性：先进后出。
- 进栈（压栈）：如下图
  
  出栈入栈
- 出栈（弹栈）：如下图
  
  出栈和入栈

1.4 数据结构-队列

队列：是一种受限的特殊线性表。
受限：只允许在表的前端（队头）进行删除操作，后端（队尾）进行插入操作。
特性：先进先出

队列

1.5 数据结构-数组

数组：一组有序的（索引有序并且从0开始）类型相同的元素集合。
特性：有序、同类型、长度固定。
应用效果：
- 查询快。
  - 从数组索引0开始查找，根据指定位置的偏移量可快速获取数据。
- 增删慢。
  - 数组的长度是固定的，若删除或增加一格元素，则会先创建一个新的数据，再把原数组的数据根据操作复制到新数组中。

1.6 数据结构-链表（单链表）

链表

链表：是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
特点：
- 由一系列结点（链表中的每一个元素称为结点）组成。
- 结点可以在运行时动态生成。
- 每个结点包括两个部分
  - 一个是存储数据元素的数据域
  - 另一个是存储下一个结点地址的指针域。
应用效果：
- 查询慢：链表的地址不是连续的，每次查找都得从头开始查找。
- 增删快：增删操作不会影响链表的整体结构。

1.7 数据结构-红黑树

红黑树

红黑树（对称二叉B树）：一种自平衡二叉查找树。
应用效果：
- 查询速度快。
  - 在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能

2. List集合

2.1 List集合介绍

? List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法，如下：

方法：
public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。
public E get(int index) :返回集合中指定位置的元素。
public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素

代码：

List list = new ArrayList();
    list.add("a");
    list.add("b");
    list.add("c");
    // public void add(int index, E element) : 将指定的元素，添加到该集合中的指定位置上。
    list.add(1,"d");
    System.out.println(list); // [a, d, b, c]
    // public E get(int index) :返回集合中指定位置的元素。
    System.out.println(list.get(2)); // b
    // public E remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。
    list.remove(1);
    System.out.println(list); // [a, b, c]
    // public E set(int index, E element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素
    list.set(1,"B");
    System.out.println(list); // [a, B, c]

特点：
- 存取顺序一致，并且有索引。
- 元素内容可重复。

2.2 List集合实现类-ArrayList

? java.util.ArrayList 集合数据存储的结构是数组结构。元素增删慢，查找快，用于日常开发中使用最多的功能为查询数据、遍历数据，所以 ArrayList 是最常用的集合。

? 许多程序员开发时非常随意地使用ArrayList完成任何需求，并不严谨，这种用法是不提倡的。

2.3 List集合实现类-LinkedList

介绍：java.util.LinkedList 集合数据存储的结构是链表结构。方便元素添加、删除的集合。
LinkedList是一个双向链表，那么双向链表是什么样子的呢，如图

链表

常用方法

方法：
实际开发中对一个集合元素的添加与删除经常涉及到首尾操作，而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。

代码：

LinkedList list = new LinkedList();
    list.add("a");
    list.add("b");
    // public void addFirst(E e) :将指定元素插入此列表的开头。
    list.addFirst("A");
    // public void addLast(E e) :将指定元素添加到此列表的结尾。
    list.addLast("B");
    System.out.println(list); // [A, a, b, B]
    // public E getFirst() :返回此列表的第一个元素。
    System.out.println(list.getFirst()); // A
    // public E getLast() :返回此列表的最后一个元素。
    System.out.println(list.getLast()); // B
    // public E removeFirst() :移除并返回此列表的第一个元素。
    list.removeFirst();
    // public E removeLast() :移除并返回此列表的最后一个元素。
    list.removeLast();
    System.out.println(list); //[a, b]
    // public E pop() :从此列表所表示的堆栈处弹出一个元素。
    list.pop();
    System.out.println(list); // [b]
    // public void push(E e) :将元素推入此列表所表示的堆栈。
    list.push("a");
    System.out.println(list); // [a, b]
    // public boolean isEmpty() ：如果列表不包含元素，则返回true。
    System.out.println(list.isEmpty()); // false

3. Set集合

3.1 Set集合介绍

继承了Collectin集合
没有扩充方法
与List集合不同的是会保证集合中元素的唯一性。

3.2 Set集合实现类-HashSet

HashSet介绍
- 集合中的元素存取是无序的
- 集合中的元素是不重复的
- HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于： hashCode 与 equals 方法。
- 代码：
```
Set set = new HashSet();
    set.add("张三");
    set.add("李四");
    set.add("李四");
    set.add("王五");
    set.add("赵六");
    System.out.println(set);  // [李四, 张三, 王五, 赵六]
```

哈希值

一个十进制的逻辑地址。
所有的对象都继承里Object中的HashCode方法

代码：

System.out.println("a".hashCode());  // 97
    System.out.println("b".hashCode()); // 98
    System.out.println("张三".hashCode()); // 774889
    System.out.println("李四".hashCode()); // 842061
    int[]arr1={1,2,3};
    System.out.println(arr1.hashCode()); //1355531311

HashSet存储数据的结构
- 结构：数组+链表/红黑树
  ? 在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。
  ? 但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。
- 图解存储结构
  
  Set

图解元素唯一性原理流程图

流程图

小结：
总而言之，JDK1.8引入红黑树大程度优化了HashMap的性能，那么对于我们来讲保证HashSet集合元素的唯一，其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。

HashSet存储自定义类型对象

要求：自定义人物类型（含有姓名、年龄），用HashSet集合存储，若对象的姓名和年龄一致则在集合中不允许重复

代码：

/*人物类*/
public class People {
  private String name;
  private int age;
  public People(String name, int age) {
    this.name = name;
    this.age = age;
  }
  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    People people = (People) o;
    return age == people.age &&
            name.equals(people.name);
  }
  @Override
  public int hashCode() {
    return Objects.hash(name, 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;
  }
}

// 入口类
public class Main {
  public static void main(String[] args) {
    People p1 = new People("张三",10);
    People p2 = new People("李四",12);
    People p4 = new People("李四",12);
    People p3 = new People("王五",10);

    HashSet set = new HashSet();
    set.add(p1);
    set.add(p2);
    set.add(p3);
    set.add(p4);
    System.out.println(set.size()); // 3
  }
}

3.3 Set集合实现类-LinkedHashSet

组织结构：哈希表（数组+链表/红黑树） + 链表（记录存取顺序）
特点：
- 元素唯一性
- 元素存取有序。

代码：

LinkedHashSet set = new LinkedHashSet();
    set.add("张三");
    set.add("李四");
    set.add("李四");
    set.add("王五");
    set.add("赵六");
    System.out.println(set);  // [张三, 李四, 王五, 赵六]

3.4 其他扩展-可变参数

格式：

修饰符 返回值类型 方法名(参数类型... 形参名){ }
等价于
修饰符 返回值类型 方法名(参数类型[]形参名){ }

代码：

public static void main(String[] args) {
    System.out.println(add(1,2,3));  // 6
    System.out.println(add(1,200,300,400));  // 901
  }

  public  static int add(int...num) {
    int sum = 0;
    for (int i = 0; i < num.length; i++) {
      sum += num[i];
    }
    return sum;
  }

原理：在编译成class文件时，源代码中的可变参数会自动变成数组。
注意事项：
- 可变参数类型要一致
- 可变参数要放在参数列表最后

4. Collections

4.1 Collection介绍和使用

? java.utils.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> )** :将集合中元素按照指定规则排序。

代码：

ArrayList<Integer> list = new ArrayList<>();
    //public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。
    Collections.addAll(list, 1, 3, 4, 5, 6, 8, 7);
    System.out.println(list); // [1, 3, 4, 5, 6, 8, 7]
    //public static void shuffle(List<?> list) 打乱顺序 :打乱集合顺序。
    Collections.shuffle(list);
    System.out.println(list); // 随机顺序[5, 4, 6, 3, 7, 1, 8]
    //public static <T> void sort(List<T> list) :将集合中元素按照默认规则排序。
    Collections.sort(list);
    System.out.println(list); // 默认升序[1, 3, 4, 5, 6, 7, 8]
    //public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。
    Collections.sort(list, new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return o2-o1;
      }
    });
    System.out.println(list);

注意事项：

若要对自定义对象进行排序时，使用 sort(List<T> list)时，自定义类型需要实现Comparable接口，并且要重新CompareTo方法

代码：

public class People implements Comparable<People> {
  private String name;
  private int age;

  public People(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 int compareTo(People o) {
    return this.age - o.age;  // 升序
   // return o.age-this.age; 降序

  }
}