主要内容

• 数据结构
• List集合
• Set集合
• Collections工具类

一.数据结构

1.1 数据结构有什么用

当你用着java里面的容器类很爽的时候，你有没有想过，怎么ArrayList就像一个无限扩充的数组，也好像链表之类的。好用吗？好用，这就是数据结构的用处，只不过你在不知不觉中使用了。

现实世界的存储，我们使用的工具和建模。每种数据结构有自己的优点和缺点，想想如果Google的数据用的是数组的存储，我们还能方便地查询到所需要的数据吗？而算法，在这么多的数据中如何做到最快的插入，查找，删除，也是在追求更快。

我们java是面向对象的语言，就好似自动档轿车，C语言好似手动档吉普。数据结构呢？是变速箱的工作原理。你完全可以不知道变速箱怎样工作，就把自动档的车子从 A点 开到 B点，而且未必就比懂得的人慢。写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。当然了，数据结构内容比较多，细细的学起来也是相对费功夫的，不可能达到一蹴而就。我们将常见的数据结构：堆栈、队列、数组、链表和红黑树 这几种给大家介绍一下，作为数据结构的入门，了解一下它们的特点即可。

1.2 栈(stack)

栈：stack,又称堆栈，它是运算受限的线性表。其限制是仅允许在标的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

简单的说：采用该结构的集合，对元素的存取有如下的特点

• 先进后出：（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。例如，子弹压进弹夹，先压进去的子弹在下面，后压进去的子弹在上面，当开枪时，先弹出上面的子弹，然后才能弹出下面的子弹。

• 栈的入口、出口的都是栈的顶端位置。

这里两个名词需要注意：

• 压栈：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
• 弹栈：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

1.3 队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。

简单的说，采用该结构的集合，对元素的存取有如下的特点：

• 先进先出：（即，存进去的元素，要在后它前面的元素依次取出后，才能取出该元素）。例如，小火车过山洞，车头先进去，车尾后进去；车头先出来，车尾后出来。
• 队列的入口、出口各占一侧。例如，下图中的左侧为入口，右侧为出口。

1.4 数组

数组:Array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是一排出租屋，有100个房间，从001到100每个房间都有固定编号，通过编号就可以快速找到租房子的人。

特点

简单的说,采用该结构的集合，对元素的存取有如下的特点：

• 查找元素快：通过索引，可以快速访问指定位置的元素

这是因为数组的地址值是连续的，并且长度固定，可以快速的通过索引得到想要的数据。

• 增删元素慢：

1. 指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。

2. 指定索引位置删除元素：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。

图例：

1.5 链表

链表(linked list),由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时i动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表，那么这里给大家介绍的是单向链表。

简单的说，采用该结构的集合，对元素的存取有如下的特点：

• 多个结点之间，通过地址进行连接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。

• 查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素，每次查询都需要从第一个开始元素查找。

• 增删元素快：

  • 增加元素：只需要修改连接下个元素的地址即可。

• 删除元素：只需要修改连接下个元素的地址即可。

1.6 红黑树

二叉树：binary tree ,是每个结点不超过2的有序树（tree） 。

简单的理解，就是一种类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点。

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点，两边被称作“左子树”和“右子树”。

如图：

对于二叉树，有几种特殊的二叉树：

• 排序树/查找树：左子树的值一定比右子树的小，这样有利于根据大小寻找某个值。
• 平衡树
• 不平衡树

我们要说的是二叉树的一种比较有意思的叫做红黑树，红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。

红黑树的约束:

1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点:​速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍。、

2. List集合

我们掌握了Collection接口的使用后，再来看看Collection接口中的子类，他们都具备那些特性呢？

接下来，我们一起学习Collection中的常用几个子类（java.util.List集合、java.util.Set集合）。

2.1 List接口介绍

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

List接口特点：

1. 它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。
2. 它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
3. 集合中可以有重复的元素，通过元素的equals方法，来比较是否为重复的元素。

