Analysis on the difference between ArrayList and LinkList in Java

It implements a data structure based on dynamic arrays, and LinkedList is based on a data structure based on a linked list.
2. For random access to get and set, ArrayList is better than LinkedList because ArrayList can be positioned randomly, while LinkedList needs to move the pointer to the node step by step. (Refer to arrays and linked lists for thinking)
3. For the addition and deletion operations add and remove, LinedList is more advantageous. It only needs to modify the pointer, while ArrayList needs to move data to fill the space of the deleted object.

ArrayList and LinkedList are two collection classes that store a series of object references. For example, we can use ArrayList to store a series of Strings or Integers. So what is the difference in performance between ArrayList and LinkedList? When should I use ArrayList? When should I use LinkedList?

one. Time complexity

First of all, the key is that the internal implementation of ArrayList is based on the basic object array, so when it uses the get method to access any element in the list (random-access), it is faster than LinkedList. The get method in LinkedList is to check from one end of the list in order to the other end. For LinkedList, there is no faster way to access a specified element in the list.

Suppose we have a large list, and the elements in it are already sorted. This list may be of ArrayList type or LinkedList type. Now we will search this list in binary (binary search) and compare the query speed of ArrayList and LinkedList. See the following program:

LinkedList consumption time: 2596

This result is not fixed, but basically the time of ArrayList is significantly smaller than that of LinkedList. Therefore, in this case, LinkedList is not suitable. The random access strategy used by the binary search method, while LinkedList does not support fast random access. The time it takes to do random access to a LinkedList is proportional to the size of the list. Accordingly, the time it takes to perform random access in ArrayList is fixed.

Does this indicate that ArrayList always performs better than LinkedList? This is not necessarily the case, and in some cases LinkedList performs better than ArrayList, and some algorithms are more efficient when implemented in LinkedList. For example, when using methods to invert the list, its performance is better.

Looking at an example like this, if we have a list that needs to perform a lot of insertion and deletion operations, LinkedList is a better choice in this case. Please see the following extreme example, we repeatedly insert an element at the beginning of a list:

At this time, my output result is: ArrayList time-consuming: 2463

LinkedList time taken: 15

This is in contrast to the results of the previous example. When an element is added to the beginning of the ArrayList, all existing elements will be moved backwards, which means the overhead for data movement and copying. Instead, adding an element to the beginning of LinkedList is simply to assign a record to the element and then adjust the two connections. The overhead of adding an element at the beginning of a LinkedList is fixed, while the overhead of adding an element at the beginning of an ArrayList is proportional to the size of the ArrayList.

two. Space complexity

There is a private inner class in LinkedList, defined as follows:

private static class Entry {
         Object element;
         Entry next;
         Entry previous;
     }

Each Entry object reference list has an element, as well as its previous and next element in LinkedList. A LinkedList object with 1000 elements will have 1000 Entry objects linked together, each corresponding to an element in the list. In this way, there will be a large space overhead in a LinkedList structure because it stores the relevant information of these 1000 Entity objects.

ArrayList uses a built-in array to store elements, and the starting capacity of this array is 10. When the array needs to grow, the new capacity is obtained as follows: New capacity = (old capacity * 3)/2+1, which means that the capacity will increase by about 50% each time. This means that if you have an ArrayList object with a large number of elements, then there will be a lot of space to be wasted in the end, which is caused by the way ArrayList works itself. If there is not enough space to store new elements, the array will have to be reassigned so that new elements can be added. Reassigning the array will result in a sharp drop in performance. If we know how many elements an ArrayList will have, we can specify the capacity through the constructor method. We can also use the trimToSize method to remove the wasted space after the ArrayList is allocated.

three. Summarize

ArrayList and LinkedList have their own advantages and disadvantages in performance, and they all have their own applicable areas. Generally speaking, it can be described as follows:

Performance Summary:

1. For ArrayList and LinkedList, the overhead of adding an element at the end of the list is fixed. For ArrayList, it is mainly to add an item to the internal array, pointing to the added elements, which may occasionally lead to reassigning the array; for LinkedList, this overhead is unified, allocating an internal Entry object.

2. Inserting or deleting an element in the middle of an ArrayList means that the remaining elements in the list will be moved; the overhead of inserting or deleting an element in the middle of an LinkedList is fixed.

3. LinkedList does not support efficient random element access.

