数据结构

栈

• 栈：stack，又称堆栈，它是运算受限的线性表，仅允许在一端进行插入和删除
• 先进后出
• 栈的入口、出口都是栈的顶端位置
• 压栈：存元素
• 弹栈：取元素

队列

• 队列：queue，简称队，也是一种运算受限的线性表，仅允许在表的一端插入，而在表的另一端删除
• 先进先出
• 队列的人口、出口各占一侧

数组

• 数组：Array，是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间释放元素
• 查找元素块
• 增删元素慢

链表

• 链表：linked list，由一系列结点node组成，结点可以在运行时动态生成；结点包括两部分：一部分是存储数据元素的数据域，另一个是存储下一结点地址的指针域
• 多个结点之间通过地址进行连接
• 查找元素慢
• 增删元素块

红黑树

• 二叉树：binary tree，是每个结点不超过2的有序树

• 红黑树的约束：

  1.节点可以是红色或者黑色的

  2.根节点是黑色的

  3.叶子节点（特指空节点）是黑色的

  4.每个红色节点的子节点都是黑色的

  5.任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点：

​ 速度特别快，趋*衡树，查找叶子元素最少和最多次数不多于二倍

List集合

java.util.List接口继承自Collection接口，是单列集合的一个重要分支，习惯性地会将实现了List接口的对象称为List集合

介绍

• 特点：

  1. 它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）

  2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）

  3. 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素

常用方法

• 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的子类

ArrayList集合

java.util.ArrayList集合数据存储的结构是数组结构，增删慢，查找快

LinkedList集合

java.util.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

Set接口

HashSet集合介绍

java.util.HashSet是Set接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致）

HashSet是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能

保证元素唯一性的方式依赖于：hashCode与equals方法

HashSet集合存储数据的结构（哈希表）

JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间

HashSet存储自定义类型元素

HashSet中存放自定义类型元素时，需要重写对象中的hashCode和equals方法，建立自己的比较方式，才能保证HashSet集合中的对象唯一

LinkedHashSet

java.util.LinkedHashSet是链表和哈希表组合的一个数据存储结构

可变参数

在JDK1.5之后，如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，我们可以对其简化成如下格式：

修饰符 返回值类型 方法名（参数类型... 形参名） {}

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

Coparator比较器

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Demo01Comparator {
    public static void main(String[] args) {
        
        //声明一个ArrayList类对象并实例化为list01
        ArrayList<Student> list01 = new ArrayList<>();
        
        //在集合list01添加Student类匿名对象
        list01.add(new Student("Ashe",18));
        list01.add(new Student("Riven",21));
        list01.add(new Student("Zoe",21));
        list01.add(new Student("Timo",21));
        
        //自定义排序规则
        Collections.sort(list01, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                
                //根据年龄来排序，如果年龄一样则根据首字母来排序
                int result = o1.getAge() - o2.getAge();    
                if(result == 0) {
                    result = o1.getName().charAt(0) - o2.getName().charAt(0);
                }
                
                
                return result;
            };
        });
        System.out.println(list01);
    }
}