java学习记录十四：Collection、List、泛型、数据结构

快来打我* 2021-09-08 13:38 346阅读 0赞

### java学习记录十四：Collection、List、泛型、数据结构 ###

*  一、集合
 *   *  一、解释
     *  二、集合和数字的区别
     *  三、单列集合
 *  一、collection集合
 *   *  一、解释
     *  二、collection集合常用方法
     *   *  1.把给定的对象添加到当前集合中
         *  2.清空集合中所有的元素
         *  3.把给定的对象在当前集合中删除
         *  4.判断当前集合中是否包含给定的对象
         *  5.判断当前集合是否为空
         *  6.返回集合中元素的个数
         *  7.把集合中的元素，存储到数组中
 *  三、迭代器
 *   *  一、解释
     *  二、写法
     *  三、迭代器的注意事项
     *  四、迭代器原理
 *  四、增强for循环
 *   *  一、解释
     *  二、写法
     *  三、使用注意点
 *  五、泛型
 *   *  一、解释
     *  二、定义和使用泛型的类写法
     *  三、定义和使用含有泛型的方法的写法
     *  四、定义和使用含有泛型的接口的写法
     *  五、实现含有泛型接口的写法
     *   *  1、定义实现类时确定泛型的类型
         *  2.始终不确定泛型的类型，直到创建对象时，确定泛型的类型
     *  六、小结
 *  六、泛型通配符
 *   *  一、解释
     *  二、写法
 *  七、受限泛型
 *   *  一、解释
     *  二、写法
 *  八、数据结构
 *   *  一、解释
     *  二、堆栈结构
     *  三、队列结构
     *  四、数组结构
     *  五、链表结构
     *  六、树结构
     *   *  1、二叉树
         *  2.二叉查找树
         *  3.平衡二叉树
         *  4、红黑树
 *  九、list接口
 *   *  一、解释
     *  二、特点
     *  三、list接口常用方法
     *   *  1.将指定的元素，添加到该集合中的指定位置上。
         *  2.返回集合中指定位置的元素。
         *  3.移除列表中指定位置的元素, 返回的是被移除的元素。
         *  4.用指定元素替换集合中指定位置的元素,返回值的更新前的元素
 *  十一、list接口的实现类
 *   *  一、ArrayList集合
     *  二、LinkedList集合

# 一、集合 #

## 一、解释 ##

集合是java提供的一种容器,可以用来存储多个引用类型数据,基本类型需要包装成引用数据类型,才能存入集合。

## 二、集合和数字的区别 ##

*  数组的长度是固定的。集合的长度是可变的。
 *  集合存储的都是引用数据类型。如果想存储基本类型数据需要存储对应的包装类类型。
 *  数组可以存储

## 三、单列集合 ##

单列集合就是单个元素存储的，相当于没有键，与值对应，双列集合就是有键，有值。单列就是单个对象存储。  
Collection：是单列集合类的根接口，用于存储一系列符合某种规则的元素，

# 一、collection集合 #

## 一、解释 ##

collection集合是单列集合的顶层父接口，collection集合没有索引，不能遍历，但是sun公司有一个遍历器，可以遍历其中的数据。  
它有两个重要的子接口,分别是

*  `java.util.List:` **List的特点是元素有序、元素可重复,元素有索引 ;**
    
     *  `List`接口的主要实现类有`java.util.ArrayList`和`java.util.LinkedList`，
     *  ArrayList集合: 实现类,查询快,增删慢
     *  LinkedList集合: 实现类,查询慢,增删快
 *  `java.util.Set:` **Set的特点是元素不可重复,元素无索引**。
    
     *  `Set`接口的主要实现类有`java.util.HashSet`和`java.util.LinkedHashSet`，`java.util.TreeSet`。
     *  LinkedHashSet集合:实现类,元素存取有序
     *  TreeSet集合:实现类,可以对集合中的元素进行排序

## 二、collection集合常用方法 ##

### 1.把给定的对象添加到当前集合中 ###

//public boolean add(E e)： 把给定的对象添加到当前集合中 。
         // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
       System.out.println("col集合:"+col);// col集合:[范冰冰, 李冰冰, 林心如, 赵薇]

