List集合

兰舟千帆

发布于 2022-07-16 13:36:35

1.7K0

发布于 2022-07-16 13:36:35

文章被收录于专栏：兰舟千帆的java学习笔记

三：List集合

List集合是单列集合的一种，它所存储的元素是可以重复的。List是直接实现Collection接口类的一种。完整的lIst接口类定义如下。

public interface List<E>extends Collection<E>

E是指代了泛型，泛型说明了类属性。

与 set 不同，列表通常允许重复的元素。更确切地讲，列表通常允许满足 e1.equals(e2) 的元素对 e1 和 e2，并且如果列表本身允许 null 元素的话，通常它们允许多个 null 元素。 List 接口在 iterator、add、remove、equals 和 hashCode 方法的协定上加了一些其他约定，超过了 Collection 接口中指定的约定。为方便起见，这里也包括了其他继承方法的声明。 List 接口提供了 4 种对列表元素进行定位（索引）访问方法。列表（像 Java 数组一样）是基于 0 的。注意，这些操作可能在和某些实现（例如 LinkedList 类）的索引值成比例的时间内执行。因此，如果调用者不知道实现，那么在列表元素上迭代通常优于用索引遍历列表。 List 接口提供了特殊的迭代器，称为 ListIterator，除了允许 Iterator 接口提供的正常操作外，该迭代器还允许元素插入和替换，以及双向访问。还提供了一个方法来获取从列表中指定位置开始的列表迭代器。 List 接口提供了两种在列表的任意位置高效插入和移除多个元素的方法。

既然是接口，那必然需要实现类了。我们通常需要了解两种，那就是ArrayList，LinkedList。

1：实现类ArrayList

<1>方法说明

注意ArrayList只是实现了List，但是并没有继承List接口

public class ArrayList<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, Serializable

可见ArrayList的继承自AbstractList,然后我们查看AbstractList的类定义 查询JDK API说明我们可以看到AbstractList的完整定义

public abstract class AbstractList<E>extends AbstractCollection<E>implements List<E>

溯源

public abstract class AbstractCollection<E>extends Object implements Collection<E>

这些了解就可以，没有什么疑问，Object是根。

ArrayList数据结构为数组，通过数组的特点，我们可以了解到，数组的查询是比较快的，但是增删是比较慢的。

我们来看ArrayList的几个常用的方法。

测试了大部分方法

     //1:将指定的元素添加到此列表的尾部。
        List l = new ArrayList<>();
        //ArrayList L = new ArrayList<>();
        l.add("Hello");//一次只能插入一个元素
        System.out.println(l);
        // 2： add(int index, E element) 
        l.add(0,"jgdabc");
        System.out.println(l);
        ArrayList l1 = new ArrayList<>();
        l1.add("jgdabc01");
        l1.add(20);
        System.out.println(l1);
        //3:add()方法，整个集合添加
        l.add(l1);
        l.addAll(1,l1);
        System.out.println(l);
        //4:addAll(Collection<? extends E> c) 
        l.addAll(l1);
        System.out.println(l);
        //5:addAll(int index, Collection<? extends E> c) 
        //从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。
        l.add(1,l1);
        System.out.println(l);
        //6:clear() 
        //移除此列表中的所有元素。
        l.clear();
        System.out.println(l);
        //7:contains(Object o) 
        //如果此列表中包含指定的元素，则返回 true。
        boolean flag = l1.contains("jgdabc");
        System.out.println(flag);
        //8:get(int index) 
        //返回此列表中指定位置上的元素。如果集合为空，会报异常。
        l.add("jgdabc");
        String s = (String) l.get(0);
        System.out.println(s);
        //9：indexOf(Object o) 
        //返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。
        int x = l.indexOf("jgdabc");
        System.out.println(x);
        //10:isEmpty() 
        //如果此列表中没有元素，则返回 true
        boolean flag_1 = l.isEmpty();
        System.out.println(flag_1);
        //11:lastIndexOf(Object o) 
        //返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。
        int flag_2 = l.lastIndexOf("jgdabc");
        System.out.println(flag_2);
        //12:remove(int index) 
        l.remove(0);
        System.out.println(l);
        //13:removeRange(int fromIndex, int toIndex) 
        //移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。
        // removeRange()方法受保护，只提供子类使用
        l.add("jgdabc");
        l.add("jgdabc01");
        ArrayList ll = new ArrayList<>();
        ArrayList ll2 = ll;
        //14:set(int index, E element) 
        //用指定的元素替代此列表中指定位置上的元素。
        l.set(0, "zhan");
        System.out.println(l);
        // 15:toArray() 
        //按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组
        l.toArray();
        System.out.println(l);
        // 17:trimToSize() 
        //将此 ArrayList 实例的容量调整为列表的当前大小。
        ((ArrayList<Object>) l).trimToSize();
        System.out.println(l.size());

