java基础-day16-list集合

List集合

1. List集合

1.1 List集合特征

特征:
    有序，可重复
有序:
    添加顺序和存储顺序一致
可重复:
    List集合中允许出现相同元素。

List 
--| ArrayList 可变长数组
--| LinkedList 双向链表
--| Vector 线程安全的可变长数组

1.2 List常用方法

增
    boolean add(E e);
        在集合末尾添加指定类型的元素对象
    boolean addAll(Collection<? extends E> e);
        在集合末尾添加另一个集合对象，要求参数集合中的元素是E类型本身或者E类型的
        子类，泛型的【上限】
    boolean add(int index, E e);
        在集合中指定下标位置添加指定E类型元素
    boolean addAll(int index, Collection<? extends E> e);
        在集合中指定下标位置添加另一个集合对象，求参数集合中的元素是E类型本身或者
        E类型的子类，泛型的【上限】
    
删
    remove(Object obj);
        删除指定元素
    removeAll(Collection<?> c);
        删除两个集合的交集
    retainAll(Collection<?> c);
        保留两个集合的交集
    clear();
        清空整个集合
    E remove(int index);
        删除指定下标的元素，返回值是被删除元素
改
    E set(int index, E e);
        使用指定元素替换指定下标元素，返回值类型是被替换的元素。
查
    int size();
        获取有效元素个数
    boolean isEmpty();
        判断当前集合是否为空
    boolean contains(Object obj);
        判断指定元素是否在集合中存在
    boolean containsAll(Collection<?> c);
        判断参数集合是不是当前集合的子集合
    Object[] toArray();
        集合中的所有元素全部转换成Object类型数组返回
    E get(int index);
        获取指定下标的元素
    int indexOf(Object obj);
        获取指定元素的下标位置
    int lastIndexOf(Object obj);
        获取指定元素最后一次出现的下标位置
    List<E> subList(int fromIndex, int toIndex);
        截取子List集合对象，要求从fromIndex开始操作，到toIndex截止，并且是要
        头不要尾 fromIndex <= n < toIndex

2. ArrayList 可变长数组 【重点】

2.1 ArrayList特征

1. ArrayList是一个可变长数组形式的数据存储方式。底层保存数据的是一个Object类型数组。该数组在调用无参数构造方法时，默认容量 
    private static final int DEFAULT_CAPACITY = 10;
    如果调用有参数构造方法，在合理范围以内按照用户指定的容量创建对应的底层数组

2. ArrayList因为底层存储数据的结构是一个Object类型数组
    查询快
    增删慢

3. ArrayList常用方法都是List接口对应方法。
    trimToSize();
        缩容方法
    ensureCapacity(int capacity);
        确认容量方法
    grow(int minCapacity);
        扩容方法
    rangeCheck(int index);
        下标范围验证方法

2.2 增删慢

增:
    1. 在指定位置添加元素，会导致从指定位置开始，之后的元素整体向后移动，移动过程【浪费时间】
    2. 如果底层数组容量不足，需要进行grow扩容操作，扩容操作过程中，需要进行数据的复制转移，该过程非常【浪费时间】
    3. 如果同时发生以上两种情况，蹦沙卡拉卡...

删:
    1. 删除指定下标的元素，会导致从指定位置开始，之后的元素整体向前移动，该过程非常【浪费时间】
    2. 删除数据过多的情况下，会导致空间浪费，会选择【时间换空间】

2.3 查询快

2.3.1 【补充知识点 内存地址】

内存地址:
    从内存第一个字节开始，到内存的最大内容。按照内存最小单位【字节】
    从0编号到最大值内存。每一个字节都有一个唯一编号！！！
    内存地址:
        32GB内存对于计算机所有的内存地址编号
        0x0 ~ 0x 7 FFFF FFFF
    
生活中的地址:
    航海中路60号
    黄河路60号
    对于快递员可以明确的送到快递
    
如果存在一个内存地址，CPU可以通过该地址直达目标！！！【效率极高！！！】

2.3.2 【补充知识点 null到底是个啥】

null 是内存编号为0x0内存，也就是整个计算机中第一个内存。
    0x0 null 不能读，不能写
    是收到系统保护的！！！只要存在任何一个程序读取或者写入数据到0x0 null
    直接杀死！！！Kill -9
    
    null不得调用任何的一个方法！！！

2.3.3 【补充知识点 数组内存地址图】

image.png

2.3.4 查询快的原因

1. ArrayList底层存储数据的是一个Object类型数组。
    需要通过下标方式获取对应的元素，这里可以计算对应下标元素的内存地址，直接跳转操作，效率较高

2. ArrayList是一个连续空间存储。

2.4 ArrayList源代码实现

增
    boolean add(E e);
        在集合末尾添加指定类型的元素对象
    boolean add(int index, E e);
        在集合中指定下标位置添加指定E类型元素
    
删
    remove(Object obj);
        删除指定元素
    clear();
        清空整个集合
    E remove(int index);
        删除指定下标的元素，返回值是被删除元素
改
    E set(int index, E e);
        使用指定元素替换指定下标元素，返回值类型是被替换的元素。
查
    int size();
        获取有效元素个数
    boolean isEmpty();
        判断当前集合是否为空
    boolean contains(Object obj);
        判断指定元素是否在集合中存在
    Object[] toArray();
        集合中的所有元素全部转换成Object类型数组返回
    E get(int index);
        获取指定下标的元素
    int indexOf(Object obj);
        获取指定元素的下标位置
    int lastIndexOf(Object obj);
        获取指定元素最后一次出现的下标位置
    MyList<E> subList(int fromIndex, int toIndex);
        截取子List集合对象，要求从fromIndex开始操作，到toIndex截止，并且是要
        头不要尾 fromIndex <= n < toIndex

3. LinkedList 双向链表结构

3.1 双向链表结构示意图

image.png

3.2 链表结构方法

boolean addFirst(E e);
    添加元素到链表开头
boolean addLast(E e);
    添加元素到链表末尾 ==> add(E e);
E getFirst();
    获取链表头元素
E getLast();
    获取链表尾元素
E removeFirst();
    删除链表头元素
E removeLast();
    删除链表尾元素

完成:
    1. 堆栈结构
        getLast removeLast addLast
    2. 队列结构
        getFirst removeFirst addLast