### 2.清空集合中所有的元素 ###

//public void clear() :清空集合中所有的元素
         // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
           System.out.println("col集合:"+col);// col集合:[范冰冰, 李冰冰, 林心如, 赵薇]
      // 清空集合中所有的元素
          col.clear();
          System.out.println("col集合:"+col);// col集合:[]

### 3.把给定的对象在当前集合中删除 ###

//public boolean remove(E e): 把给定的对象在当前集合中删除。
     // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
    // 删除李冰冰这个元素
            col.remove("李冰冰");
            System.out.println("col集合:"+col);// col集合:[范冰冰, 林心如, 赵薇]

### 4.判断当前集合中是否包含给定的对象 ###

//public boolean contains(Object obj): 判断当前集合中是否包含给定的对象
     // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
          boolean res1 = col.contains("我");
            System.out.println("res1:"+res1);// false

### 5.判断当前集合是否为空 ###

//public boolean isEmpty(): 判断当前集合是否为空。
     // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
       //判断当前集合是否为空。(判断集合中是否有元素)
            boolean res3 = col.isEmpty();
            System.out.println("res3:"+res3);// false

### 6.返回集合中元素的个数 ###

//public int size(): 返回集合中元素的个数。
     // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
      // 获取集合中元素的个数
            System.out.println("集合中元素的个数:"+col.size());// 3

### 7.把集合中的元素，存储到数组中 ###

//public Object[] toArray(): 把集合中的元素，存储到数组中
    
     // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
             // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
    
    // 把集合中的元素，存储到数组中
            Object[] arr = col.toArray();
            System.out.println(Arrays.toString(arr));// [范冰冰, 李冰冰 林心如]

# 三、迭代器 #

## 一、解释 ##

在程序开发中，经常需要遍历单列集合中的所有元素。针对这种需求，JDK专门提供了一个接口`java.util.Iterator`。  
**迭代**：即Collection集合元素的通用获取方式。在取元素之前先要判断集合中有没有元素，如果有，就把这个元素取出来，继续再判断，如果还有就再取出来。一直把集合中的所有元素全部取出。这种取出方式专业术语称为迭代。

## 二、写法 ##

//Collection集合提供了一个获取迭代器的方法：
    //`public Iterator iterator(): 获取集合对应的迭代器，用来遍历集合中的元素的。
    
     // Iterator接口的常用方法
    
     //public E next():返回迭代的下一个元素。
     //public boolean hasNext():有元素可以迭代，则返回 true。
    Collection<String> col = new ArrayList<>();
    
            // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
    
            // 获取迭代器对象
            Iterator<String> it = col.iterator();
    
            // 循环判断集合中是否有元素可以迭代
            while (it.hasNext()){ 
                // 说明有元素可以迭代
                String e = it.next();
                System.out.println(e);
            }

## 三、迭代器的注意事项 ##

*  在进行集合元素获取时，如果集合中已经没有元素可以迭代了，还继续使用迭代器的next方法，将会抛出java.util.NoSuchElementException没有集合元素异常。如果还想继续迭代集合，需要重新获取一个迭代器
 *  在进行集合元素迭代时，如果添加或移除集合中的元素 , 将无法继续迭代 , 将会抛出ConcurrentModificationException并发修改异常，但是删除可以解决，不用集合的删除方法，而是使用迭代器的删除方法就可以删除元素。添加暂无法解决。

// 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
    
            // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
    
            // 获取集合的迭代器对象
            Iterator<String> it = col.iterator();
    // 循环判断集合中是否有元素可以迭代
        while (it.hasNext()) { 
            // 获取可以迭代的元素
            String e = it.next();
            System.out.println(e);
            // 添加元素到集合中
            //col.add("高圆圆");// 报异常
            // 删除元素
            //col.remove(e);// 报异常
            // 如果迭代出来的元素是李冰冰,就删除
            if (e.equals("李冰冰")){ 
                it.remove();
            }
        }

## 四、迭代器原理 ##