tips:我们在基础班的时候已经学习过List接口的子类java.util.ArrayList类，该类中的方法都是来自List中定义。

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

示例：

public static void main(String[] args) {
        //创建一个List集合对象,多态
        List<String> list = new ArrayList<>();
        //使用add方法往集合中添加元素
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("a");
        //打印集合
        System.out.println(list);//[a, b, c, d, a]  不是地址重写了toString

        //public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
        //在c和d之间添加一个itheima
        list.add(3,"itheima");//[a, b, c, itheima, d, a]
        System.out.println(list);

        //public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素。
        //移除元素
        String removeE = list.remove(2);
        System.out.println("被移除的元素:"+removeE);//被移除的元素:c
        System.out.println(list);//[a, b, itheima, d, a]

        //public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
        //把最后一个a,替换为A
        String setE = list.set(4, "A");
        System.out.println("被替换的元素:"+setE);//被替换的元素:a
        System.out.println(list);//[a, b, itheima, d, A]

遍历List:三种方式

    public static void main(String[] args) {
        //创建一个List集合对象,多态
        List<String> list = new ArrayList<>();
        //使用add方法往集合中添加元素
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("a");
        //打印集合
        System.out.println(list);//[a, b, c, d, a]  不是地址重写了toString

        //List集合遍历有3种方式
        //使用普通的for循环
        for(int i=0; i<list.size(); i++){
            //public E get(int index):返回集合中指定位置的元素。
            String s = list.get(i);
            System.out.println(s);
        }
        System.out.println("-----------------");
        //使用迭代器
        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            String s = it.next();
            System.out.println(s);
        }
        System.out.println("-----------------");
        //使用增强for
        for (String s : list) {
            System.out.println(s);
        }

        // String r = list.get(5);//IndexOutOfBoundsException: Index 5 out-of-bounds for length 5
        // System.out.println(r);
    }

获取元素时，不能超出最大索引值。否则回抛出：ArrayIndexOutOfBoundsException异常。

2.3 ArrayList集合

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

许多程序员开发时非常随意地使用ArrayList完成任何需求，并不严谨，这种用法是不提倡的。如果要使用的数据查询较少，增删较多，不提倡使用。

2.4 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的子类，List中的方法LinkedList都是可以使用，这里就不做详细介绍，我们只需要了解LinkedList的特有方法即可。在开发时，LinkedList集合也可以作为堆栈，队列的结构使用。（了解即可）

注意：在使用LinkedList时，创建对象时不能使用多态写法，因为多态会限制该对象所能调用的方法。

移除元素：

private static void show03() {
        //创建LinkedList集合对象
        LinkedList<String> linked = new LinkedList<>();
        //使用add方法往集合中添加元素
        linked.add("a");
        linked.add("b");
        linked.add("c");
        System.out.println(linked);//[a, b, c]

//        String first = linked.removeFirst();
        String first = linked.pop();
        System.out.println("被移除的第一个元素:"+first);    // a
        String last = linked.removeLast();
        System.out.println("被移除的最后一个元素:"+last);   // c
        System.out.println(linked);//[b]
    }

获取元素：

    private static void show02() {
        //创建LinkedList集合对象
        LinkedList<String> linked = new LinkedList<>();
        //使用add方法往集合中添加元素
        linked.add("a");
        linked.add("b");
        linked.add("c");

        //linked.clear();//清空集合中的元素 在获取集合中的元素会抛出NoSuchElementException

        if(!linked.isEmpty()){
            String first = linked.getFirst();
            System.out.println(first);       //a
            String last = linked.getLast();
            System.out.println(last);        //c
        }
    }

public boolean isEmpty()：如果列表不包含元素，则返回true。

添加元素：

private static void show01() {
        //创建LinkedList集合对象
        LinkedList<String> linked = new LinkedList<>();
        //使用add方法往集合中添加元素
        linked.add("a");
        linked.add("b");
        linked.add("c");
        System.out.println(linked);//[a, b, c]

        //public void addFirst(E e):将指定元素插入此列表的开头。
        //linked.addFirst("www");
        linked.push("www");
        System.out.println(linked);//[www, a, b, c]

        //public void addLast(E e):将指定元素添加到此列表的结尾。此方法等效于 add()
        linked.addLast("com");
        System.out.println(linked);//[www, a, b, c, com]
    }

