Java基础篇 List集合的详解

末蓝、 2022-05-21 08:29 194阅读 0赞

## 简述 ##

--------------------

上章简单介绍了什么是集合，集合有哪几种种类。  
在这章中我们主要介绍Collection的其中一种实现方式，List。

## 什么是List ##

--------------------

在上一章，我们已经了解了List主要分为3类，ArrayList， LinkedList和Vector。  
为了进一步清晰List的结构，我在这手工画了一张图，用于回顾下

![这里写图片描述][20161018214236504]

AbstarctCollection在上一张[Java集合详解–什么是集合][Java]已经有简单的介绍，它是Collection接口的部分实现

**1.List接口**

首先看下List的官方定义

![这里写图片描述][20161018215511411]

这段描述解决了许多公司经常问的两个问题List有什么特点和Set有什么区别。  
上面清楚的说明了List是一个有序的集合，和set不同的是，List允许存储项的值为空，也允许存储相等值的存储项，还举了e1.equal(e2)的例子。

List是继承于Collection接口，除了Collection通用的方法以外，扩展了部分只属于List的方法。

![这里写图片描述][20161018214542238]

从上图可以发现，List比Collection主要多了几个add（…）方法和remove(…)方法的重载，还有几个index(…)， get(…)方法。  
而AbstractList也只是实现了List接口部分的方法，和AbstractCollection是一个思路，这里就不具体介绍了，有兴趣的同学可以自行研究下。

**2.ArraryList**

ArrayList是一个数组实现的列表，由于数据是存入数组中的，所以它的特点也和数组一样，查询很快，但是中间部分的插入和删除很慢。我们来看几段关键的代码。

首先是ArrayList的类关系和成员变量

//ArrayList继承了Serializable并且申明了serialVersionUID，表示ArrayList是一个可序列化的对象，可以用Bundle传递
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        private static final long serialVersionUID = 8683452581122892189L;
    
        /** * Default initial capacity. */
        private static final int DEFAULT_CAPACITY = 10;
    
        /** * Shared empty array instance used for empty instances. */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to * DEFAULT_CAPACITY when the first element is added. */
         //从这里可以看到，ArrayList的底层是由数组实现的，并且默认数组的默认大小是10
        private transient Object[] elementData;
    
        /** * The size of the ArrayList (the number of elements it contains). * * @serial */
        private int size;
    
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32

然后是构造函数

