Use and performance analysis of JAVA LinkedList and ArrayList

Part 1 List summary
Block diagram of List
< img SRC = "border = 0 / / img.jbzj.com/file_images/article/201311/20131105104229.jpg? 2013105104846 ">
List is an interface that inherits from the Collection's interface. It represents an ordered queue.
An AbstractList is an abstract class that is subclassed from an AbstractCollection. AbstractList implements functions in the List interface other than size() and get(int location).
AbstractSequentialList is an abstract class that subclasses AbstractList. AbstractSequentialList implements "all functions of a linked list that operate on the index index value in a linked list".
ArrayList, LinkedList, Vector, Stack are the four implementation classes of List.
An ArrayList is an array queue that ACTS as a dynamic array. It is implemented by array, random access efficiency is high, random insertion, random deletion efficiency is low.
LinkedList is a two-way LinkedList. It can also be operated as a stack, queue, or double-ended queue. LinkedList random access efficiency is low, but random insertion and random deletion efficiency is low.
A Vector is a Vector queue, and like an ArrayList, it is a dynamic array, implemented by an array. But an ArrayList is not thread-safe, whereas a Vector is thread-safe.
A Stack is a Stack that inherits from a Vector. Its feature is: First In Last Out.

Part 2 lists usage scenarios
The ultimate purpose of learning something is to be able to understand and use it. The following is an overview of the usage scenarios of each List, and the reasons for this will be analyzed later.
If "stack", "queue", "linked List" and other operations are involved, we should consider using List, and choose which List specifically according to the following criteria.
(01) for quick inserts and deletes, use LinkedList.
(02) for elements that require quick random access, an ArrayList should be used.
(3)
For a "single-threaded" or "multi-threaded environment where a List is only manipulated by a single thread," you should use an asynchronous class (such as an ArrayList).
For "multi-threaded environments where a List may be operated on by multiple threads at the same time," you should use a synchronized class (such as a Vector).

We verify the above conclusions (01) and (02) through the following test procedure. The reference code is as follows:

import java.util.*;
import java.lang.Class;

public class ListCompareTest {
    private static final int COUNT = 100000;
    private static LinkedList linkedList = new LinkedList();
    private static ArrayList arrayList = new ArrayList();
    private static Vector vector = new Vector();
    private static Stack stack = new Stack();
    public static void main(String[] args) {
        //A newline
        System.out.println();
        //insert
        insertByPosition(stack) ;
        insertByPosition(vector) ;
        insertByPosition(linkedList) ;
        insertByPosition(arrayList) ;
        //A newline
        System.out.println();
        //Random reads
        readByPosition(stack);
        readByPosition(vector);
        readByPosition(linkedList);
        readByPosition(arrayList);
        //A newline
        System.out.println();
        //delete
        deleteByPosition(stack);
        deleteByPosition(vector);
        deleteByPosition(linkedList);
        deleteByPosition(arrayList);
    }
    //Gets the name of the list
    private static String getListName(List list) {
        if (list instanceof LinkedList) {
            return "LinkedList";
        } else if (list instanceof ArrayList) {
            return "ArrayList";
        } else if (list instanceof Stack) {
            return "Stack";
        } else if (list instanceof Vector) {
            return "Vector";
        } else {
            return "List";
        }
    }
    //Inserts COUNT elements into the list at the specified location and counts the time
    private static void insertByPosition(List list) {
        long startTime = System.currentTimeMillis();
        //Insert a COUNT into the list position 0
        for (int i=0; i<COUNT; i++)
            list.add(0, i);
        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(getListName(list) + " : insert "+COUNT+" elements into the 1st position use time : " + interval+" ms");
    }
    //Deletes COUNT elements from the specified location in the list and counts the time
    private static void deleteByPosition(List list) {
        long startTime = System.currentTimeMillis();
        //Delete the first location element of the list
        for (int i=0; i<COUNT; i++)
            list.remove(0);
        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(getListName(list) + " : delete "+COUNT+" elements from the 1st position use time : " + interval+" ms");
    }
    //According to position, constantly read the elements from the list and count the time
    private static void readByPosition(List list) {
        long startTime = System.currentTimeMillis();
        //Read the list element
        for (int i=0; i<COUNT; i++)
            list.get(i);
        long endTime = System.currentTimeMillis();
        long interval = endTime - startTime;
        System.out.println(getListName(list) + " : read "+COUNT+" elements by position use time : " + interval+" ms");
    }
}

