[数据结构与算法]List的使用

1. 集合类体系

2. 常见方法

2.1 List 线性表

官方文档

2.1.1 add(E e)

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        System.out.println(list);
    }

[1, 2]

我们 new 了一个 ArrayList 对象
查看一下 ArrayList 对象

我们发现里边有一个 不带参数的构造方法

this.elementData 是一个 Object 的数组，并未初始化，只是一个变量

1. ArrayList底层是一个数组
2. add 方法默认是放到了这个数组的最后位置

思考： 这个数组有多大呢？
看到 DEFAULTCAPACITY_EMPTY_ELEMENTDATA;, 又是默认值，又是空，又是元素。

我们再查看 DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

发现，它默认是一个 空数组, 那么问题来了，空数组是如何进行 add 尾插而没有发生数组越界异常呢?

点击 add 后, 发现我们调用的是 List 类的方法；而我们想要看的是 ArrayList 类的 add 方法我们去 ArrayList 类中查找:

ArrayList 类中在按住 command+7

找左下角 Structre 中的 add 方法
elementData[size++] = e;【size 就相当于前面顺序表中的 usedSize 】, 分析得出结论: 一定是放在数组的末尾的

我们查看 size

发现它是 ArrayList 的类成员属性，由于是 int型，所以默认值为 0
所以 ensureCapacityInternal(size + 1) 中传入的就是 1

再查看 ensureCapacityInternal(size + 1);【后续的形参传递注意仔细看】

进来之后我们在看外部的 calculateCapacity 函数

进来之后我们发现 if判断是相等的, 所以就会返回 Math.max(DEFAULT_CAPACITY, minCapacity 我们查看 DEFAULT_CAPACITY 是多少

发现默认值是 10
那么 Math.max(DEFAULT_CAPACITY, minCapacity 就会是 10
那么 calculateCapacity 就会返回 10

再查看最外部的 ensureExplicitCapacity 函数

发现有一个 modCount 变量为 0 值

if (minCapacity - elementData.length > 0)// minCapacity=10， elementData.length = 0
	grow(minCapacity);

所以会进入 grow 函数

再查看 grow 函数

发现它是1.5倍扩容增长的
我们在查看下边的if判断代码: if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);

如果当前扩容的容量比最大容量还大【Integer的最大值 - 8】，就让它使用 hugeCapacity 函数进行扩容

一般 grow 函数用在线性表中代表的是扩容

分析完 add 的源码后我们在代入参数看看到底是如何一步一步扩容的


这里一定要注意不能直接通过 ctrl+左键进入 add 函数：进入的是 List 的 add 而不是 ArrayList 的 add
因此我们需要在 ArrayList 类structre【command+7（alt+7）】中找 add 方法


至此我们发现是很正常的尾插操作
下一步我们应该思考的是一个 0 长度的数组是怎么扩容的








结论

当只是 List<Integer> lis = new ArrayList<>(); 实则此时的 list 的大小是 0, 当第一次 add 的时候最终走到了 grow 扩容函数就变为了 10；如果 10 个放满就会是 1.5倍扩容

2.1.2 addAll(Collection<? extends E> c)

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        List<Integer> list1 = new ArrayList<>();
        list1.addAll(list);
        list1.add(3);
        System.out.println(list1);
    }

[1, 2, 3]

解释：Collection<? extends E>c

代表传过来的参数, 是实现了 Collection 接口的, 然后这个集合类对象, 一定是当前 List 指定的类型或者指定类型的子类

假设 E 为 Person 类，则 传递的参数可以是 Student 可以是 Teacher 等 Person 的子类的意思

2.1.3 remove(int index)

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        System.out.println(list.remove(1));// 删除 1 下标
        System.out.println(list.remove(Integer.valueOf(1)));// 删除遇到的第一个 1 对象
        System.out.println(list);
    }

3
true
[3, 1, 2, 2]

2.2.4 get(int index)

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        System.out.println(list.get(1));
    }

3

2.2.5 set(int index, E e)

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        System.out.println(list.set(1, 0b1111));// 返回 1 下标的值后再做修改
        System.out.println(list);
    }

3
[3, 15, 1, 1, 2, 2]

2.2.6 clear()

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        list.clear();
        System.out.println(list);
    }

[]

2.2.7 indexOf(Object o)

   public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        System.out.println(list.indexOf(1));// 返回 1 的下标
        System.out.println(list.indexOf(Integer.valueOf(1)));
    }

2
2

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        System.out.println(list.lastIndexOf(1));// 最后一个 1 的下标
        System.out.println(list.lastIndexOf(Integer.valueOf(1)));
    }

3
3

2.2.8 sublist(int start, int end)

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(3);
        list.add(3);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(2);
        List<Integer> list1 = list.subList(0, list.size()>>1);
        System.out.println(list1);
        list1.set(0, 0);
        System.out.println(list);
        System.out.println(list1);
    }

[3, 3, 1]
=========
[0, 3, 1, 1, 2, 2]
[0, 3, 1]

并不是发生了 牵拷贝 而是通过引用修改了另一个引用指向的对象

2.2 ArrayList 顺序表

官方文档

2.2.1 **ArrsyList()**无参初始化

2.2.2 **ArrayList(int initcapacity)**确定容量初始化

2.2.3 ArrayList<Collection? extends E>c 上边界限定

2.3 LinkedList 链表

官方文档

2.3.1 LinkedList() | 无参构造

public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        LinkedList<Integer> list1 = new LinkedList<>();
    }

由于是链表，所以没有整数形参。只有两种创建方式

2.2.3.2 LinkedList(Collection <? extends E>c)上边界限定

    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        LinkedList<Integer> list1 = new LinkedList<>();
        LinkedList<Integer> list2 = new LinkedList<>(list);
        LinkedList<Integer> list3 = new LinkedList<>(list1);
        LinkedList<Integer> list4 = new LinkedList<>(list2);
    }

注意

1. 数组和链表的区别：内存空间连续，数组只能访问
2. 顺序表和链表的区别：内存空间连续，增删查改效率问题
3. ArrayList 和 LinkedList的区别：LinkedList 底层是一个双向链表【目录一的体系】