其中需要注意的就是两个方法，一个removeRange()，这个方法虽然在ArrayList中被提供，但是受到保护，只能被子类使用。也就是写一个继承类就好。 还有一个方法，可能并不常用。其实涉及到优化。那就是trimToSize()方法

ArrayList 的内部使用数组存储元素，当数组将被存满，就会创建一个新数组，其容量是当前数组的 1.5 倍。同时，所有元素都将移至新数组，假设内部数组已满，而我们现在又添加了 1 个元素，ArrayList 容量就会以相同的比例扩展（即前一个数组的1.5倍）。在这种情况下，内部数组中将有一些未分配的空间。这时，trimToSize() 方法可以删除未分配的空间并更改 ArrayList 的容量，使其等于 ArrayList 中的元素个数。

<2>并发修改异常

先来看一个代码

package java_practice;

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

public class ListDemo {
    public static void main(String args[]) {

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        Iterator<String> it = list.iterator();
        while(it.hasNext()) {
            String s = it.next();
            if(s.equals("world"))
            {
                list.add("javaee");
            }


           }
//            for(int i=0;i<list.size();i++)
//            {
//                String s = list.get(i);
//                if(s.equals("world"))
//                {
//                    list.add("javaee");
//                }
//
//            }
            System.out.println(list);


    }
}

很显然这里抛出了异常，为什么会这样呢？

下面摘录异常信息

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:907)
	at java.util.ArrayList$Itr.next(ArrayList.java:857)
	at java_practice.ListDemo.main(ListDemo.java:16)

我们根据checkForComodification步步跟进源码 下面是跟进和溯源处理后的关键源码信息

public interface List<E>{
Iterator<E> iterator();
boolean add(E e)
}

public abstract class AbstractList<E>
{
protected transient int modCount = 0;

}

