Java笔记——集合_List

2024年10月19日

1 Collection


Collection是其他类的父接口，是更广泛的类别，包含了所有集合类型，本身不提供实现，其他如List、Set等等都继承该类

<E>为泛型，表示该集合中存放的数据类型，注意必须是引用数据类型(如String)，而不能是基本数据类型(如string)

Collection定义了一些基本的操作方法，比如添加元素 add()，删除元素remove()，检查集合是否为空isEmpty()等等，确保集合行为的一致性

初始化集合:

   Collection<String> collection = new ArrayList<>();

增加元素:

collection.add("111");
collection.add("222");
System.out.println(collection);

删除数组中首个匹配到的元素:

collection.remove("111");
System.out.println(collection);

复制集合:

Collection<String> collection1 = new ArrayList<>(collection);
System.out.println(Objects.equals(collection,collection1);

清空集合:

collection.clear();

判断集合是否为空:

System.out.println(collection.isEmpty());
System.out.println(collection1.isEmpty());

获取集合内元素数量:

System.out.println(collection1.size());

讲集合转换成数组:

我们可以使用Object[]:

  Object[] strings = collection1.toArray(new Object[0]);
  for(Object object2 : strings){
      System.out.println(object2);
  }

但不推荐这么做，我们往往需要确定的数据类型格式:

     String[] strings = collection1.toArray(new String[0]);
     for (String object2 : strings) {
         System.out.println(object2);
     }

2 List

2.1 ArrayList

2.1.1 方法示例

List中的元素是有序的，并且可以存在重复元素

对于List部分，实际使用与Collection类似，不再赘述:

        ArrayList<String> arrayList = new ArrayList<>();
        //List基本方法
        //添加元素
        arrayList.add("丁真");
        arrayList.add("谷爱凌");
        arrayList.add("蔡徐坤");
        arrayList.add("吴亦凡");
        System.out.println(arrayList);
        //删除元素
        arrayList.remove(2);
        System.out.println(arrayList);
        //修改元素
        arrayList.set(0,"丁真珍珠");
        //查询元素
        System.out.println(arrayList.get(0));
        //获取列表大小
        System.out.println(arrayList.size());
        //克隆列表
        ArrayList<String> arrayList1 = (ArrayList<String>) arrayList.clone();
        System.out.println(arrayList1);
        //清空列表
        arrayList.clear();
        //检测是否为空
        System.out.println(arrayList.isEmpty());

运行结果:

[丁真, 丁真, 谷爱凌, 蔡徐坤, 吴亦凡]     //添加元素
[丁真, 丁真, 蔡徐坤, 吴亦凡]          //删除元素
丁真珍珠                        //修改元素
4                               //获取列表长度
[丁真珍珠, 丁真, 蔡徐坤, 吴亦凡]        //克隆列表
true                            //检测是否为空

2.1.2 底层实现

ArrayList的底层基于数组:

    private String data[];

我们使用变量size保存集合内元素的总长度(数量):

    private static int size;

我们首先创建两个构造函数，用于数组的初始化:

  • 如果传入形参 ，则创建一个指定长度的数组，否则将创建一个长度为0的数组(后续会动态扩容)
public ArrayListDemo() {
    data = new String[0];
}

public ArrayListDemo(int length) {
    if (length < 0)
        throw new IllegalArgumentException("列表长度不可以小于0");
    data = new String[length];
}

然后我们新建方法来对数组新增数据:

  • 在插入数据之前，我们需要先检查数组长度内知否已放满数据，如果是，我们需要先完成数组扩容，扩容后的新长度为其自身长度 + 自身长度向右移一位(位运算)，额外扩大其自身一半的长度(长度为16的数组扩容后为24)，
private void grow() {
    if (data.length == 1){
        Arrays.copyOf(data,data.length + 1);
    }else {
        Arrays.copyOf(data,data.length + (data.length >> 1));
    }
}
  • 由于ArrayList是有序数组，我们需要两个add()方法，分别应对是否指定数组索引的情况
  • 若没有指定索引，我们只需要在数组末尾加入数据，再让变量size自增即可
  • 如果指定了索引，我们需要先判断数据是否非法，数组的索引不能小于0，也不能超出数组长度，否则都会抛出异常，而后我们需要把数组索引以及它后面的内容全部向后挪一位，最后将数据放置在指定的索引处，并让变量size自增
public void add(String content) {
    if (size >= data.length) {
        grow();
    }
    data[size] = content;
    size++;
}
public void add(int index, String content) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("索引值 " + index + " 越界了");
    }

    if (size >= data.length) {
        grow();
    }
    //方法一
    //for (int i = size - 1; i >= index; i--) {
    //    data[i + 1] = data[i];
    //}
    //方法二（推荐）
    System.arraycopy(data,index,data,index + 1,size - index);
    data[index] = content;
    size++;
}
  • 补充说明：System类中的arraycopy()方法更适合数组中部分内容的复制(挪动)，而Array类中的copyOf()方法更适合复制整个数组

