Java Improvement Chapter (32)-----List Summary

                                                                                LZ has fully introduced most of the knowledge about the List interface, such as ArrayList, LinkedList, Vector, Stack. Through these knowledge points, you can have a deeper understanding of the List interface. Only knowledge summarized through induction is your knowledge. So below, LZ will make a summary of the List interface. Recommended reading:

#java improvement article (21)---- -ArrayList

#                      Java Improvement Chapter (Two Two) -----LinkedList

                                                                                                                       Java Improvement Chapter (Sanyi) -----Stack

1. Overview of the List interface

                             

List interface becomes an ordered Collection, that is, a sequence. This interface can precisely control the insertion position of each element in the list, and users can access elements based on their integer index (position in the list) and search for elements in the list. The following figure is the framework diagram of the List interface:

##              
Through the above With the framework diagram, you can clearly understand the structure of List. Its various classes and interfaces are as follows:

Collection：

Collection The root interface in the hierarchy. It represents a set of objects, which are also called elements of a collection. For Collection, it does not provide any direct implementation, and all implementations are the responsibility of its subclasses.

           AbstractCollection: Provides the backbone implementation of the Collection interface to minimize the need to implement this interface work. For us to implement an immutable collection, we simply extend this class and provide implementations of the iterator and size methods. But to implement a modifiable collection, the add method of this class must be overridden (otherwise, UnsupportedOperationException will be thrown), and the iterator returned by the iterator method must also implement its remove method.

          terator: Iterator.

           ListIterator: Series list iterator, allowing programmers to traverse the list in either direction and modify it during iteration list and gets the iterator's current position in the list.

​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ It represents an ordered queue.         

AbstractList:

Backbone implementation of the List interface to minimize the need to implement "random access" data storage (such as an array) is required for this interface to work.

                                    

Queue: Queue. Provides basic insertion, retrieval, and inspection operations for the queue.

          Deque: A linear collection that supports inserting and removing elements at both ends. Most Deque implementations have no fixed limit on the number of elements they can contain, but this interface supports both capacity-limited deques and deques without a fixed size limit.

## The work required to access this interface supported by a data store such as a linked list. In a sense, this class is the same as implementing a "random access" method on a list iterator of a list.

           LinkedList: Linked list implementation of the List interface. It implements all optional list operations.

​​​​​​​ ArrayList: Implementation of variable-sized array of List interface. It implements all optional list operations and allows all elements including null. In addition to implementing the List interface, this class also provides methods to manipulate the size of the array used internally to store the list.

​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ Like an array, it contains components that can be accessed using integer indexes.              Stack:

Last-in-first-out (LIFO) object stack. It extends class Vector with five operations that allow vectors to be treated as stacks. ​​​​​ Enumeration：

Enumeration, an object that implements this interface, generates a series of elements, one at a time one. Continuous calls to the nextElement method will return a sequence of consecutive elements.

##2. Usage scenarios

      

The fundamental purpose of learning knowledge is to use it. Each knowledge point has its scope of use. The same is true for collections. The family of collections in Java is very large, and each member has the most suitable usage scenario. When he first came into contact with List, LZ said If it involves operations such as "stack", "queue", and "linked list", please give priority to using List.

As for which List it is, it is divided as follows:

            1. If you need to quickly insert and delete elements, you need to use LinkedList.

##       

2. If you need to access elements quickly, you need to use ArrayList. ##​​​

3. For "single-threaded environment" or "multi-threaded environment, but List is only operated by one thread", you need to consider using asynchronous classes. If It is a "multi-threaded environment, and List may be operated by multiple threads at the same time." Consider using a synchronized class (such as Vector).

2.1ArrayList, LinkedList Performance Analysis

##                                                                                                                                                                We also learned about the usage scenarios and differences between them.

public class ListTest {
    private static final int COUNT = 100000;
    
    private static ArrayList arrayList = new ArrayList<>();
    private static LinkedList linkedList = new LinkedList<>();
    private static Vector vector = new Vector<>();
    
