常见的数据结构

一、常见数据结构

二、List 集合（ArrayList实现)

由于之前已经学过ArrayList集合，这里仅介绍数据结构

Arraylist集合 查询快，增删慢

1.1 List接口

java.util.List 接口继承自 Collection 接口，是单列集合的一个重要分支，习惯性地会将实现了 List 接口的对 象称为List集合。在List集合中允许出现重复的元素，所有的元素是以一种线性方式进行存储的，在程序中可以通过 索引来访问集合中的指定元素

1.2 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) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。

//注意：操作集合索引时，一定要主要索引越界异常
public class Demo01List {
    public static void main(String[] args) {
        //创建List集合对象，多态
        List<String> list=new ArrayList<>();
        //用add方法往集合添加元素
        list.add("b");
        list.add("c");
        list.add("a");
        list.add("a");//允许重复
        list.add("d");
        //打印集合
        System.out.println(list);//[b,c,a,a,d]
        //public void add(int index,E element):将制定元素，添加到集合指定的位置上
        list.add(3,"RainDown");
        System.out.println(list);
        //public E remove(int index):移除指定位置的元素，返回被移除元素
        String removeE=list.remove(3);
        System.out.println("被移除元素:"+removeE);//被移除元素:RainDown
        System.out.println(list);//[b, c, a, a, d]
        //public E set(int index,E element):用指定元素替换集合中指定位置的元素，返回替换前的元素
        String setE=list.set(4,"D");
        System.out.println("被替换元素:"+setE);//被替换元素:d
        System.out.println(list);//[b, c, a, a, D]
        //list集合遍历 ->3种方式
        //for
        for (int i = 0; i < list.size(); i++) {
            //public E get(int index):返回集合中指定位置的元素
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("==============");
        //迭代器遍历
        Iterator<String> it=list.iterator();
        while (it.hasNext())
        {
            String s=it.next();
            System.out.print(s+" ");
        }
        System.out.println();
        System.out.println("===============");
        //增强for循环遍历
        for (String s : list) {
            System.out.print(s+" ");
        }
        System.out.println();
        System.out.println("=================");
    }
}

三、List的子类

3.1 ArrayList

由于之前已经学过ArrayList集合，这里仅介绍数据结构

Arraylist集合 查询快，增删慢

3.2 LinkedList

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

import java.util.LinkedList;
public class Demo01LinkedList {
    public static void main(String[] args) {
        show01();
        show02();
        show03();
    }
    private static void show03() {
        //创建LinkedList集合
        LinkedList<String> link=new LinkedList<String>();
        //使用add方法往集合中添加元素
        link.add("a");
        link.add("b");
        link.add("c");
        //移除元素的方法
        String first=link.removeFirst();//移除并返回列表第一个元素
        String last=link.removeLast();//移除并返回列表最后一个元素
        System.out.println("removed first:"+first+"\nremoved last:"+last);
        //        removed first:a
        //        removed last:c
        System.out.println(link);//[b]
    }
    private static void show02() {
        //创建LinkedList集合
        LinkedList<String> link=new LinkedList<String>();
        //使用add方法往集合中添加元素
        link.add("a");
        link.add("b");
        link.add("c");
        //集合无元素，则抛出NoSuchElementException异常
        if(!link.isEmpty()){
            String first=link.getFirst();//获取第一个元素
            String last=link.getLast();//获取末尾元素
            System.out.println("first:"+first+"\nlast:"+last);
//            first:a
//            last:c
        }
    }
    private static void show01() {
        //创建LinkedList集合
        LinkedList<String> link=new LinkedList<String>();
        //使用add方法往集合中添加元素
        link.add("a");
        link.add("b");
        link.add("c");
        System.out.println(link);//[a,b,c]
        //public void addFirst(E e)指定元素插入列表开头
        link.addFirst("www");
        link.push("2www");//和addFirst方法效果一样
        System.out.println(link);//[2www,www,a,b,c]
        //public void addLast(E e),将指定元素添加至列表尾部，等效于add方法
        link.addLast("com1");
        link.add("com2");
        System.out.println(link);//[2www,www,a,b,c,com1,com2]
    }
}

四、Set 接口

Set接口和List接口一样继承与Collection接口

Set接口特点

        **1.不允许存储重复元素**

        **2.没有索引，没有带索引的方法，不能使用普通for循环遍历**

tips：Set集合取出元素方法：迭代器、增强for循环

4.1 HashSet

java.util.HashSet 是 Set 接口的一个实现类

它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序 不一致)

