Analysis of the difference between ArrayList and LinkList in java

1.ArrayList implements a data structure based on dynamic arrays, and LinkedList implements a data structure based on linked lists.
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. (Think with reference to arrays and linked lists)
3. For the new 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 used to store a series of object references. For example, we can use ArrayList to store a series of String or Integer. So what is the difference in performance between ArrayList and LinkedList? When should you use ArrayList and when should you use LinkedList?

one. time complexity

The first key point is that the internal implementation of ArrayList is based on a basic object array. Therefore, 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 checks from one end of the list to the other end in order. For LinkedList, there is no faster way to access a specific element in the list.

Suppose we have a large list, and the elements in it have been sorted. This list may be of ArrayList type or LinkedList type. Now we perform a binary search on this list. The comparison list is For the query speed of ArrayList and LinkedList, see the following program:

LinkedList time consumed: 2596

This result is not fixed, but basically the time of ArrayList is significantly less than that of LinkedList. Therefore LinkedList should not be used in this case. The binary search method uses a random access (randomaccess) strategy, and LinkedList does not support fast random access. The time consumed by random access to a LinkedList is proportional to the size of the list. Correspondingly, the time consumed for random access in ArrayList is fixed.

Does this mean that ArrayList always performs better than LinkedList? This is not necessarily true, in some cases LinkedList performs better than ArrayList, and some algorithms are more efficient when implemented in LinkedList. For example, the performance is better when using the Collections.reverse method to reverse a list.

Look at such an example, if we have a list and want to perform a large number of insertion and deletion operations on it, in this case LinkedList is a better choice. Consider the following extreme example, where we repeatedly insert an element at the beginning of a list:

At this time, my output is: ArrayList takes: 2463

LinkedList takes: 15

This is completely opposite to the result of the previous example. When an element is added to the beginning of the ArrayList, all existing elements will be moved backward, which means the overhead of data movement and copying. In contrast, adding an element to the beginning of a LinkedList simply assigns a record to the element and then adjusts the two links. The cost of adding an element to the beginning of a LinkedList is fixed, while the cost of adding an element to 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 references an element in the list, as well as its previous element and next element in the LinkedList. A LinkedList object with 1000 elements will have 1000 Entry objects linked together, each object corresponding to an element in the list. In this case, there will be a lot of space overhead in a LinkedList structure, because it needs to store the relevant information of these 1000 Entity objects.

ArrayList uses a built-in array to store elements. The starting capacity of this array is 10. When the array needs to grow, the new capacity is obtained according to the following formula: new capacity = (old capacity*3)/2+1, that is to say The capacity will increase by about 50% each time. This means that if you have an ArrayList object with a large number of elements, you will end up with a lot of wasted space. This waste is caused by the way ArrayList works. If there is not enough space to store the new element, the array will have to be reallocated so that the new element can be added. Reallocating the array will cause a drastic drop in performance. If we know how many elements an ArrayList will have, we can specify the capacity through the constructor. We can also use the trimToSize method to remove the wasted space after the ArrayList is allocated.

three. Summarize

ArrayList and LinkedList each have their own advantages and disadvantages in terms of performance, and each has its own application. Generally speaking, it can be described as follows:

Performance summary:

1. For both ArrayList and LinkedList, the cost of adding an element to the end of the list is fixed. For ArrayList, it mainly adds an item to the internal array, pointing to the added element, which may occasionally cause the array to be reallocated; for LinkedList, this overhead is uniform, 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; while inserting or deleting an element in the middle of a LinkedList has a fixed cost.

3． LinkedList does not support efficient random element access.

4． The space waste of ArrayList is mainly reflected in reserving a certain amount of space at the end of the list, while the space consumption of LinkedList is reflected in that each element of it needs to consume a considerable amount of space.

It can be said like this: When the operation is to add data after a column of data instead of in the front or middle, and you need to randomly access the elements, using ArrayList will provide better performance; when your operation is in front of a column of data When you add or delete data in the middle and access the elements in order, you should use LinkedList.

The difference between ArrayList and List in java

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

Unlike the Set collection, List allows duplicate elements. For e1 and e2 object elements that meet the conditions of e1.equals(e2), 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.
At the same time, List also provides a listIterator() method, which returns a ListIterator interface object. Compared with the Iterator interface, ListIterator adds methods for adding, deleting, and setting elements, and can also traverse forward or backward.

The relationship between List and Collection:
java.util.Collection[I]
+--java.util.List[I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C]
+--java.util.Stack [C]

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

Father-son relationship.
List is an interface, and ArrayList inherits this interface and implements it.
When using it, I usually use ArrayList. I 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. Some Collections allow identical elements and others do not. Some sort and others don't. The Java SDK does not provide classes that directly inherit from Collection. The classes provided by the Java SDK are all "sub-interfaces" that inherit from Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: a parameterless constructor for creating an empty Collection, and a Collection parameter constructor for creating a new Collection. The input Collection has the same elements. The latter constructor allows the user to copy a Collection.

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

List interface:
List is an ordered Collection. Using this interface, you can precisely control the insertion position of each element. Users can access elements in the List using the index (the position of the element in the List, similar to an array subscript), which is similar to a Java array.
Unlike the Set mentioned below, List allows the same elements.
In addition to the iterator() method necessary for the Collection interface, List also provides a listIterator() method, which returns a ListIterator interface. Compared with the standard Iterator interface, ListIterator has some more add() and other methods, allowing additions. Delete, set elements, and traverse forward or backward.
Common classes that implement the List interface are LinkedList, ArrayList, Vector and Stack.

LinkedList class
LinkedList implements the List interface and allows null elements. In addition, LinkedList provides additional get, remove, and insert methods at the head or tail of LinkedList. These operations allow LinkedList to be used as a stack, queue, or deque.
Note that LinkedList has no synchronized methods. If multiple threads access a List at the same time, they must implement access synchronization themselves. One workaround is to construct a synchronized List when creating the List:
List list = Collections.synchronizedList(new LinkedList(...));

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

Summary: If operations such as stacks and queues are involved, you should consider using List. If you need to quickly insert and delete elements, you should use LinkedList. If you need fast random access to elements, you should use ArrayList.
Try to return the interface rather than the actual type, such as returning List instead of ArrayList, so that if you need to replace ArrayList with LinkedList in the future, the client code does not need to change. This is programming for abstraction.