当遍历集合时，首先通过调用t集合的iterator()方法获得迭代器对象，然后使用hashNext()方法判断集合中是否存在下一个元素，如果存在，则调用next()方法将元素取出，否则说明已到达了集合末尾，停止遍历元素。  
 Iterator迭代器对象在遍历集合时，内部采用指针的方式来跟踪集合中的元素。在调用Iterator的next方法之前，迭代器的索引位于第一个元素之前，不指向任何元素，当第一次调用迭代器的next方法后，迭代器的索引会向后移动一位，指向第一个元素并将该元素返回，当再次调用next方法时，迭代器的索引会指向第二个元素并将该元素返回，依此类推，直到hasNext方法返回false，表示到达了集合的末尾，终止对元素的遍历。

# 四、增强for循环 #

## 一、解释 ##

增强for循环(也称for each循环)是**JDK1.5**以后出来的一个高级for循环，专门用来遍历数组和集合的。它的内部原理其实是个Iterator迭代器，所以在遍历的过程中，不能对集合中的元素进行增删操作。

## 二、写法 ##

/*for(元素的数据类型 变量 : Collection集合or数组){ //写操作代码 }*/
    // 创建Collection集合对象,限制集合中元素的类型为String
            Collection<String> col = new ArrayList<>();
            // 往col集合中添加元素
            col.add("范冰冰");
            col.add("李冰冰");
            col.add("林心如");
            col.add("赵薇");
            // 增强for循环遍历
            for (String e : col) { 
                System.out.println(e);
            }
           
         String[] arr = { "范冰冰","李冰冰","林心如", "赵薇"};
            for (String e : arr){ 
                System.out.println(e);
            }
    // 增强for循环快捷键: 数组名\集合名.for

## 三、使用注意点 ##

*  增强for循环必须有被遍历的目标，目标只能是Collection或者是数组；
 *  增强for（迭代器）仅仅作为遍历操作出现，不能对集合进行增删元素操作，否则抛出ConcurrentModificationException并发修改异常

# 五、泛型 #

## 一、解释 ##

表示一种未知的数据类型,在使用的时候确定其具体的数据类型。泛型的作用是在创建对象时，将未知的类型确定具体的类型。当没有指定泛型时，默认类型为Object类型。  
在创建集合的时候，<>里不写数据类型，可以什么都存，但是在取出来的时候，会出现转换异常。要是指定了类型，只能存储着一种数据了。这时候就需要泛型。在定义的时候，使用泛型，而在使用的时候确定其具体的类型。

## 二、定义和使用泛型的类写法 ##

/*修饰符 class 类名<代表泛型的变量> { } 代表泛型的变量: 可以是任意字母 例如: T,E... class ArrayList<E>{ public boolean add(E e){ } public E get(int index){ } .... } 当E确定后，方法的返回值，变量的类型就都确定了。即E是String，成员变量和方法的返回值和参数都是String了 相当于是一个模板。 */
    public class MyArrayList<E> { 
        //定义成员变量
        E e;
        
        int age;
        String name;
     
     //定义成员方法，不知道返回类型和参数类型，这时候泛型就当于一个占位。在使用的时候再确定。
        public E method(E e){ 
            return e;
        }
    
    }
    //创建String类的集合
    MyArrayList<String> list1 = new MyArrayList<>();
           list.age = 10
            list.name ="世界"
            list1.e = "itheima";
            String res1 = list1.method("itcast");
            System.out.println("res1:"+res1);// itcast
            
            //创建Integer类型的集合
     MyArrayList<Integer> list2 = new MyArrayList<>();
            list2.e = 100;
            Integer res2 = list2.method(10);
            System.out.println("res2:"+res2);// 10

## 三、定义和使用含有泛型的方法的写法 ##

//修饰符 <代表泛型的变量> 返回值类型 方法名(参数){ }
    //
    
      // 定义含有泛型的方法
      //要是类没有使用泛型，这里不能直接光写T，因为不是定义在泛型类中
        public static <T> T method1(T t){ 
            return t;
        }
    Integer i1 = method1(100);// 指定泛型的具体数据类型为Integer
            System.out.println(i1);// 100
      String s = method1("itheima");// 指定泛型的具体数据类型为String
            System.out.println(s);// itheima

## 四、定义和使用含有泛型的接口的写法 ##