4. The space waste of ArrayList is mainly reflected in the reservation of a certain capacity space at the end of the list, while the space cost of LinkedList is reflected in the fact that every element of it needs to consume a considerable space.

It can be said that when an operation adds data behind a column of data rather than in front or in the middle, and requires random access to elements in it, using ArrayList will provide better performance; when your operation adds or deletes data in front or in the middle of a column of data, and accesses elements in it in order, you should use LinkedList.

The difference between ArrayList and List in Java

List collection
List inherits from the Collection interface. List is an ordered set. Elements in List can be obtained/deleted/inserted based on the index (sequence number: the location information of the element in the set).

Unlike Set collections, List allows duplicate elements. For e1 and e2 object elements that satisfy the (e2) condition, they can exist in the List collection at the same time. Of course, there are also List implementation classes that do not allow duplicate elements to exist.
At the same time, List also provides a listIterator() method, which returns a ListIterator interface object. Compared with the Iterator interface, ListIterator adds elements and other methods, which can also traverse forward or backward.

The relationship between List and Collection:
[I]
+-- [I]
   +-- [C]
   +-- [C]
   +-- [C]
      +-- [C]

The implementation classes of List interface mainly include ArrayList, LinkedList, Vector, Stack, etc.

Father-son relationship.
List is an interface, and ArrayList inherits and implements it.
When using it, you usually use ArrayList. You have never used List. You can use it like this: List list = new ArrayList();

Collection interface
Collection is the most basic collection interface. A Collection represents a set of Objects, that is, the elements of the Collection (Elements). Some Collections allow the same elements while others don't. Some can sort but others cannot. The Java SDK does not provide classes that are directly inherited from Collection. The classes provided by the Java SDK are all "subinterfaces" that are inherited from Collection such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: the parameterless constructor is used to create an empty Collection, and a Collection parameter constructor is used to create a new Collection, which has the same elements as the incoming Collection. The latter constructor allows the user to copy a Collection.

How to iterate through every element in the Collection? Regardless of the actual type of the Collection, it supports an iterator() method, which returns an iterator, and uses this iterator to access each element in the Collection one by one. Typical usages are as follows:
Iterator it = (); // Get an iterator
    while(()) {
Object obj = (); // Get the next element
       }
The two interfaces derived from the Collection interface are List and Set.

List interface:
List is an ordered collection, and this interface can accurately control the position of each element inserted. Users can use indexes (the position of elements in List, similar to array subscripts) to access elements in List, which is similar to Java's arrays.
Unlike the Set mentioned below, List allows the same elements.
In addition to the iterator() method that has the necessary collection interface, List also provides a listIterator() method, which returns a ListIterator interface. Compared with the standard Iterator interface, ListIterator has more methods such as add(), allowing adding, deleting, setting elements, and traversing forward or backward.
Common classes that implement List interfaces include LinkedList, ArrayList, Vector and Stack.

LinkedList class
LinkedList implements the List interface, allowing null elements. In addition, LinkedList provides additional get, remove, insert methods at the header or tail of the LinkedList. These operations enable LinkedList to be used as a stack, queue, or a two-way queue.
Note that LinkedList does not have a synchronization method. If multiple threads access a List at the same time, you must implement access synchronization by yourself. One workaround is to construct a synchronous List when creating it:
List list = (new LinkedList(...));

ArrayList class
ArrayList implements variable-sized arrays. It allows all elements, including null. ArrayList is not synchronized.
The run time of the size, isEmpty, get, set methods is constant. However, the overhead of the add method is an amortized constant, and it takes O(n) time to add n elements. The other methods have linear run time.
Each ArrayList instance has a Capacity, which is the size of the array used to store elements. This capacity can automatically increase as new elements are constantly added, but the growth algorithm is not defined. When a large number of elements need to be inserted, the ensureCapacity method can be called before inserting to increase the capacity of the ArrayList to improve insertion efficiency.
Like LinkedList, ArrayList is also unsynchronized.

Summarize
If stack, queue and other operations are involved, you should consider using List. For elements that need to be quickly inserted and deleted, you should use LinkedList. If elements need to be accessed quickly, you should use ArrayList.
Try to return the interface rather than the actual type, such as returning a List instead of an ArrayList. In this way, if you need to change the ArrayList to a LinkedList in the future, the client code does not need to be changed. This is for abstract programming.