    public static void insertToList(List list){
        long startTime = System.currentTimeMillis();

        for(int i = 0 ; i < COUNT ; i++){
            list.add(0,i);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("插入 " + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }
    
    public static void deleteFromList(List list){
        long startTime = System.currentTimeMillis();
        
        for(int i = 0 ; i < COUNT ; i++){
            list.remove(0);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("删除" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }
    
    public static void readList(List list){
        long startTime = System.currentTimeMillis();
        
        for(int i = 0 ; i < COUNT ; i++){
            list.get(i);
        }
        
        long endTime = System.currentTimeMillis();
        System.out.println("读取" + COUNT + "元素" + getName(list) + "花费 " + (endTime - startTime) + " 毫秒");
    }

    private static String getName(List list) {
        String name = "";
        if(list instanceof ArrayList){
            name = "ArrayList";
        }
        else if(list instanceof LinkedList){
            name = "LinkedList";
        }
        else if(list instanceof Vector){
            name = "Vector";
        }
        return name;
    }
    
    public static void main(String[] args) {
        insertToList(arrayList);
        insertToList(linkedList);
        insertToList(vector);
        
        System.out.println("--------------------------------------");
        
        readList(arrayList);
        readList(linkedList);
        readList(vector);
        
        System.out.println("--------------------------------------");
        
        deleteFromList(arrayList);
        deleteFromList(linkedList);
        deleteFromList(vector);
    }
}

                                                                        ##

插入 100000元素ArrayList花费 3900 毫秒
插入 100000元素LinkedList花费 15 毫秒
插入 100000元素Vector花费 3933 毫秒
--------------------------------------
读取100000元素ArrayList花费 0 毫秒
读取100000元素LinkedList花费 8877 毫秒
读取100000元素Vector花费 16 毫秒
--------------------------------------
删除100000元素ArrayList花费 4618 毫秒
删除100000元素LinkedList花费 16 毫秒
删除100000元素Vector花费 4759 毫秒

        从上面的运行结果我们可以清晰的看出ArrayList、LinkedList、Vector增加、删除、遍历的效率问题。下面我就插入方法add(int index, E element),delete、get方法各位如有兴趣可以研究研究。

        首先我们先看三者之间的源码：

        ArrayList

public void add(int index, E element) {
        rangeCheckForAdd(index);   //检查是否index是否合法

        ensureCapacityInternal(size + 1);  //扩容操作
        System.arraycopy(elementData, index, elementData, index + 1, size - index);    //数组拷贝
        elementData[index] = element;   //插入
        size++;
    }

        rangeCheckForAdd、ensureCapacityInternal两个方法没有什么影响，真正产生影响的是System.arraycopy方法，该方法是个JNI函数，是在JVM中实现的。声明如下：

public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

        目前LZ无法看到源码，具体的实现不是很清楚，不过System.arraycopy源码分析对其进行了比较清晰的分析。但事实上我们只需要了解该方法会移动index后面的所有元素即可，这就意味着ArrayList的add(int index, E element)方法会引起index位置之后所有元素的改变，这真是牵一处而动全身。

        LinkedList 

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)     //插入位置在末尾
            linkLast(element);
        else                   
            linkBefore(element, node(index));
    }

        该方法比较简单，插入位置在末尾则调用linkLast方法，否则调用linkBefore方法，其实linkLast、linkBefore都是非常简单的实现，就是在index位置插入元素，至于index具体为知则有node方法来解决，同时node对index位置检索还有一个加速作用，如下：

Node<E> node(int index) {
        if (index < (size >> 1)) {    //如果index 小于 size/2 则从头开始查找
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {   //如果index 大于 size/2 则从尾部开始查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

        所以linkedList的插入动作比ArrayList动作快就在于两个方面。1：linkedList不需要执行元素拷贝动作，没有牵一发而动全身的大动作。2:查找插入位置有加速动作即：若index < 双向链表长度的1/2，则从前向后查找; 否则，从后向前查找。

        Vector

        Vector的实现机制和ArrayList一样，同样是使用动态数组来实现的，所以他们两者之间的效率差不多，add的源码也一样，如下：

public void add(int index, E element) {
        insertElementAt(element, index);
    }
    
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

        上面是针对ArrayList、LinkedList、Vector三者之间的add（int index,E element)方法的解释，解释了LinkedList的插入动作要比ArrayList、Vector的插入动作效率为什么要高出这么多！至于delete、get两个方法LZ就不多解释了。

        同时LZ在写上面那个例子时发现了一个非常有趣的现象，就是linkedList在某些时候执行add方法时比ArrayList方法会更慢！至于在什么情况？为什么会慢LZ下篇博客解释，当然不知道这个情况各位是否也遇到过？？

2.2、Vector和ArrayList的区别

        四、更多

        java提高篇（二一）-----ArrayList

        java提高篇（二二）-----LinkedList

        java提高篇（二九）-----Vector

                                                                                                                  This is the content summarized in Java Improvement Chapter (32)-----List. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!

---