//修饰符 interface接口名<代表泛型的变量> { }
    
    public interface IA<E> { 
    
        public abstract void method1(E e);
    
        public default E method2(E e){ 
            return e;
        }
    }

## 五、实现含有泛型接口的写法 ##

### 1、定义实现类时确定泛型的类型 ###

// 通过实现类的方式确定接口泛型的具体数据类型
    public class Imp1 implements IA<String> { 
        @Override
        public void method1(String s) { 
    
        }
        @Override
        public String method2(String s) { 
            return null;
        }
    }
       // 创建实现类对象的时候确定接口泛型的具体数据类型
            Imp2<String> imp1 = new Imp2<>();
            imp1.method1("itheima");
            String s1 = imp1.method2("itcast");
            System.out.println(s1);// itcast

### 2.始终不确定泛型的类型，直到创建对象时，确定泛型的类型 ###

// 实现类实现接口的时候不确定接口泛型的具体数据类型,
    // 而是创建实现类对象的时候确定接口泛型的具体数据类型
    public class Imp2<E> implements IA<E> { 
        @Override
        public void method1(E e) { 
            System.out.println("实现类 method1");
        }
    
        @Override
        public E method2(E e) { 
            return e;
        }
    }
       Imp2<Integer> imp2 = new Imp2<>();
            imp2.method1(100);
            Integer i = imp2.method2(100);
            System.out.println(i);// 100

## 六、小结 ##

泛型：定义的时候表示一种未知的数据类型,在使用的时候确定其具体的数据类型。  
使用含有泛型的类: 创建该类对象的时候,指定泛型的具体数据类型  
使用含有方向的方法: 调用该方法的时候,确定泛型的具体数据类型  
使用含有泛型的接口:  
1.创建实现类实现接口的时候,指定泛型的具体数据类型  
2.创建实现类实现接口的时候,不知道泛型的具体数据类型,而是创建实现类对象的时候指定泛型的具体数据类型

# 六、泛型通配符 #

## 一、解释 ##

不知道使用什么类型来接收的时候,此时可以使用?,?表示未知通配符。此时只能接受数据,不能往该集合中存储数据。

## 二、写法 ##

public class Test { 
        public static void main(String[] args) { 
            // 关系:String继承Object,Integer继承Number,Number继承Objec
            ArrayList<Object> list1 = new ArrayList<>();
            ArrayList<String> list2 = new ArrayList<>();
            ArrayList<Integer> list3 = new ArrayList<>();
            ArrayList<Number> list4 = new ArrayList<>();
            
            list2.add("itheima");
    
            //method1(list1);
            method1(list2);
            //method1(list3);
            //method1(list4);
    
            //method2(list1);
            method2(list2);
            //method2(list3);
            //method2(list4);
    
            // 泛型没有多态
            //ArrayList<Object> list = new ArrayList<String>();// 编译报错
        }
        // 定义一个方法,可以接收以上4个集合
        public static void method1(ArrayList list){ 
            Object obj = list.get(0);
            list.add("jack");
            System.out.println("obj:"+obj);// itheima
            System.out.println("list:"+list);// [itheima, jack]
        }
    
        public static void method2(ArrayList<?> list){ 
            Object obj = list.get(0);
            //list.add("jack");// 编译报错，不能存储数据，但是可以获取数据
            System.out.println("obj:"+obj);// itheima
            System.out.println("list:"+list);// [itheima]
        }
    }

# 七、受限泛型 #

## 一、解释 ##

之前设置泛型的时候，实际上是可以任意设置的，只要是类就可以设置。但是在JAVA的泛型中可以指定一个泛型的**上限**和**下限**。

## 二、写法 ##

public class Test { 
        public static void main(String[] args) { 
            /* 通配符高级使用----受限泛型: 上限: <? extends 类名> 只能接收该类类型或者其子类类型 下限: <? super 类名> 只能接收该类类型或者其父类类型 */
            // 关系:String继承Object,Integer继承Number,Number继承Objec
            ArrayList<Object> list1 = new ArrayList<>();
            ArrayList<String> list2 = new ArrayList<>();
            ArrayList<Integer> list3 = new ArrayList<>();
            ArrayList<Number> list4 = new ArrayList<>();
            
            method1(list1);
            method1(list2);
            method1(list3);
            method1(list4);
            
            //method2(list1);// 编译报错
            //method2(list2);// 编译报错
            method2(list3);
            method2(list4);
    
    
            method3(list1);
            //method3(list2);// 编译报错
            method3(list3);
            method3(list4);
        }
    
