First, review the outline of a List

List is an interface that inherits from Collection’s interface. It represents an ordered queue. AbstractList is an abstract class that extends from AbstractCollection. AbstractList implements the List interface functions other than size() and get(int location). AbstractSequentialList is an abstract class that inherits AbstractList. AbstractSequentialList implements “all functions that operate linked lists based on index values”.

ArrayList, LinkedList, Vector, Stack are the four implementation classes of List. An ArrayList is an array queue, the equivalent of a dynamic array. It is implemented by array, and the efficiency of random access is high, but the efficiency of random insertion and random deletion is low. LinkedList is a two-way LinkedList. It can also operate as a stack, queue, or double-endian queue. The random access efficiency of LinkedList is low, but the random insertion and deletion efficiency is low. A Vector is a Vector queue, and like an ArrayList, it is a dynamic array, implemented by arrays. But ArrayList is thread-safe, whereas Vector is thread-safe. A Stack is a Stack, which inherits from a Vector. Its features are: FILO, First In Last Out.

The ultimate goal of learning something is to be able to understand and use it. The following is a brief description of the usage scenarios of each List, and then analyze the reasons.

If it involves “stack”, “queue”, “linked List”, etc., you should consider using List, which List to choose according to the following criteria. (01) Use LinkedList for quick insertion and removal of elements. (02) For elements that require fast random access, ArrayList should be used. (03) In a “single-threaded environment” or “multi-threaded environment, but a List can only be operated on by a single thread”, asynchronous classes (such as ArrayList) should be used. In a multi-threaded environment where a List can be operated on by multiple threads at the same time, a synchronized class (such as Vector) should be used.

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

View Code runs 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 100000 elements by position use time：10809 ms ArrayList : read 100000 elements by position use time：5 ms

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: 15 ms ArrayList: Delete 100000 elements from the 1st position use time: 1909 ms delete 100000 elements from the 1st position use time: 1909 ms Removing 100,000 elements takes the shortest LinkedList time: 15ms. LinkedList takes the longest time to traverse 100,000 elements: 10809 ms; ArrayList, Stack, and Vector are similar, all in seconds.

Consider that Vector supports synchronization, and Stack inherits from Vector; Therefore, it is concluded that (01) for quick insertion and removal of elements, you should use LinkedList. (02) For elements that require fast random access, ArrayList should be used. (03) For “single-threaded” or “multi-threaded, but a List can only be operated on by a single thread”, use asynchronous classes.

Let’s take a look at why LinkedList inserts quickly and ArrayList inserts slowly!

The code for inserting elements to the specified location in linkedlist.java looks like this:

Public void add(int index, E element) {addBefore(element, (index==size? header : entry(index))); }

/ / get a double linked list specify the location of the node private Entry Entry (int index) {if (index < 0 | | index > = size) throw new IndexOutOfBoundsException(“Index: “+index+ “, Size: “+size); Entry e = header; // Get the node at index. // If index < 1/2 of the length of the bidirectional list, look backwards; // Otherwise, look forward from back. 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 (node data is E) before the entry node. Private Entry addBefore(E E, Entry Entry) {// Create node newEntry and insert newEntry before node E; And the data that sets newEntry is e Entry newEntry = New Entry(e, Entry, entry.previous); // Insert newEntry into the list newentry.previous. next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; } add(int index, E element) to LinkedList First, find the index of the node to insert in the bidirectional list. Once found, insert a new node. If index is less than 1/2 of the length of the bidirectional list, the bidirectional list searches backwards and forwards. Otherwise, look backwards.

Next, we look at the code in ArrayList.java that inserts elements to the specified location. As follows:

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++;
Copy the code

} The copy code ensureCapacity(size+1) is used to “confirm the capacity of the ArrayList and increase the capacity if it is insufficient.” Arraycopy (elementData, index, elementData, index + 1, size-index);

The arrayCopy () declaration in the Java /lang/ system.java JDK package reads 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 is available in the OpenJDK package. Arraycopy () = arrayCopy (); arrayCopy () = arrayCopy (); System.arraycopy(elementData, index, elementData, index + 1, size – index); It moves everything after index. This means that the add(int index, E element) function of the ArrayList will cause all elements after the index to change!

From the above analysis, we can understand why elements are inserted quickly in LinkedList and slowly in ArrayList. “Delete elements” and “insert elements” work in a similar way, but I won’t go into details here.

Next, let’s look at “why random access is slow in linkedLists and fast in ArrayLists.”

Take a look at the code for random access to LinkedList

Public E get(int index) {return entry(index).element; }