The operation results are as follows:
Stack: insert 100000 elements into the 1st position use time: 1640 ms
Vector: insert 100000 elements into the 1st position use time: 1607 ms
LinkedList: insert 100000 elements into the 1st position use time: 29 ms
ArrayList: insert 100000 elements into the 1st position use time: 1617 ms
Stack: read 100000 elements by position use time: 9 ms
Vector: read 100000 elements by position use time: 6 ms
LinkedList: read 100,000 elements by position use time: 10809 ms
ArrayList: read 100000 elements by position use time: 5ms
Stack: delete 100000 elements from the 1st position use time: 1916 ms
Vector: delete 100000 elements from the 1st position use time: 1910 ms
LinkedList: delete 100000 elements from the 1st position use time: 15ms
ArrayList: delete 100000 elements from the 1st position use time: 1909 ms

From this, we can find:
With 100,000 elements inserted, LinkedList takes the shortest time: 29ms.
Removing 100,000 elements on LinkedList takes the shortest time: 15ms.
Traversing 100,000 elements, LinkedList took the longest time: 10809 ms; ArrayList, Stack and Vector are similar, all taking just a few seconds.
Considering that Vector supports synchronization, and Stack is inherited from Vector; Therefore, it is concluded that:
(01) for quick inserts and deletes, use LinkedList.
(02) for elements that require quick random access, an ArrayList should be used.
(3)
For a "single-threaded" or "multi-threaded environment, but a List is only manipulated by a single thread," you should use an asynchronous class.

 
Part 3 analysis of performance differences between LinkedList and ArrayList
Let's take a look at why LinkedList inserts elements quickly, while ArrayList inserts elements slowly!
The code for inserting an element into the specified location in linkedlist.java is as follows:

//Add a node before index and the value of the node is element
public void add(int index, E element) {
    addBefore(element, (index==size ? header : entry(index)));
}
//Gets the node at the specified location in the bidirectional linked list
private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    //Gets the node at index.
    //If the index <1/2 of the length of the two-way list, then look from front to back;
    //Otherwise, look backwards.
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}
//Add the node (the node data is e) before the entry node.
private Entry<E> addBefore(E e, Entry<E> entry) {
    //New node newEntry, insert newEntry before node e; And the data for setting newEntry is e
    Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
    //Insert newEntry into the linked list
    newEntry.previous.next = newEntry;
    newEntry.next.previous = newEntry;
    size++;
    modCount++;
    return newEntry;
}

From this, we can see that when you insert an element into a LinkedList by adding (int index, E element). First, the position index of the node to be inserted is found in the bidirectional linked list. Once found, insert a new node.
There is an accelerated action when a two-way linked list looks up a node at the index position: if index < 1/2 of the length of the two-way list, then look from front to back; Otherwise, look backwards.
Next, let's look at the code in arraylist.java that inserts an element at the specified location. As follows:

//Adds e to the specified location of the ArrayList
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);
    ensureCapacity(size+1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
         size - index);
    elementData[index] = element;
    size++;
}

The role of ensureCapacity(size+1) is to "verify the capacity of the ArrayList, and if the capacity is insufficient, increase the capacity."
The really time-consuming operation is system.arraycopy (elementData, index, elementData, index + 1, size-index);
Arraycopy () in Java /lang/ system.java for the Sun JDK package is declared as follows:
Public static native void arraycopy(Object SRC, int srcPos, Object dest, int destPos, int length);
Arraycopy () is a JNI function that is implemented in the JVM. The source code is not available in the sunJDK, but it is available in the OpenJDK package. There is an analysis of arraycopy(), please refer to: System. Arraycopy source analysis
In fact, we only need to know: System. Arraycopy (elementData, index, elementData, index + 1, size-index); I'm going to move index and then I'm going to move all the elements. This means that the add(int index, E element) function of ArrayList will cause all the elements after index to change!

From the above analysis, we can understand why LinkedList inserts elements quickly, while ArrayList inserts elements slowly.
The principle of "delete element" is similar to that of "insert element".

Next, let's look at "why random access is slow in LinkedList and fast in ArrayList."
Let's start with the code that LinkedList randomly accesses

//Returns the element of the specified location on LinkedList
public E get(int index) {
    return entry(index).element;
}
//Gets the node at the specified location in the bidirectional linked list
private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    //Gets the node at index.
    //If the index <1/2 of the length of the two-way list, the previous search;
    //Otherwise, look backwards.
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

From this, we can see that when we get the index element of LinkedList by get(int index). First, find the element to index in the bidirectional linked list; Find it and return.
There is an accelerated action when a two-way linked list looks up a node at the index position: if index < 1/2 of the length of the two-way list, then look from front to back; Otherwise, look backwards.
Now look at the code that ArrayList randomly accesses

//Gets the value of the element at the index position
public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}
private void RangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(
        "Index: "+index+", Size: "+size);
}