3. Set集合

java.util.Set接口和java.util.List接口一样，同样继承自Collection接口，它与Collection接口中的方法基本一致，并没有对Collection接口进行功能上的扩充，只是比Collection接口更加严格了。与List接口不同的是，Set接口中元素无序。

并且都会以某种规则保证存入的元素不出现重复：
其调用e1.equals(e2)，返回true时，表示该元素重复，那么Set只保留一个。

Set集合有多个子类，这里我们介绍其中的java.util.HashSet、和java.util.LinkedHashSet这两个集合。

Set集合取出元素的方式可以采用：迭代器、增强for

3.1 HashSet集合

java.util.HashSet是Set接口的一个实现类，它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。java.util.HashSet底层的实现其实是一个java.util.HashMap支持。

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

示例：

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()){
            Integer n = it.next();
            System.out.println(n);//1,2,3
        }
        //使用增强for遍历set集合
        System.out.println("-----------------");
        for (Integer i : set) {
            System.out.println(i);
        }
    }

对于其他数据类型的数据在存储时，也遵循无序，不重复的原则。
注意：String类型有常量池。

3.2 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

3.3 treeSet集合

treeSet集合采用二叉树的结构进行数据存储

4. 可变参数

我们在使用方法参数时，如果参数的类型都为同一中类型，那么在方法参数列表中可以使用可变参数的格式进行标识。

public static int add(int...arr){

        //定义一个初始化的变量,记录累加求和
        int sum = 0;
        //遍历数组,获取数组中的每一个元素
        for (int i : arr) {
            //累加求和
            sum += i;
        }
        //把求和结果返回
        return sum;
    }

arr的底层时使用数组进行表示，可变参数一般写在参数列表的最后边。

5.集合工具类Collections

• Collections.sort(list):对集合list进行升序排序。
• Collections.reverse(list)：将集合反转
• Collections.max(list)：返回集合中最大元素
  -Collections.min(list)：返回集合中最小元素
• copy:复制

 public static void main(String[] args) {

        // 创建集合
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        // 加入一些数据
        Collections.addAll(list,4,5,6);
        list.add(3);
        System.out.println(list);  //[1, 2, 3, 4, 5, 6, 3]

        // 获取最大值，最小值
        Integer max = Collections.max(list);
        System.out.println(max);         // 6
        Integer min = Collections.min(list);
        System.out.println(min);          // 1

        // 反转,原地操作
        Collections.reverse(list);
        System.out.println(list);  //[3, 6, 5, 4, 3, 2, 1]

        Collections.shuffle(list);
        System.out.println(list); //[4, 5, 6, 3, 1, 2, 3]
    }

6.Map集合

6.1 Map概述

• Collection中的集合，元素是孤立存在的（理解为单身），向集合中存储元素采用一个个元素的方式存储。
• Map中的集合，元素是成对存在的(理解为夫妻)。每个元素由键与值两部分组成，通过键可以找对所对应的值。
• Collection中的集合称为单列集合，Map中的集合称为双列集合。
• 需要注意的是，Map中的集合不能包含重复的键，值可以重复；每个键只能对应一个值。

6.2 Map常用子类

• HashMap - key/value对按照哈希算法存储的。
• TreeMap:key/value对按照key排序存储的。
  通过查看Map接口描述，看到Map有多个子类，这里我们主要讲解常用的HashMap集合、LinkedHashMap集合。

• HashMap<K,V>：存储数据采用的哈希表结构，元素的存取顺序不能保证一致。由于要保证键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。
• LinkedHashMap<K,V>：HashMap下有个子类LinkedHashMap，存储数据采用的哈希表结构+链表结构。通过链表结构可以保证元素的存取顺序一致；通过哈希表结构可以保证的键的唯一、不重复，需要重写键的hashCode()方法、equals()方法。