//ArrayList有2个构造函数，一个是默认无参的，一个是传入数组大小的
    //在JavaEffect书中明确提到，如果预先能知道或者估计所需数据项个数的，需要传入initialCapacity
    //因为如果使用无参的构造函数，会首先把EMPTY_ELEMENTDATA赋值给elementData
    //然后根据插入个数于当前数组size比较，不停调用Arrays.copyOf()方法，扩展数组大小
    //造成性能浪费
    /** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */
        public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }
    
        /** * Constructs an empty list with an initial capacity of ten. */
        public ArrayList() {
            super();
            this.elementData = EMPTY_ELEMENTDATA;
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27

然后是add()操作

//首先看到，不过是指定index执行add操作，还是在尾部执行add操作，都会先确认当前的数组空间是否够插入数据
    //并且从
    //int oldCapacity = elementData.length;
    //int newCapacity = oldCapacity + (oldCapacity >> 1);
    //if (newCapacity - minCapacity < 0)
    // newCapacity = minCapacity;
    //看出，ArrayList默认每次都是自增50%的大小再和minCapacity比较，如果还是不够，就把当的
    //size扩充至minCapacity
    //然后，如果是队尾插入，也简单，就把数组向后移动一位，然后赋值
    //如果是在中间插入，需要用到System.arraycopy，把index开始所有数据向后移动一位
    //再进行插入
    /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        /** * Inserts the specified element at the specified position in this * list. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */
        public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    
         private void ensureCapacityInternal(int minCapacity) {
                if (elementData == EMPTY_ELEMENTDATA) {
                    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
                }
    
                ensureExplicitCapacity(minCapacity);
            }
    
            private void ensureExplicitCapacity(int minCapacity) {
                modCount++;
    
                // overflow-conscious code
                if (minCapacity - elementData.length > 0)
                    grow(minCapacity);
            }
    
         private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69

然后是remove操作

//个人感觉整个remove操作的代码写了很冗余，不像甲骨文这些大神的风格
    //首先来看remove(int index)
    //先进行边界确认，传入的index是否超过了当前数组的大小，如果是抛出异常
    //如果在数组范围内，就把index之后的数据整体向前移动一位，最后一位值清空
    //如果是remove(Object o)，传入的是一个对象，就会进行一次indexOf的操作，去当前数组中寻找
    //判断是否存在，这里的代码就十分冗余了，就是把indexOf的代码拷贝了一次，完全可以调用indexOf方法
    //根据返回值是否为-1来判断该值是否存在，如果存在就调用fastRemove方法
    //fastRemove(int index)和remove(int index)方法除了边界检查一模一样
    //完全可以在remove调用完rangeCheck(index)后调用fastRemove就可以了
    //这里不是很明白设计者的意图
    /** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */
        public E remove(int index) {
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
    
        /** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified element (or equivalently, if this list * changed as a result of the call). * * @param o element to be removed from this list, if present * @return <tt>true</tt> if this list contained the specified element */
        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
        /* * Private remove method that skips bounds checking and does not * return the value removed. */
        private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73
       74
       75
       76

indexof

//这里就和上面remove寻找是一模一样的，就不进行探讨了
    public int indexOf(Object o) {
            if (o == null) {
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
            } else {
                for (int i = 0; i < size; i++)
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13

**3.Vector**

Vector就是ArrayList的线程安全版，它的方法前都加了synchronized锁，其他实现逻辑都相同。  
如果对线程安全要求不高的话，可以选择ArrayList，毕竟synchronized也很耗性能

**4.LinkedList**

故名思意就是链表，和我们大学在数据结构里学的链表是一会事，LinkedList还是一个双向链表。

![这里写图片描述][20161019214729600]

LinkedList继承于AbstractSequentialList,和ArrayList一个套路。内部维护了3个成员变量，一个是当前链表的头节点，一个是尾部节点，还有是链表长度。然后我们在来看下Node这个数据结构。

![这里写图片描述][20161019214926369]

和C语言实现方式差不多，由于是双向链表，所以记录了next和prev，只不过把C语言里的指针换成了对象。

然后我们简单的在来看下链表额度查询，插入和删除操作

首先是add(E e)操作

//学过数据结构的同学看这部分代码特别轻松
        //首先来看下void linkLast(E e)，尾部插入
        //就是把newNode的前面节点执行现在的尾部节点，newNode的后面节点执行null,因为是在尾部嘛
        //然后把现在的尾部节点的后面节点指向newNode,因为现在的尾部节点不是最后一个了
    
        //然后再来看下中间插入
        //也是一个套路。假设现在在3号位插入一个newNode
        //就是通过现在的3号Node的prev找到2号节点，然后修改2号节点的next，指向nowNode
        //然后nowNode的prev指向2号节点，next指向3号节点
        //最后3号节点的prev变成了nowNode,next不变
        //这样就完成了一次中间插入 
    
        /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */
        public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    
        /** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #addLast}. * * @param e element to be appended to this list * @return {@code true} (as specified by {@link Collection#add}) */
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
        /** * Links e as last element. */
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    
        /** * Inserts element e before non-null Node succ. */
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73

然后是void linkLast(E e)操作

//indexOf操作非常简单，就是从头开始遍历整个链表，如果没有就反-1，有就返回当前下标
    /**
         * Returns the index of the first occurrence of the specified element
         * in this list, or -1 if this list does not contain the element.
         * More formally, returns the lowest index {
       @code i} such that
         * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
         * or -1 if there is no such index.
         *
         * @param o element to search for
         * @return the index of the first occurrence of the specified element in
         *         this list, or -1 if this list does not contain the element
         */
        public int indexOf(Object o) {
            int index = 0;
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null)
                        return index;
                    index++;
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item))
                        return index;
                    index++;
                }
            }
            return -1;
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29