HashSet 是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。保证元素唯一性 的方式依赖于： hashCode 与 equals 方法。

public class Demo01HashSet {
    public static void main(String[] args) {
        Set<Integer> set=new HashSet<>();
        //使用add方法往集合中添加元素
        set.add(1);
        set.add(3);
        set.add(2);
        set.add(1);

        //使用迭代器遍历Set集合
        Iterator<Integer> it=set.iterator();
        while(it.hasNext())
        {
            System.out.print(it.next()+" ");
        }
        //1 2 3
        //剔除了重复元素，并且不按存入顺序读取
        System.out.println();
        //增强for循环
        System.out.println("============");
        for (Integer integer : set) {
            System.out.print(integer+" ");
        }
    }
}

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

hash值

哈希值：是一个十进制的整数，由系统随机给出(就是对象的地址值，是一个逻辑地址，是模拟出来的，不是数据实际存储的物理地址）

在Object类中有一个方法， 可以获取对象的哈希值
int hashCode() 返回该对象的哈希码值
hashcode的源码：

public native int hashCode();
       // native：代表该方法调用的是本地操作系统的方法

简介

哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的

数组结构：把元素进行了分组（相同哈希值的元素是一组）

链表/红黑树结构：把相同哈希值的元素连接到一起

哈希表数组结构初始容量为16

哈希冲突：两个元素不同，但是哈希值相同

流程：

• 将元素按照哈希值进行分组到数组的不同下标处
• 再将相同哈希值的元素用链表连接在一起
• 一旦链表长度超过8时，转换为红黑树存储

4.3 Set集合元素不重复原理

HashSet<String> set=new HashSet<>();
String s1=new String("abc");
String s2=new String("abc");
set.add(s1);
set.add(s2);
set.add("重地");
set.add("通话");
set.add("abc");
System.out.println(set);//[重地,通话,abc]

Set集合在调用add方法时，add方法会调用元素的hashCode方法和equals方法，判断元素是否重复

当存入s1的时候调用hashcode方法发现集合中没有相同哈希值，所以存入

当存入s2的时候调用hashcode方法发现集合中有相同hash值的元素，然后调用equals方法进行比较，返回true ->哈希值相同，equals方法返回true 所以判定元素重复

所以重地和通话不是重复元素

4.4 HashSet存储自定义类型元素

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

创建自定义Student类

import java.util.Objects;

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);
    }
    //重写equals

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    //重写hashCode

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    //重写toString
}

测试类：

public class Demo01HashSet {
    public static void main(String[] args) {
        //创建集合对象 该集合中存储Student类型对象
        HashSet<Student> stuSet= new HashSet();

        //添加元素
        Student stu=new Student("骆瑜",20);
        stuSet.add(stu);
        stuSet.add(new Student("骆瑜",20));
        stuSet.add(new Student("雨落",20));
        stuSet.add(new Student("雨落",18));

        for (Student student : stuSet) {
            System.out.println(student);
            //重写toString方法即可
        }

//        Student{name='雨落', age=20}
//        Student{name='雨落', age=18}
//        Student{name='骆瑜', age=20}
    }
}

4.4 LinkedHashSet

LinkedHashSet -> 不允许重复 + 有序

我们知道HashSet保证元素唯一，可是元素存放进去是没有顺序的，那么我们要保证有序，怎么办呢？

在HashSet下面有一个子类java.util.LinkedHashSet，它是链表和哈希表组合的一个数据存储结构。

演示代码如下:

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<String>();
        set.add("bbb");
        set.add("aaa");
        set.add("abc");
        set.add("bbc");
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}
结果：
  bbb
  aaa
  abc
  bbc

4.5 可变参数

可变常数：是JDK1.5之后出现的新特性
使用前提：当方法的参数列表数据类型已经确定，但是参数的个数不确定，就可以使用可变参数
使用格式：定义方法时使用

修饰符 返回值类型 方法名(数据类型...变量名){}

可变参数原理：
可变参数底层就是一个数组，根据传递参数个数不同，会创建不同长度的数组，来存储这些参数
传递的参数个数，可以是0个(不传递)，1,2，…多个