若想查询某个元素的索引值，我们需要提供带查询元素的内容，然后在数组中遍历查询第一个符合该值的元素的索引值，并将其返回，如果找不到，就返回-1，并在之后的代码中根据返回值做出回应:

    private int indexOf(int userInput) {
        for (int i = 0; i < size; i++) {
            if (Objects.equals(userInput,data[i])){
                return i;
            }
        }
        return -1;
    }

若想查询某个元素的内容，我们需要提供待查询元素的索引值，若数据合法，则返回数组对应索引元素的值

    private String get(int userInput) {
        if (userInput < 0 || userInput >= size){
            throw  new IndexOutOfBoundsException("索引越界了");
        }
        return data[userInput];
    }

若想修改某个元素，我们需要提供待修改元素的索引值，若数据合法，则返回将传来的String类型值赋值给对应数组索引，即可完成数组元素更新

    public void set(String content,int index){
        if (index < 0 || index >= size){
            throw new IndexOutOfBoundsException("索引越界了");
        }
        data[index] = content;
    }

如果想删除数组中的某个元素，我们需要提供待删除的元素索引，如果索引的值合法，我们可以截取数组中待删除元素以后的内容，并让其往前覆盖一个单位，以完成删除某个元素的同时保证数组数据连续

    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引值 " + index + " 越界了");
        }
        //方法一
//        for (int i = index; i < size - 1; i++) {
//            data[i] = data[i + 1];
//        }

        //方法二(推荐)
        System.arraycopy(data,index + 1,data,index,size - index - 1);
        size--;
    }

2.2 LinkedList

2.2.1 方法示例

节约时间，这里暂时略过，详情见底层实现

2.2.2 底层实现

我们首先要定义一些私有全局变量，他们分别记录了链表的长度、首节点和尾节点:

    private int size;
    private Node first;
    private Node last;

之后，我们建立一个内部类Node，该类包含每个节点指向上一个节点的引用(我们称其为指针)、指向下一个节点的引用(同上)和该节点保存的数据，该类还提供一个构造函数，接受的形参包括了上述三个节点信息，并把他们存储在当前节点

在LinkedList中，每一个节点都是独立的对象，我们在对节点进行创建、读取、修改、删除等操作时，通过这些节点对象来完成操作，"这允许我们动态的对链表进行添加节点、删除节点等操作，而不需要大量移动元素"，但请注意，这句话仅仅是对链表概念的解释(包括回答面试问题)，我们几乎在所有需要用到集合的场景中都使用ArrayList，而非LinkedList，LinkedList看似灵活高效，在实际应用中大量数据产生的大量对象，反而会导致LinkedList的效率并不如ArrayList