From this, we can see: get(int index) to get the index element of ArrayList. Returns the element at the index position in the array directly without looking it up like a LinkedList.
Part 3 compares Vector and ArrayList
In common
1 they're both lists
They both subclass AbstractList and implement the List interface.
The class definitions of ArrayList and Vector are as follows:

//The definition of the ArrayList
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
//The definition of the Vector
public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

They implement RandomAccess and Cloneable interfaces
Implement RandomAccess interface, which means they all support fast RandomAccess;
Implementing the Cloneable interface means they can clone themselves.

They are all implemented through arrays, which are essentially dynamic arrays
The array elementData is defined in arraylist.java to hold the elements
// saves an array of the data in the ArrayList
Private transient Object [] elementData;
The array elementData is also defined in vector.java to hold the elements
// holds an array of data in the Vector
Protected Object [] elementData;

4 their default array capacity is 10
  If the ArrayList or Vector is created, the capacity is not specified. The default size 10 is used.
The default constructor for ArrayList is as follows:

//ArrayList constructor. The default capacity is 10.
public ArrayList() {
    this(10);
}
Vector The default constructor is as follows: 
//Vector constructor. The default capacity is 10.
public Vector() {
    this(10);
}

5 they both support Iterator and listIterator traversal
Both are subclassed from an AbstractList, which implements "iterator() interface returns iterator" and "listIterator() returns listIterator iterator," respectively.

 
The difference
Thread safety is different
ArrayList is non-thread-safe;
A Vector is thread-safe and its functions are synchronized, which means they support synchronization.
ArrayList works for single threads and Vector works for multiple threads.
2 different support for serialization
  ArrayList supports serialization, but Vector does not. That is, ArrayList implements the java.io.Serializable interface, while Vector does not.
The number of constructors is different
An ArrayList has three constructors and a Vector has four. In addition to the three constructors that are similar to the ArrayList, the Vector contains an additional constructor that specifies the capacity increase factor.
The constructor of ArrayList is as follows:

//Default constructor
ArrayList()
//Capacity is the default capacity for ArrayList. When the capacity is insufficient due to increased data, the capacity is increased by half of the previous capacity.
ArrayList(int capacity)
//Create an ArrayList that contains the collection
ArrayList(Collection<? extends E> collection)
Vector Is as follows: 
//Default constructor
Vector()
//Capacity is the default capacity of a Vector. When the capacity is increased due to increased data, the capacity is doubled each time.
Vector(int capacity)
//Create a Vector that contains a collection
Vector(Collection<? extends E> collection)
//Capacity is the default size of a Vector, and capacity increment is the increment value each time the Vector's capacity is increased.
Vector(int capacity, int capacityIncrement)

4. Different ways of increasing capacity
When adding elements one by one, if the capacity of ArrayList is insufficient, "new capacity" = "(original capacity x3)/2 + 1".
While the capacity growth of Vector is related to the "growth coefficient", if the "growth coefficient" is specified, and the "growth coefficient is effective (that is, greater than 0)"; Then, each time the capacity is insufficient, "new capacity" = "original capacity + growth coefficient". If the growth coefficient is not valid (i.e., less than/equal to 0), "new capacity" = "original capacity x 2".
The main function of capacity growth in ArrayList is as follows:

public void ensureCapacity(int minCapacity) {
    //Will "modify statistics" +1
    modCount++;
    int oldCapacity = elementData.length;
    //If the current capacity is insufficient to accommodate the current number of elements, set the new capacity = "(original capacity x3)/2 + 1"
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

The main function of capacity growth in Vector is as follows:

private void ensureCapacityHelper(int minCapacity) {
    int oldCapacity = elementData.length;
    //When the capacity of the Vector is insufficient to hold all the current elements, increase the capacity.
    //If capacity increment coefficient> 0 (namely capacityIncrement> 0), then increment the capacity as increment
    //Otherwise, double the volume.
    if (minCapacity > oldCapacity) {
        Object[] oldData = elementData;
        int newCapacity = (capacityIncrement > 0) ?
            (oldCapacity + capacityIncrement) : (oldCapacity * 2);
        if (newCapacity < minCapacity) {
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

5 different support for Enumeration. A Vector supports traversing through an Enumeration, but a List does not
The code for implementing an Enumeration in a Vector is as follows:

public Enumeration<E> elements() {
    //Implement an Enumeration through an anonymous class
    return new Enumeration<E>() {
        int count = 0;
        //Does the next element exist
        public boolean hasMoreElements() {
            return count < elementCount;
        }
        //Gets the next element
        public E nextElement() {
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return (E)elementData[count++];
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}