        // 定义一个方法,只可以接收以上list3和list4集合
        public static void method2(ArrayList<? extends Number> list){ 
    
        }
        
        // 定义一个方法,只可以接收以上list3和list4,list1集合
        public static void method3(ArrayList<? super Integer> list){ 
    
        }
        
        // 定义一个方法,可以接收以上4个集合
        public static void method1(ArrayList<?> list){ 
           
        }
        // 定义一个方法,可以接收以上4个集合
        public static void method(ArrayList list){ 
    
        }
    }

# 八、数据结构 #

## 一、解释 ##

数据结构 : **其实就是存储数据和表示数据的方式**。常见的数据结构：**堆栈、队列、数组、链表和红黑树**。

## 二、堆栈结构 ##

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

*  **先进后出**（即，存进去的元素，要在后它后面的元素依次取出后，才能取出该元素）。例如，子弹压进弹夹，先压进去的子弹在下面，后压进去的子弹在上面，当开枪时，先弹出上面的子弹，然后才能弹出下面的子弹。
 *  **栈的入口、出口的都是栈的顶端位置**。
 *  **压栈**：就是存元素。即，把元素存储到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置。
 *  **弹栈**：就是取元素。即，把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置。

## 三、队列结构 ##

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

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

## 四、数组结构 ##

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

*  **查找元素快**：通过索引，可以快速访问指定位置的元素
 *  **增删元素慢**
 *  **指定索引位置增加元素**：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。
 *  **指定索引位置删除元素**：需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。

## 五、链表结构 ##

**linked list**,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域，最后一个节点的指针域存储的是null。我们常说的链表结构有单向链表与双向链表。单向链表只有向下一个的指针域，双向链表一个节点有两个指针与，存储的两边的节点地址的指针域。注意链表和单双列集合的区别  
特点：

*  多个结点之间，通过地址进行连接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。
 *  查找元素慢：想查找某个元素，需要通过连接的节点，依次向后查找指定元素。
 *  增删元素快：只需要修改链接下一个元素的地址值即可

## 六、树结构 ##

特点：

1.  每一个节点有零个或者多个子节点
2.  没有父节点的节点称之为根节点，一个树最多有一个根节点。
3.  每一个非根节点有且只有一个父节点
4.  子节点可以超过2个。  
    ![树][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70]

<table> 
 <thead> 
  <tr> 
   <th>名词</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>节点</td> 
   <td>指树中的一个元素</td> 
  </tr> 
  <tr> 
   <td>节点的度</td> 
   <td>节点拥有的子树的个数，二叉树的度不大于2</td> 
  </tr> 
  <tr> 
   <td>叶子节点</td> 
   <td>度为0的节点，也称之为终端结点</td> 
  </tr> 
  <tr> 
   <td>高度</td> 
   <td>叶子结点的高度为1，叶子结点的父节点高度为2，以此类推，根节点的高度最高</td> 
  </tr> 
  <tr> 
   <td>层</td> 
   <td>根节点在第一层，以此类推</td> 
  </tr> 
  <tr> 
   <td>父节点</td> 
   <td>若一个节点含有子节点，则这个节点称之为其子节点的父节点</td> 
  </tr> 
  <tr> 
   <td>子节点</td> 
   <td>子节点是父节点的下一层节点</td> 
  </tr> 
  <tr> 
   <td>兄弟节点</td> 
   <td>拥有共同父节点的节点互称为兄弟节点</td> 
  </tr> 
 </tbody> 
</table>

### 1、二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 1]

解释：  
如果树中的每个节点的子节点的个数不超过2，那么该树就是一个二叉树。

### 2.二叉查找树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 2]

特点：