tips：Map接口中的集合都有两个泛型变量<K,V>,在使用时，要为两个泛型变量赋予数据类型。两个泛型变量<K,V>的数据类型可以相同，也可以不同。

6.3 Map常用方法

Map接口中定义了很多方法，常用的如下：

• public V put(K key, V value): 把指定的键与指定的值添加到Map集合中。

• m.putAll(HashMap a):将a中所有的映射关系加入到m中,无返回值。

// 设置Map集合键值的泛型都为String
        Map<String,String> m = new HashMap<>();
        // 添加元素
       m.put("zhangsan","22");
        m.put("lizhao","20");
        // a集合
        Map<String,String> a = new HashMap<>();
        a.put("lisi","50");
        m.putAll(a);
        System.out.println(m);   
        //{lisi=50, lizhao=20, zhangsan=22}

• public V remove(Object key): 把指定的键 所对应的键值对元素 在Map集合中删除，返回被删除元素的值V。如果remove()的参数为键和值，在集合中查找该键值，有的话返回true，删除该键值对，否则返回false，

public static void main(String[] args) {
        Map<String,String> m = new HashMap<>();
        // 添加元素
        m.put("tom","18");
        m.put("lizhao","20");

        // 删除
        Object v = m.remove("tom");
        System.out.println(v);   //18
        boolean v1 = m.remove("lizhao", 1);
        System.out.println(v1);      //false
}

• public V get(Object key) 根据指定的键，在Map集合中获取对应的值。

public static void main(String[] args) {
        Map<String,String> m = new HashMap<>();
        // 添加元素
        m.put("tom","18");
        m.put("lizhao","20");
        System.out.println(m.get("tom"));   // 18
}

• boolean containsKey(Object key) 判断集合中是否包含指定的键。

• boolean containsValue(Object key) :判断该集合中是否存在该value值所对应一个或多个键。

 public static void main(String[] args) {
        Map<String,String> m = new HashMap<>();
        // 添加元素
        m.put("tom","18");
        m.put("lizhao","20");
        System.out.println(m.containsKey("tom"));  //true
        System.out.println(m.containsValue("20"));  //true

• public int size():获取集合的长度/元素个数

public static void main(String[] args) {
        Map<String,String> m = new HashMap<>();
        // 添加元素
        m.put("tom","18");
        m.put("lizhao","20");
        // 长度元素个数
        System.out.println(m.size());   //2

• public Set<K> keySet(): 获取Map集合中所有的键，返回值存储到Set集合中。

public static void main(String[] args) {
        Map<String,String> m = new HashMap<>();
        // 添加元素
        m.put("tom","18");
        m.put("lizhao","20");
        
        m.put("zhangsan","22");
        // 遍历所有的key
        Set s = m.keySet();
        for (Object o : s) {
            System.out.println(o+":"+m.get(o));
          // tom:18
          // lizhao:20
          // zhangsan:22 
}

• Collection<V> values():获取Map中的所有值，返回一个Collection集合。

        System.out.println(m);  //{lisi=50, lizhao=20, zhangsan=22}
        // 遍历value
        Collection<String> values = m.values();
        for (String value : values) {
            System.out.println(value);  
            //50
            //20
            //22
        }

• public Set<Map.Entry<K,V>> entrySet(): 获取到Map集合中所有的键值对对象的集合(Set集合)。

• public K getKey():获取entry对象中得键。
• public V getValues():获取entry对象中得值。

        System.out.println(m);  //{lisi=50, lizhao=20, zhangsan=22}
        Set<Map.Entry<String, String>> e = m.entrySet();
        for (Map.Entry<String, String> entry : e) {
            System.out.println(entry);
            // lisi=50
            //lizhao=20
            //zhangsan=22
            // 获取每个键值对象中的键
            System.out.println(entry.getKey());
            // 获取键值对象中得值
            System.out.println(entry.getValue());        
}

6.4 总结