代码如下:

    class Node {
        String item;
        Node prev;
        Node next;

        public Node(String item, Node prev, Node next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

首先说明的是：first为指向头节点(首节点)的引用，last为指向尾节点的引用，prev为当前节点指向上一个节点的引用，next为当前节点指向下一个节点的引用，item为当前节点存储的数据。为了方便理解，我们后续都使用英文描述节点

当我们向LinkedList添加元素时，我们需要建立两个方法，分别对应有无提供待插入索引值

若无索引值，分为两种情况

  • 若当前链表长度为0，我们需要新建一个节点，并将该链表的first节点和last节点都指向它，最后将记录链表长度的变量size+1

  • 若当前链表长度不为0，我们需新建一个节点，将当前链表的last节点的next指向它，并将它的prev指向当前链表的last节点。当建立当前链表last节点与新加入节点的联系后，我们再将当前量表的last节点指向当前节点，这样就完成了链表新增节点，最后将记录链表长度的变量size+1

代码如下:

    public void add(String content) {
        Node node = new Node(content, null, null);
        if (size == 0){
            this.first = node;
        }else {
            this.last.next = node;
            node.prev = this.last;
        }
        this.last = node;
        size++;
    }

若有索引值，我们需要先判断索引的合法性，他不能小于索引下限值0，也不能超过当前链表长度，而后也分为两类情况第一类：

  • 若索引值等于当前链表长度，就等于在链表末尾新增节点，也就是上述无索引值传参的add()方法，那么直接调用另一个方法，之后使用return来结束方法，完成节点添加操作，不再赘述

第二类:

若索引值不等于当前链表长度，我们先创建一个Node对象node，并通过构造函数的方式将形参中的数据存入节点。而后再次分为两种情况:

  • 若待插入的索引值为0，将当前节点的next指向当前链表的first节点，并将first节点的next指向当前节点node，这样就把当前节点与当前列表first节点建立了联系，最后再将链表的头节点指向当前节点node，完成对链表头部添加节点的操作

    • 若索引值不为0，就再次新建一个节点对象node1，并将其指向待插入索引值对应的链表节点(原节点)
    • 之后我们首先将原节点node1的上一个节点的next指向新节点node，然后把新节点的prev指向原节点的prev，这样一来我们就切断了源节点node1与他上一个节点的连接，并让上一个节点与新节点node建立连接
    • 然后将新节点node的next指向原节点node1，并将原节点node1的prev指向新节点node，这样一来我们在切断node1与上一个节点的基础上，建立新节点node与原节点node1的连接。
    • 这样宏观表现就是我们将断开原节点的上一个节点的连接，让上一个节点与新节点连接，而新节点再与原节点连接，达到再指定索引位置插入新节点的效果

最终代码如下:

    public void add(String content,int index){
        if (index < 0 || index > size){
            throw new IndexOutOfBoundsException("索引越界了");
        }
        if (index == size){
            add(content);
            return;
        }
        Node node = new Node(content,null,null);
        if (index == 0){
            node.next = this.first;
            this.first.prev = node;
            this.first = node;
        }else {
            Node node1 = getNode(index);
            node1.prev.next = node;
            node.prev = node1.prev;
            node.next = node1;
            node1.prev = node;
        }
        size++;
    }

在上述代码中，我们在查询原节点时用到了getNode()方法，下面我们将对它展开说明:

在调用getNode()方法时，我们需要传入索引值进行查询，首先同样需要检查数据合法性，索引不能小于0，也不能超过链表长度

LinkList是双向循环链表，我们需要从链表的首位作为循环的起点，一般从头节点开始，在查询到期望数据后，将其节点对象返回，代码如下:

    private Node getNode(int index) {
        if (index < 0 || index >= size){
            throw new IndexOutOfBoundsException("索引越界了");
        }
        Node node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

接下来我们该如何修改链表内容呢，当我们调用set()方法时，需要传入节点数据、节点索引两个参数，首先检查索引合法性，他不能小于0，也不能超过数组长度

之后传入索引值调用getNode()方法，拿到返回的节点对象，并将想要修改的数据赋值给这个对象的item

同理如果我们想要根据节点数据，查询匹配到的第一个索引值，可以调用indexOf()方法，由于这里不需要操作索引值，不用担心越界，也就不用再检查合法性

在这个方法中，我们首先创建一个节点对象，并将其指向链表的头节点，之后遍历链表，每次循环都进行一次比对，如果匹配成功，就直接返回i值作为索引值，并结束循环，每一次比对结束后都要让当前节点对象node指向下一个节点，这样才会一条路遍历下去直到尾节点

  • 从运行效率的角度思考，我们在对比两个数据时，首先对比他的哈希值，如果哈希值都不同，那么数据一定不相同，直接哒咩，但哈希值相同，数据也不一定相同哦，这个时候我们再考虑它是否为null值，如果不是，再使用equals()方法进行字符比对，也就是if((a == b) || (a != null && a.equals(b)))，而Objects类中已经按照我们上述的条件重写了equals()方法，因此我们在对比数据时直接调用Objects.equals()即可，Objects类中equals()方法源码如下图:

代码如下:

public int indexOf (String content){
    Node node = first;
    for (int i = 0; i < size; i++){
        if (Objects.equals(node.item,content)){
            return i;
        }
        node = node.next;
    }
    return -1;
}

当我们想要删除某个节点，我们调用remove()方法时需要传入待删除节点的索引，所以我们需要先判断索引值是否越界，它不能小于0，也不能大于节点长度，而后分为三种情况:

  • 如果待删除结点的索引值为0，也就是我们需要删除链表的头节点。我们将链表的first节点指向first节点的next，再将更新后链表的first节点的prev(也就是已经被丢弃的那个节点)设为null即可
  • 如果待删除节点的索引值在0之后，在最后一个节点之前，也就是数学中的[0,n-1)，由于索引值从0开始，所以n-1，也就是size-1的值就是为尾节点对应的索引。所以说我们要删除的是尾节点，与第一种情况类似，我们需要先将链表的last节点指向倒数第二个节点，也就是last节点的prev，然后将更新后链表的last节点的next(也就是已经被丢弃的那个节点)设为null
  • 如果索引值为前两种之外的情况，既不是头节点，也不是尾节点，那就是链表中间的节点，在数学上用(0,n-1)表示。我们先新建一个节点对象node，通过getNote()方法找到想要删除的节点，并让node指向它，之后我们让将要被删除的节点对象node的prev指向待删除节点node的next(也就是让待删除的那个节的与它上一个节点断开连接，让上一个节点绕过待删除节点连接它的下一个节点)，然后我们让待删除节点node的next节点的prev指向待删除节点node的prev(也就是让待删除的那个节点与它下一个节点断开连接，让下一个节点绕过待删除的那个节点去连接他的的上一个节点)，这样一套流程下来，我们就断开了想要删除的那个结点与链表中的上下连接关系，并让除此之外断开的链表重新连接起来，达到删除的目的。最后让记录链表长度的变量size自减一次即可，这样我们就完成了删除指定索引节点的操作，代码如下:
public void remove(int index){
    if (index < 0 || index >= size){
        throw new IndexOutOfBoundsException("索引越界了");
    }
    if (index == 0){
        this.first = this.first.next;
        this.first.prev = null;
    }else if (index == size - 1){
        this.last = this.last.prev;
        this.last.next = null;
    }else {
        Node node = getNode(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    size--;
}

如果我们想要清空链表，不要挨个每个节点都清空，由于我们不要这个链表了，以后也不用它了，那我们直接把这个链表的头节点和尾节点都设置为null，这样等于让链表中间的所有节点都与这个链表断开了连接，最后再将用于记录链表长度的变量size设为0，一套下来就达到宏观上清空链表的效果

有的朋友可能心中有疑问，为什么在这里我们不遍历删除节点，而是直接丢弃呢，这样不会浪费内存空间吗？答案是不会的，首先这么做宏观上能快速高效的达到我们想要的结果，而在代码和系统层面，所有的节点都是Node类的对象，当整个程序不存在任何指向这些对象的引用时，JVM自带的内存垃圾回收系统会自动释放内存，所以完全不需要我们来操作

代码如下:

public void clean(){
    this.first = this.last = null;
    size = 0;
}

— 思考一下，我们该如何截取链表中的内容呢?