1.  左子树上所有的节点的值均小于等于他的根节点的值
2.  右子树上所有的节点值均大于或者等于他的根节点的值
3.  每一个子节点最多有两个子树
4.  遍历获取元素的时候可以按照"左中右"的顺序进行遍历；这样去取出的数是从小到大的
5.  获取元素时有前序：中左右，中序：左中右，后序：左右中，不同的方式取，取的顺序是不一样的。
6.  注意：二叉查找树存在的问题：会出现"瘸子"的现象，影响查询效率  
    ![6.][]

### 3.平衡二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 3]

**1.解释：**  
为了避免出现"瘸子"的现象，减少树的高度，提高我们的搜素效率，又存在一种树的结构：“平衡二叉树”  
规则：它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

**2.旋转**  
在构建一棵平衡二叉树的过程中，当有新的节点要插入时，检查是否因插入后而破坏了树的平衡，如果是，则需要做旋转去改变树的结构。旋转是自动完成的。

**3.左旋**  
左旋就是将节点的右支往左拉，右子节点变成父节点，并把晋升之后多余的左子节点出让给降级节点的右子节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 4]

**4.右旋**  
将节点的左支往右拉，左子节点变成了父节点，并把晋升之后多余的右子节点出让给降级节点的左子节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 5]

**5.左左**  
左左：只需要做一次右旋就变成了平衡二叉树。

**6.左右**  
左右先做一次分支的左旋，再做一次树的右旋，才能变成平衡二叉树。

**7.右右**  
右右：只需要做一次左旋就变成了平衡二叉树。

**8.右左**  
先做一次分支的右旋，再做一次数的左旋，才能变成平衡二叉树。

### 4、红黑树 ###

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构，它是在1972年由Rudolf Bayer发明的，当时被称之为平衡二叉B树，后来，在1978年被Leoj.Guibas和Robert Sedgewick修改为如今的"红黑树"。它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色，可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过"红黑树的特性"进行实现的；  
**红黑树的特性：**

1.  每一个节点或是红色的，或者是黑色的。
2.  根节点必须是黑色
3.  每个叶节点(Nil)是黑色的；（如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点）
4.  如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
5.  对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 6]  
在进行元素插入的时候，和之前一样； 每一次插入完毕以后，使用黑色规则进行校验，如果不满足红黑规则，就需要通过变色，左旋和右旋来调整树，使其满足红黑规则；

*  红黑树的作用: 提高搜索效率
 *  表示集合的类有很多,但是每个集合存储数据的的数据结构不同,所以每个集合有各自的特点,
 *  ArrayList集合: 查询快,增删慢 —>存储数据的数据结构是数组
 *  LinkedList集合: 查询慢,增删快—>存储数据的数据结构是链表

# 九、list接口 #

## 一、解释 ##

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

## 二、特点 ##

1.  它是一个元素存取有序的集合。例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）。
2.  它是一个带有索引的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）。
3.  集合中可以有重复的元素。
4.  .ArrayList类，该类中的方法都是来自List中定义。是list接口的子类。

## 三、list接口常用方法 ##

List作为Collection集合的子接口，不但继承了Collection接口中的全部方法，而且还增加了一些根据元素索引来操作集合的特有方法。怎么看是否是新增方法，看方法需不需要给索引，需要索引的方法是list新增的，Collection不可能有索引，因为它要给list和set提供方法，而set接口是没有索引的。

### 1.将指定的元素，添加到该集合中的指定位置上。 ###

//public void add(int index, E element): 将指定的元素，添加到该集合中的指定位置上。
     // 创建list集合,限制集合中元素的类型为String类型
            List<String> list = new ArrayList<>();
            // 往集合中添加一些元素
               list.add("王老师");
               list.add("李老师");
             System.out.println(list);// [王老师, 李老师]
              // 在索引为1的位置添加张老师
            list.add(1, "张老师");
            System.out.println(list);// [王老师, 张老师，李老师]
            //两个add是不同的方法

### 2.返回集合中指定位置的元素。 ###

//public E get(int index):返回集合中指定位置的元素。
       List<String> list = new ArrayList<>();
            // 往集合中添加一些元素
               list.add("王老师");
               list.add("李老师");
             System.out.println(list);// [王老师, 李老师]
              // 在索引为1的位置添加张老师
            list.add(1, "张老师");// [王老师, 张老师，李老师]
       // 获取索引为1的元素
            System.out.println("索引为1的元素:"+list.get(1));// 张老师