public class Demo0VarArgs {
    public static void main(String[] args) {
        int i = add(10,20,30,40,50);
        System.out.println(i);
    }
    /*
        定义计算（0-n)整数和的方法
        已知：计算整数的和，数据类型已经确定int
        位置：计算的数量，要传递几个参数。
        ->使用可变参数
        调用add()方法，就会创建一个长度为0的数组=> new int[0]
        调用add(...)方法,就会创建一个长度为参数个数的数组 new int[]{...}
    */
    public static int add(int...arr){
        System.out.println(arr);//[I@50cbc42f  [ 代表数组  I 代表数组类型
        System.out.println(arr.length);//长度取决于参数个数
        //定义初始化变量,记录累加求和
        int sum=0;
        //遍历数组，获取每一个元素
        for (int i : arr) {
            sum+=i; //累加求和
        }
        return sum;
    }

注意： 一个方法的参数列表，只能有一个可变参数 如果在方法书写时，这个方法拥有多参数，参数中包含可变参数，可变参数一定要写在参数列表的末尾位置。

五、Collections

5.1常用方法

• 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<String> list=new ArrayList<>();
//往集合中添加多个元素
Collections.addAll(list,"a","b","c","d","e");
System.out.println(list);//[a, b, c, d, e]

//打乱元素顺序
Collections.shuffle(list);
System.out.println(list);//[a, e, d, c, b]


ArrayList<Integer> list2=new ArrayList<>();
Collections.addAll(list2,3,2,1,5,4,6,8,3,8,9,10);

//排序
Collections.sort(list2);//默认升序
System.out.println(list2);//[1, 2, 3, 3, 4, 5, 6, 8, 8, 9, 10]

Sort方法(Comparable)

Sort方法注意事项：
使用sort方法，被排序的集合里面存储的元素/对象，必须实现Comparable
重写接口中的方法compareTo定义排序的规则

Comparable接口的排序规则
自己(this) - 参数 ：升序
参数 - 自己(this) ：降序

定义Person类

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

    ....构造方法and Get Set...

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    //重写排序规则compareTo方法
    @Override
    public int compareTo(Person o) {
        //return 0;
        //自定义比较规则,比较两个人的年龄(this,参数Person)
        return this.getAge() - o.getAge();//升序

    }
}

ArrayList<Person> per=new ArrayList<>();

per.add(new Person("骆瑜",20));
per.add(new Person("雨落",16));
per.add(new Person("李狗蛋",21));

System.out.println(per);//[Person{name='骆瑜', age=20}, Person{name='雨落', age=16}, Person{name='李狗蛋', age=21}]


Collections.sort(per);
System.out.println(per);//[Person{name='雨落', age=16}, Person{name='骆瑜', age=20}, Person{name='李狗蛋', age=21}]

5.2 Comparator比较器

Comparator和Comparable的区别
Comparable：自己(this)和别人(参数)比较，自己需要实现Comparable接口，重写compareTo方法
Comparator：相当于找一个第三方裁判，比较两个参数

ArrayList<Integer> list1=new ArrayList<>();
list1.add(1);
list1.add(3);
list1.add(2);
System.out.println(list1);//[1, 3, 2]

//匿名内部类重写compare方法
Collections.sort(list1, new Comparator<Integer>() {
    //重写比较规则
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1-o2;//升序
        //return o2-o1; 降序
    }
});
System.out.println(list1);//[1, 2, 3]

        ArrayList<Student> list2=new ArrayList<>();
        list2.add(new Student("骆瑜",20));
        list2.add(new Student("雨落",21));
        list2.add(new Student("埃文",21));
        list2.add(new Student("王小二",15));

        Collections.sort(list2, 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(list2);
        //[Student{name='王小二', age=15}, Student{name='骆瑜', age=20}, Student{name='埃文', age=21},Student{name='雨落', age=21}]

第一个字母比较：

public class CollectionsDemo3 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        list.add("cba");
        list.add("aba");
        list.add("sba");
        list.add("nba");
        //排序方法  按照第一个单词的降序
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.charAt(0) - o1.charAt(0);
            }
        });
        System.out.println(list);
    }
}

5.3 扩展

如果在使用的时候，想要独立的定义规则去使用 可以采用Collections.sort(List list,Comparetor c)方式，自己定义规则：

Collections.sort(list, new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return o2.getAge()-o1.getAge();//以学生的年龄降序
    }
});

效果：

Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='jack', age=16}
Student{name='abc', age=16}
Student{name='mark', age=16}

如果想要规则更多一些，可以参考下面代码：

Collections.sort(list, new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                // 年龄降序
                int result = o2.getAge()-o1.getAge();//年龄降序

                if(result==0){//第一个规则判断完了 下一个规则 姓名的首字母 升序
                    result = o1.getName().charAt(0)-o2.getName().charAt(0);
                }

                return result;
            }
        });

效果如下：

Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='abc', age=16}
Student{name='jack', age=16}
Student{name='mark', age=16}