/ / get a double linked list specify the location of the node private Entry Entry (int index) {if (index < 0 | | index > = size) throw new IndexOutOfBoundsException(“Index: “+index+ “, Size: “+size); Entry e = header; // Get the node at index. // If index < 1/2 of the length of the bidirectional list, search first; // Otherwise, look forward from back. 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; } get the index of the LinkedList from get(int index). First, find the index element in the bidirectional list. Find it and return. If index is less than 1/2 of the length of the bidirectional list, the bidirectional list searches backwards and forwards. Otherwise, look backwards.

Let’s look at the code for random access to ArrayList

Public E get(int index) {RangeCheck(index);

return (E) elementData[index];
Copy the code

}

private void RangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException( “Index: “+index+”, Size: “+size); Get (int index) ArrayList index (int index); Returns the element in the array at index position without having to look it up like a LinkedList.

The similarities between Vector and ArrayList in Part 4

1 They’re all lists

They both inherit from AbstractList and implement the List interface. The ArrayList and Vector classes are defined as follows:

Public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable

Public class Vector extends AbstractList implements List, RandomAccess, Cloneable, Java.io.Serializable {} copies the code

Both implement RandomAccess and Cloneable interfaces

Implementing the RandomAccess interface means that they all support fast RandomAccess; Implementing the Cloneable interface means they can clone themselves.

3 They are all implemented through arrays, which are essentially dynamic arrays

Arraylist. Java defines the array elementData to hold elements

Private TRANSIENT Object[] elementData; private transient Object[] elementData; The array elementData is also defined in vector. Java to hold elements

Protected Object[] elementData;

4 Their default array size is 10

If no size is specified when creating an ArrayList or Vector; The default capacity is 10.

The default constructor for ArrayList is as follows:

// ArrayList constructor. The default capacity is 10. public ArrayList() { this(10); } Vector’s default constructor looks like this:

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

5 They both support Iterator and listIterator traversal

Both of them inherit from AbstractList, which implements “iterator() returns iterator” and “listIterator() returns listIterator”, respectively.

The difference

Thread safety is different

ArrayList is thread-safe; Vector, on the other hand, is thread-safe and its functions are synchronized. ArrayList works with a single thread, Vector works with multiple threads.

2 different support for serialization

ArrayList supports serialization, whereas Vector does not. That is, ArrayList implements java.io.Serializable interface, whereas Vector does not.

ArrayList has three constructors, whereas Vector has four constructors. In addition to the three constructors that Vector contains, like ArrayList, another constructor can specify a capacity increase factor.

The constructors of ArrayList are as follows:

Copy code // Default constructor ArrayList()

// Capacity is the default capacity of ArrayList. When capacity is insufficient due to increased data, half of the previous capacity is added. ArrayList(int capacity)

ArrayList ArrayList(collection <? Extends E> collection) extends E> collection) extends E> collection) extends E> collection) extends E> collection

// The default constructor Vector()

// Capacity is the default size of Vector. When the capacity is increased due to increased data, the capacity is doubled each time. Vector(int capacity)

Vector(collection <? extends E> collection)

Capacity is the default capacity of the Vector, and capacityIncrement is the increment each time the Vector increases capacity. Vector(int capacity, int capacityIncrement) copies the code

4 Different capacity increase methods

When adding elements one by one, if the capacity of the ArrayList is insufficient, New capacity = (original capacity x3)/2 + 1. The capacity growth of Vector is dependent on the “growth coefficient”. If the “growth coefficient” is specified and the “growth coefficient is valid (i.e., greater than 0)”, the capacity growth of Vector is dependent on the “growth coefficient”. Then, each time there is insufficient capacity, “new capacity” = “original capacity + growth factor”. If the growth coefficient is invalid (i.e., less than/equal to 0), then “new capacity” = “original capacity x 2”.

The main functions for capacity growth in ArrayList are as follows:

Public void ensureCapacity(int minCapacity) {// change the count +1 modCount++; int oldCapacity = elementData.length; // Set 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 for increasing the capacity in Vector is as follows:

Private void ensureCapacityHelper(int minCapacity) {int oldCapacity = elementData.length; // When the Vector does not have enough capacity to hold all the current elements, increase the capacity. // If capacityIncrement>0, increment the capacity if capacityIncrement // otherwise, increment the capacity. if (minCapacity > oldCapacity) { Object[] oldData = elementData; int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } elementData = Arrays.copyOf(elementData, newCapacity); }} Copy the code

5 Support Enumeration. Vectors support Enumeration traversal, while lists do not

The code for Enumeration in a Vector looks like this:

Public Enumeration elements() {return new Enumeration() {int count = 0;

Public Boolean hasMoreElements() {return count < elementCount; Public E nextElement() {synchronized (vector.this) {if (count < elementCount) {return (E)elementData[count++]; } } throw new NoSuchElementException("Vector Enumeration"); }};Copy the code

}