### 3.移除列表中指定位置的元素, 返回的是被移除的元素。 ###

List<String> list = new ArrayList<>();
            // 往集合中添加一些元素
               list.add("王老师");
               list.add("李老师");
             System.out.println(list);// [王老师, 李老师]
              // 在索引为1的位置添加张老师
            list.add(1, "张老师");// [王老师, 张老师，李老师]
           // 删除索引为1的老师
            String removeE = list.remove(1);
            System.out.println("被删除的元素:"+removeE);// 张老师

### 4.用指定元素替换集合中指定位置的元素,返回值的更新前的元素 ###

//public E set(int index, E element):用指定元素替换集合中指定位置的元素,返回值的更新前的元素
     // 创建list集合,限制集合中元素的类型为String类型
            List<String> list = new ArrayList<>();
            // 往集合中添加一些元素
               list.add("王老师");
               list.add("李老师");
             System.out.println(list);// [王老师, 李老师]
              // 在索引为1的位置添加张老师
            list.add(1, "张老师");// [王老师, 张老师，李老师]
          // 把索引为0的元素替换为赵老师
            String setE = list.set(0, "赵老师");
            System.out.println("被替换的元素:"+setE);// 张老师

# 十一、list接口的实现类 #

## 一、ArrayList集合 ##

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

## 二、LinkedList集合 ##

`java.util.LinkedList`集合数据存储的结构是链表结构。方便元素添加、删除的集合。LinkedList是一个双向链表,LinkedList提供了大量首尾操作的方法。

public class Test { 
        public static void main(String[] args) { 
            /* 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():从此列表所表示的堆栈处弹出一个元素。 removeFirst() - public void push(E e):将元素推入此列表所表示的堆栈。addFirst() */
            // 创建LinkedList集合,限制集合元素的类型为String类型
            LinkedList<String> list = new LinkedList<>();
    
            // 往集合中添加元素
            list.add("蔡徐坤");
            list.add("鹿晗");
            list.add("吴亦凡");
            System.out.println(list);// [蔡徐坤, 鹿晗, 吴亦凡]
    
            // 在集合的首尾添加一个元素
            list.addFirst("罗志祥");
            list.addLast("陈冠希");
            System.out.println(list);// [罗志祥, 蔡徐坤, 鹿晗, 吴亦凡, 陈冠希]
    
            // 获取集合的首尾元素
            String firstE = list.getFirst();
            String lastE = list.getLast();
            System.out.println("第一个元素是:"+firstE);// 罗志祥
            System.out.println("最后一个元素是:"+lastE);// 陈冠希
    
            // 删除首尾元素
            String removeFirst = list.removeFirst();
            String removeLast = list.removeLast();
            System.out.println("被删除的第一个元素是:"+removeFirst);// 罗志祥
            System.out.println("被删除的最后一个元素是:"+removeLast);// 陈冠希
            System.out.println(list);// [蔡徐坤, 鹿晗, 吴亦凡]
    
            // pop --->删除第一个元素
            String popE = list.pop();
            System.out.println("被删除的第一个元素是:"+popE);// 蔡徐坤
            System.out.println(list);// [鹿晗, 吴亦凡]
    
            // push --->添加一个元素在开头
            list.push("蔡徐坤");
            System.out.println(list); // [蔡徐坤, 鹿晗, 吴亦凡]
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70]: /images/20210813/18187a8e50f448e7a8f3cfd66c19a335.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 1]: /images/20210813/479096bae15443f480717de59a188c96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 2]: /images/20210813/79ee2ac9f38c44ff82886731e92ed445.png
[6.]: /images/20210813/a6e0945faa804c2aa63f7146fada6b1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 3]: /images/20210813/1f6cfd8a89bb474fa3b233087d426a15.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 4]: /images/20210813/851b551ea8b1438c98c2275acfde65de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 5]: /images/20210813/99f56beaaffe44e9873d81425224caf8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDU5ODM4_size_16_color_FFFFFF_t_70 6]: /images/20210813/b55e5a7df5854c47bf94888454ffb868.png