[数据结构与算法]集合与泛型（一）（day15）

一、 Collection集合

1.1 数组和集合的区别

• 相同点

  都是容器,可以存储多个数据

• 不同点

  • 数组的长度是不可变的,集合的长度是可变的

  • 数组可以存基本数据类型和引用数据类型

    集合**只能存引用数据类型,**如果要存基本数据类型,需要存对应的包装类

• 实例代码

package com.xu.test;

import java.util.ArrayList;
import java.util.Arrays;

public class Demo01 {
    public static void main(String[] args) {
        // 数组可以存基本数据类型和引用数据类型
        int[] array1 = {1, 2, 3};
        String[] array2 = {"a", "b", "c"};
        System.out.println(Arrays.toString(array1));
        System.out.println(Arrays.toString(array2));

        //集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类
        ArrayList<String> al1 = new ArrayList<>();
        al1.add("a");
        al1.add("b");
        al1.add("c");
        System.out.println(al1);
        ArrayList<Integer> al2 = new ArrayList<>();
        al2.add(1);
        al2.add(2);
        al2.add(3);
        System.out.println(al2);
    }
}

1.2 集合类体系结构

1.3 Collection 集合概述和使用

• Collection集合概述

  • 是单例集合的顶层接口,它表示一组对象,这些对象也称为Collection的元素
  • JDK 不提供此接口的任何直接实现.它提供更具体的子接口(如Set和List)实现

  

• 创建Collection集合的对象

  • 多态的方式
  • 具体的实现类ArrayList

• Collection集合常用方法

  方法名	说明
  boolean add(E e)	添加元素
  boolean remove(Object o)	从集合中移除指定的元素
  boolean removeIf(Object o)	根据条件进行移除
  void clear()	清空集合中的元素
  boolean contains(Object o)	判断集合中是否存在指定的元素
  boolean isEmpty()	判断集合是否为空
  int size()	集合的长度，也就是集合中元素的个数

• 示例代码

package com.xu.test;

import java.util.ArrayList;
import java.util.Collection;

public class Demo02 {
    public static void main(String[] args) {
        // 以多态的方式声明一跟collection对象
        Collection<String> collection = new ArrayList<>();
        // boolean add(E e)  添加元素
        boolean result = collection.add("aaa");
        collection.add("aaa");
        System.out.println(result);
        System.out.println(collection);

        // boolean remove(Object o)  从集合中移除指定的元素
        collection.add("bbb");
        String s = "aaa";
        boolean remove = collection.remove(s);
        System.out.println(remove);
        System.out.println(collection);

        // boolean removeIf(Object o)  根据条件进行移除
        collection.add("cccc");
        collection.removeIf(
                (String ss) -> {
                    // 删除集合内字符串长度为3的元素
                    return ss.length() == 3;
                }
        );
        System.out.println(collection);

        // void   clear()  清空集合中的元素
        collection.clear();
        System.out.println(collection);

        // boolean contains(Object o)  判断集合中是否存在指定的元素
        collection.add("cccc");
        boolean cccc = collection.contains("cccc");
        System.out.println(cccc);  //true

        // boolean isEmpty()  判断集合是否为空
        boolean empty = collection.isEmpty();
        System.out.println(empty);

        // int   size()  集合的长度，也就是集合中元素的个数
        collection.add("111");
        int size = collection.size();
        System.out.println(size);
        
    }
}

1.4 Collection集合的遍历

• 迭代器介绍

  • 迭代器,集合的专用遍历方式
  • Iterator iterator(): 返回此集合中元素的迭代器,通过集合对象的iterator()方法得到

• Iterator中的常用方法

  ? boolean hasNext(): 如果仍有元素可以迭代，则返回 true。
  ? E next(): 返回迭代的下一个元素。

• Collection集合的遍历

package com.xu.test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class Demo03 {
    public static void main(String[] args) {
        // 以多态的方式声明一跟collection对象
        Collection<String> collection = new ArrayList<>();
        // 添加一些元素
        collection.add("Hello");
        collection.add(" world");
        collection.add(" and");
        collection.add(" java!");

        Iterator<String> iterator = collection.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            System.out.print(next);
        }

    }
}

• 迭代器中删除的方法

  ? void remove(): 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。

• 示例代码

package com.xu.test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

public class Demo03 {
    public static void main(String[] args) {
        // 以多态的方式声明一跟collection对象
        Collection<String> collection = new ArrayList<>();
        // 添加一些元素
        collection.add("Hello");
        collection.add(" world");
        collection.add(" and");
        collection.add(" java!");

        Iterator<String> iterator = collection.iterator();
        while (iterator.hasNext()) {
            String next = iterator.next();
            if(" java!".equals(next)){
                iterator.remove();
            }
        }
        System.out.println(collection);

    }
}

1.5 增强for循环

• 介绍

  • 它是JDK5之后出现的,其内部原理是一个Iterator迭代器

  • 实现Iterable接口的类才可以使用迭代器和增强for

  • 简化数组和Collection集合的遍历

• 格式

  ? for(集合/数组中元素的数据类型 变量名 : 集合/数组名) {

  ? // 已经将当前遍历到的元素封装到变量中了,直接使用变量即可

  ? }

• 示例代码

package com.xu.test;

import java.util.ArrayList;

public class Demo04 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");

        for (String s : list) {
            System.out.print(s);
        }
    }
}

注：

1. 数据类型一定是集合或者数组中元素的类型
2. s仅仅是一个变量名而已,在循环的过程中,依次表示集合或者数组中的每一个元素
3. list就是要遍历的集合或者数组

二、List集合

2.1 List集合的概述和特点