public class ArrayList<E> extends AbstractList<E>implements List<E>
{
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!//每次调用add()会使modCount++
            elementData[size++] = e;
            return true;
        }
    public E get(int index) {
             rangeCheck(index);

            return elementData(index);
            }
    public Iterator<E> iterator() {
            return new Itr();
    }
    private class Itr implements Iterator<E> {

            int expectedModCount = modCount;
            //modCount为实际修改集合的次数
            //expectedModCount为预期修改集合的次数
            public E next() {
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }


            final void checkForComodification() {
                if (modCount != expectedModCount)
                //modCount为修改集合的次数，exceptedModCount为预期修改集合的次数
                    throw new ConcurrentModificationException();
            }
        }

        /**
}

源码很清楚了，而且我做了部分注释，可以自己捋一下。原因就是，我们采用迭代器的时候，迭代器会有一个预期的迭代次数，当我们进行在迭代的同时进行添加的时候会调用add()方法的话，就会modCount++（实际迭代次数）,但是expectedModCount（预期迭代次数）没有进行处理同步，造成了数据不一致，源码也说明了，如果不一致，就会抛出异常。 提出一种解决的办法，避免数据不一致，比如for循环。

package java_practice;

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

public class ListDemo {
    public static void main(String args[]) {

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        Iterator<String> it = list.iterator();
//        while(it.hasNext()) {
//            String s = it.next();
//            if(s.equals("world"))
//            {
//                list.add("javaee");
//            }

    //
           //}
            for(int i=0;i<list.size();i++)
            {
                String s = list.get(i);
                if(s.equals("world"))
                {
                    list.add("javaee");
                }

            }
            System.out.println(list);


    }
}

可能在这里你可能有疑问，get()俩面不也有add()吗？为什么不报异常。上面源码也摘录出来了。原因就是我们调用了集合的add()方法，实际上会使实际迭代次数加一的，但是get()函数里面没有进行实际与预期的判断，也自然不会抛出异常，可以参考上诉源码，明明白白。

<3>ListIterator(列表迭代器)

List集合特有的迭代器 接口完整定义

public interface ListIterator<E>extends Iterator<E>

JDK API说明

系列表迭代器，允许程序员按任一方向遍历列表、迭代期间修改列表，并获得迭代器在列表中的当前位置。 演示一个使用

package java_practice;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class ListDemo {
    public static void main(String args[]) {

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        Iterator<String> it = list.iterator();
//        while(it.hasNext()) {
//            String s = it.next();
//            if(s.equals("world"))
//            {
//                list.add("javaee");
//            }

    //
           //}
//
        ListIterator<String> lit = list.listIterator();
        while(lit.hasNext())
        {
            String s = lit.next();
            if(s.equals("world"))
            {
                lit.add("javaee");
            }
        }

        System.out.println(list);


    }
}

一个疑问就是为什么ListIterator没有报异常？ 我们还是追溯源码，最终整理如下

public interface List<E>{
Iterator<E> iterator();
ListIterator<E> listIterator();
boolean add(E e)
}

public abstract class AbstractList<E>
{
protected transient int modCount = 0;

}

public class ArrayList<E> extends AbstractList<E>implements List<E>
{
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!//每次调用add()会使modCount++
            elementData[size++] = e;
            return true;
        }
    public E get(int index) {
             rangeCheck(index);

            return elementData(index);
            }
    public Iterator<E> iterator() {
            return new Itr();
    }
    private class Itr implements Iterator<E> {
    public ListIterator<E> listIterator() {
            return new ListItr(0);
        }
}
private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
}

追诉到根本就是ListItr的add()方法。通过源码分析可以了解到，这里的add()方法在使用后会给预期的变量重新赋值，所以会使预期和实际的统一，这样就不会报异常了。

<4>增强for循环

还是从JDK API查找资料从Collection出发

public interface Collection<E>extends Iterable<E>

追溯Iterable,有理可依。

public interface Iterable<T>实现这个接口允许对象成为 "foreach" 语句的目标。

并且Iterable给出了其可使用的迭代器

Iterator iterator() 返回一个在一组 T 类型的元素上进行迭代的迭代器。

所以可以了解到增强for循环，简化数组和Collection集合的遍历。实现Iterable的类允许其对象成为增强型for循环语句的目标。版本在JDK5之后，内部实现原理是Iterator迭代器。 使用格式如下：

举例示范

int[] arr = {1,2,3,4,5};
        for(int i:arr)
        {
            System.out.println(i);
        }

        List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        for(String s :list)
        {
            System.out.println(s);
        }

验证内部实现原理

如何验证内部实现原理是Iterator迭代器，通过Iterator迭代器迭代添加过程中的并发修改异常的特点来验证

   List<String> list = new ArrayList<String>();
        list.add("Hello");
        list.add("world");
        list.add("java");
        for(String s :list)
        {
            if(s.equals("java")){
                list.add("javaee");
            }
            System.out.println(s);
        }

异常信息摘录： Exception in thread “main” java.util.ConcurrentModificationException at java.util.ArrayList

Itr.checkForComodification(ArrayList.java:907) at java.util.ArrayList

Itr.next(ArrayList.java:857) at java_practice.ListDemo.main(ListDemo.java:15)

这里的异常和并发修改的异常一样，所以可以验证出内部实现原理是Iterator迭代器。也可以通过异常追溯源码来验证。

2：实现类LinkedList

基本的继承关系上，同ArrayList一样不是直接继承List接口，是一个实现类。 我们还是明确它的继承以及实现关系

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList的底层实现是链表，并且是双向链表。

与ArrayList相比，ArrayList的基本实现是数组，数组是便于进行查找的，而LinkedList的基本是实现双向链表是方便去进行增删改，但是不是很适合去随机查询。当然是和数组相比较。这个双向链表的顺序查找效率还是比较高的，因为是双向链表嘛！每个节点都有一个直接前驱和直接后继。前驱和后继可以认为是指针(C语言中的灵魂)。

<方法说明>

我们来看方法说明，其实很多方法还是和ArrayList的方法一样的。 add() addAll,clear(),clone(),contains(),get(),indexof(),lastIndexof(),remove(),set(),toArray()。基本上这几个方法都和ArrayList的方法使是一样的。 具体的看一些新的方法。我们分开说明

1：removeLastOccurrence(Object o) 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表时）。

 LinkedList link = new LinkedList<>();
        link.add("jgdabc");
        link.add("jink");
        link.add("jgdabc");
        System.out.println(link);
        link.removeLastOccurrence("jgdabc");
        System.out.println(link);

相应的一样道理 2：removeFirstOccurrence(Object o) 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。

 LinkedList link = new LinkedList<>();
        link.add("jgdabc");
        link.add("jink");
        link.add("jgdabc");
        System.out.println(link);
        link.removeFirstOccurrence("jgdabc");
        System.out.println(link);

3：removeLast() 移除并返回此列表的最后一个元素。改方法在移除的同时会返回移除的元素。

  link.removeFirstOccurrence("jgdabc");
        System.out.println(link);
        String s_s = (String) link.removeLast();
        System.out.println("移除元素后的集合："+link);
        System.out.println("被移除的元素:"+s_s);

同样， 4：removeFirst() 移除并返回此列表的第一个元素。不再举例 5：push(E e) 将元素推入此列表所表示的堆栈。此方法就是压栈的操作。 该方法的效果等同于addFirst() 对应还有 6:pop(E e) 出栈，此方法等效于removeFirst()

  link.push("jgdabc");
        System.out.println(link);
        link.pop();
        System.out.println(link);

7:pollLast() 获取并移除此列表的最后一个元素；如果此列表为空，则返回 null 8:pollFirst() 获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 9：poll() 获取并移除此列表的头（第一个元素）

  String s_  = (String) link.pollLast();
        System.out.println(s);
        String s_1 = (String) link.pollFirst();
        System.out.println(s_1);
        String s_2 = (String) link.poll();
        System.out.print(s_2);

10：peekLast() 获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 11：peekFirst() 获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 12:peek() 获取但不移除此列表的头（第一个元素）。

String s_3 = (String) link.peekFirst();
        System.out.println(s_3);
        String s_4 = (String) link.peekLast();
        System.out.println(s_4);
        String s_5 = (String) link.peek();
        System.out.println(s_5);

13:offerLast(E e) 在此列表末尾插入指定的元素。 14:offerFirst(E e) 在此列表的开头插入指定的元素。 15:offer(E e) 将指定元素添加到此列表的末尾（最后一个元素）。

 boolean flag_f= link.offerFirst("jgdabc");
        System.out.println(flag_f);
        System.out.println(link);
        boolean baby = link.offerLast("baby");
        System.out.println(baby);
        System.out.println(link);
        boolean come_on = link.offer("come on");
        System.out.println(come_on);
        System.out.println(link);

14: Iterator descendingIterator() 返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。 具体的我们举个例子，看看这个逆向迭代器的使用，后面还会总结迭代方法

Iterator iterator = link.descendingIterator();
        while(iterator.hasNext())
        {
            System.out.println(iterator.next());

        }