虽然indexOf非常简单，但是我在这还是写了个例子，帮助大家理解下

List list = new ArrayList();
            list.add("zero");
            list.add(null);
            list.add("two");
            list.add(null);
            list.add("three");
    
            Log.i("test", "index : " + list.indexOf(null));
     
      
       1
       2
       3
       4
       5
       6
       7
       8

在不看答案的情况下 大家能准确的说出答案吗？

Answer:I/test: index : 1

从这个例子可以看出三点List的特征  
1.是按顺序查找  
2.允许存储项为空  
3.允许多个存储项的值相等

最后看下remove操作

//如果直接调无参的remove(),就会默认删除头节点
        //删除头节点非常简单，就是把头节点的值清空，next清空
        //然后把nextNode只为头节点，然后清空next的prev
        //最后size减1
        //如果是删除中间节点，调用remove(int index)
        //首先判断Index对应的节点是否为头节点，即index是否为0
        //如果不是中间节点，就是x的prev指向x的next
        public E remove() {
            return removeFirst();
        }
    
        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
    
         public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
    
        private E unlinkLast(Node<E> l) {
            // assert l == last && l != null;
            final E element = l.item;
            final Node<E> prev = l.prev;
            l.item = null;
            l.prev = null; // help GC
            last = prev;
            if (prev == null)
                first = null;
            else
                prev.next = null;
            size--;
            modCount++;
            return element;
        }
    
        /** * Unlinks non-null node x. */
        E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }
    
        /** * Unlinks non-null first node f. */
        private E unlinkFirst(Node<E> f) {
            // assert f == first && f != null;
            final E element = f.item;
            final Node<E> next = f.next;
            f.item = null;
            f.next = null; // help GC
            first = next;
            if (next == null)
                last = null;
            else
                next.prev = null;
            size--;
            modCount++;
            return element;
        }
     
      
       1
       2
       3
       4
       5
       6
       7
       8
       9
       10
       11
       12
       13
       14
       15
       16
       17
       18
       19
       20
       21
       22
       23
       24
       25
       26
       27
       28
       29
       30
       31
       32
       33
       34
       35
       36
       37
       38
       39
       40
       41
       42
       43
       44
       45
       46
       47
       48
       49
       50
       51
       52
       53
       54
       55
       56
       57
       58
       59
       60
       61
       62
       63
       64
       65
       66
       67
       68
       69
       70
       71
       72
       73
       74
       75
       76
       77
       78
       79
       80
       81
       82
       83
       84
       85
       86

## 总结 ##

--------------------

通过上面对ArrayList和LinkedList的分析，可以理解List的3个特性  
1.是按顺序查找  
2.允许存储项为空  
3.允许多个存储项的值相等  
可以知其然知其所以然

然后对比LinkedList和ArrayList的实现方式不同，可以在不同的场景下使用不同的List  
ArrayList是由数组实现的，方便查找，返回数组下标对应的值即可，适用于多查找的场景  
LinkedList由链表实现，插入和删除方便，适用于多次数据替换的场景

[20161018214236504]: /images/20220521/69b5389ff98d4c44b6dea21611a59cad.png
[Java]: http://blog.csdn.net/wz249863091/article/details/52843060
[20161018215511411]: /images/20220521/21b06180c2a1423a84a1a2712c4d148b.png
[20161018214542238]: /images/20220521/813c8d9cd34b4e1185efe2966fadf9a9.png
[20161019214729600]: /images/20220521/fb81c6da8241454b9df82fbaae99b353.png
[20161019214926369]: /images/20220521/e255ab7f76c7414f9d20b385a9523e54.png