• List集合的概述
  • 有序集合,这里的有序指的是存取顺序
  • 用户可以精确控制列表中每个元素的插入位置,用户可以通过整数索引访问元素,并搜索列表中的元素
  • 与Set集合不同,列表通常允许重复的元素
• List集合的特点
  • 存取有序
  • 可以重复
  • 有索引

2.2 List集合的特有方法

• 示例代码

package com.xu.test;

import java.util.ArrayList;
import java.util.List;

public class Demo05 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        // void add(int index,E element)  在此集合中的指定位置插入指定的元素
        list.add(0, "666");
        list.add(0, "777");
        System.out.println(list);
        System.out.println("-----------------");

        // E remove(int index)  删除指定索引处的元素，返回被删除的元素
        String remove = list.remove(0);
        System.out.println(remove);
        System.out.println(list);
        System.out.println("-----------------");
        // E set(int index,E element)  修改指定索引处的元素，返回被修改的元素
        String s = list.set(0, "888");
        System.out.println(s);
        System.out.println(list);
        System.out.println("-----------------");

        // E get(int   index)  返回指定索引处的元素
        String s1 = list.get(0);
        System.out.println(s1);
    }
}

三、数据结构（后续展开）

3.1 数据结构之栈和队列

• 栈结构

  ? 先进后出

• 队列结构

  ? 先进先出

3.2 数据结构之数组和链表

• 数组结构

  ? 查询快、增删慢

• 队列结构

  ? 查询慢、增删快

四、List集合的实现类

4.1 List集合子类的特点

• ArrayList集合

  ? 底层是数组结构实现，查询快、增删慢

• LinkedList集合

  ? 底层是链表结构实现，查询慢、增删快

4.2 LinkedList集合的特有功能

• 特有方法

  方法名	说明
  public void addFirst(E e)	在该列表开头插入指定的元素
  public void addLast(E e)	将指定的元素追加到此列表的末尾
  public E getFirst()	返回此列表中的第一个元素
  public E getLast()	返回此列表中的最后一个元素
  public E removeFirst()	从此列表中删除并返回第一个元素
  public E removeLast()	从此列表中删除并返回最后一个元素

• 示例代码

package com.xu.test;

import java.util.LinkedList;

public class Demo06 {
    public static void main(String[] args) {
        LinkedList<String> ll = new LinkedList<>();
        // public void addFirst(E e)  在该列表开头插入指定的元素
        ll.addFirst("222");
        ll.addFirst("111");
        System.out.println(ll);
        System.out.println("-------");
        // public void addLast(E e)  将指定的元素追加到此列表的末尾
        ll.addLast("333");
        System.out.println(ll);
        System.out.println("-------");
        // public E getFirst()  返回此列表中的第一个元素
        String first = ll.getFirst();
        System.out.println(first);
        System.out.println("-------");

        // public   E getLast()  返回此列表中的最后一个元素
        String last = ll.getLast();
        System.out.println(last);
        System.out.println("-------");
        // public E removeFirst()  从此列表中删除并返回第一个元素
        String s = ll.removeFirst();
        System.out.println(s);
        System.out.println("-------");

        // public   E removeLast() 从此列表中删除并返回最后一个元素
        String s1 = ll.removeLast();
        System.out.println(s1);

    }
}

五、泛型

5.1 泛型概述

• 泛型的介绍

  ? 泛型是JDK5中引入的特性，它提供了编译时类型安全检测机制

• 泛型的好处

  1. 把运行时期的问题提前到了编译期间
  2. 避免了强制类型转换

• 泛型的定义格式

  • <类型>: 指定一种类型的格式.尖括号里面可以任意书写,一般只写一个字母.例如:
  • <类型1,类型2…>: 指定多种类型的格式,多种类型之间用逗号隔开.例如: <E,T> <K,V>

5.2 泛型类

• 定义格式

  修饰符 class 类名<类型> {  }
  

• 示例代码

  • 泛型类

  public class Demo07<T> {
      
      private T t;
  
      public T getT() {
          return t;
      }
  	// 泛型类中泛型方法可以不声明<T>
      public void setT(T t) {
          this.t = t;
      }
  }
  

5.3 泛型方法

• 定义格式

  修饰符 <类型> 返回值类型 方法名(类型 变量名) {  }
  

• 示例代码

  • 带有泛型方法的类

    public class Demo08 {
        // 普通类中要先声明时泛型方法
        public <T> void show(T t) {
            System.out.println(t);
        }
    }
    

5.4 泛型接口

• 定义格式

  修饰符 interface 接口名<类型> {  }
  

• 示例代码

  • 泛型接口

    public interface Demo09<T> {
        void show(T t);
    }
    

  • 泛型接口实现类1

    ? 定义实现类时,定义和接口相同泛型,创建实现类对象时明确泛型的具体类型

    public class Demo10<T> implements Demo09<T> {
        @Override
        public void show(T t) {
            System.out.println(t);
        }
    }
    

  • 泛型接口实现类2

    ? 定义实现类时,直接明确泛型的具体类型

    public class Demo11 implements Demo09<Integer>{
         @Override
         public void show(Integer t) {
              System.out.println(t);
         }
    }
    

5.5 类型通配符

• 类型通配符: <?>

  • ArrayList<?>: 表示元素类型未知的ArrayList,它的元素可以匹配任何的类型
  • 但是并不能把元素添加到ArrayList中了,获取出来的也是父类类型

• 类型通配符上限: <? extends 类型>

  • ArrayListList <? extends Number>: 它表示的类型是Number或者其子类型

• 类型通配符下限: <? super 类型>

  • ArrayListList <? super Number>: 它表示的类型是Number或者其父类型

• public static void method (ArrayList<? extends Number> list){}

六、ArrayList和LinkedList底层原码解析图

• ArrayList

• LinkedList