Difference analysis of ArrayList and LinkList in Java
- 2020-04-01 01:54:40
- OfStack
1.ArrayList is a data structure based on dynamic array, while LinkedList is a data structure based on LinkedList.
2. For random access to get and set, ArrayList is better than LinkedList because ArrayList can be randomly located, while LinkedList moves the pointer to the node step by step. (think arrays and linked lists)
3. For the new and delete operations add and remove, LinedList is more dominant. It only needs to modify the pointer, while ArrayList moves the 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 an ArrayList to store a series of strings or integers. So what's the performance difference between an ArrayList and a LinkedList? When should I use ArrayList and when should I use LinkedList?
one Time complexity
First and foremost, the internal implementation of ArrayList is based on a basic array of objects, 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 in order from one end of the list to the other. There is no faster way for LinkedList to access a specific element in the list.
Suppose we have a large list of sorted elements, which may be of type ArrayList or LinkedList. Now let's perform binary search on the list, comparing the query speed of the list with that of the list on ArrayList and LinkedList, and see the following program:
package com.mangocity.test;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class TestList ...{
public static final int N=50000;
public static List values;
static...{
Integer vals[]=new Integer[N];
Random r=new Random();
for(int i=0,currval=0;i<N;i++)...{
vals=new Integer(currval);
currval+=r.nextInt(100)+1;
}
values=Arrays.asList(vals);
}
static long timeList(List lst)...{
long start=System.currentTimeMillis();
for(int i=0;i<N;i++)...{
int index=Collections.binarySearch(lst, values.get(i));
if(index!=i)
System.out.println("*** error ***");
}
return System.currentTimeMillis()-start;
}
public static void main(String args[])...{
System.out.println("ArrayList Time spent: "+timeList(new ArrayList(values)));
System.out.println("LinkedList Time spent: "+timeList(new LinkedList(values)));
}
}
The output I get is: ArrayList elapsed time: 15
LinkedList cost time: 2596
This result is not fixed, but basically the time of ArrayList is significantly less than the time of LinkedList. So LinkedList should not be used in this case. Binary search USES a randomaccess strategy, and LinkedList does not support fast randomaccess. The time spent doing a random visit to a LinkedList is proportional to the size of the list. Correspondingly, the time required for random access in the ArrayList is fixed.
Does this mean that arraylists always perform better than linkedlists? 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, when you reverse a list using the collections.reverse method, the performance is better.
Consider an example where LinkedList is a good choice if we have a list that requires a lot of insertions and deletions. In an extreme example, we repeatedly insert an element at the beginning of a list:
package com.mangocity.test;
import java.util.*;
public class ListDemo {
static final int N=50000;
static long timeList(List list){
long start=System.currentTimeMillis();
Object o = new Object();
for(int i=0;i<N;i++)
list.add(0, o);
return System.currentTimeMillis()-start;
}
public static void main(String[] args) {
System.out.println("ArrayList Time: "+timeList(new ArrayList()));
System.out.println("LinkedList Time: "+timeList(new LinkedList()));
}
}
My output is: ArrayList time: 2463
LinkedList takes time: 15
This is the opposite of the previous example, where when an element is added to the beginning of the ArrayList, all existing elements move back, which means overhead for data movement and replication. Instead, the beginning of adding an element to a LinkedList is simply to assign a record to that element and then adjust the two joins. The cost of adding an element to the beginning of a LinkedList is fixed, and the cost of adding an element to the beginning of an ArrayList is proportional to the size of the ArrayList.
two Spatial complexity
There is a private inner class in LinkedList, defined as follows:
Private static class Entry {
The Object element;
Entry next;
Entry previous;
}
Each Entry object is an element in the reference list, along with its previous and next elements in the LinkedList. A LinkedList object with 1,000 elements will have 1,000 linked Entry objects, each corresponding to an element in the list. In this case, there is a large space overhead on a LinkedList structure because it stores information about the 1000 Entity objects.
ArrayList USES a built-in array to store the elements, starting at 10. When the array needs to grow, the new capacity is obtained by the following formula: new capacity =(old capacity *3)/2+1, which means that the capacity grows by approximately 50% each time. This means that if you have an ArrayList object with a large number of elements, you end up wasting a lot of space because of the way the ArrayList works. If there is not enough space to hold new elements, the array will have to be redistributed so that new elements can be added. Redistributing arrays can result in a dramatic performance loss. 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 wasted space after ArrayList is allocated.
3. conclusion
Both ArrayList and LinkedList have their strengths and weaknesses in terms of performance, and each has its place, which can be summarized as follows:
Performance summary:
1. For both ArrayList and LinkedList, the overhead of adding an element to the end of the list is fixed. In the case of an ArrayList, the main thing is to add an item to the internal array, pointing to the added element, which may occasionally cause the array to be reassigned. For LinkedList, the overhead is uniform, assigning an internal Entry object.
2. Inserting or removing an element in the middle of an ArrayList means that the remaining elements in the list will be moved; The overhead of inserting or removing an element in the middle of a LinkedList is fixed.
3. LinkedList does not support efficient access to random elements.
4. The space waste of ArrayList is mainly reflected in the capacity space reserved at the end of the list, while the space cost of LinkedList is reflected in the amount of space each element of it consumes
It can be said that using ArrayList provides better performance when the operation is to add data after a column of data rather than in front or in the middle, and when the elements in it need to be accessed randomly. Use LinkedList when your action is to add or remove data before or in the middle of a column, and to access the elements in that column in order.
ArrayList, List distinction in Java
The List collection
List inherits from the Collection interface. List is an ordered collection in which the elements can be retrieved/deleted/inserted according to the index (sequence number: information about the position of the elements in the collection).
Unlike a Set Set, a List allows duplicate elements. Elements of the e1 and e2 objects that satisfy the e1.equals(e2) condition 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 that returns a listIterator interface object. Compared with the Iterator interface, listIterator can add, delete, and set elements, and can be traversed forward and backward.
Relationship between List and Collection:
Java. Util. Collection [I]
[I] + - Java. Util. List
+ - Java. Util. ArrayList [C]
+ - Java. Util. LinkedList [C]
+ - Java. Util. Vector [C]
+ - Java. Util. Stack [C]
The implementation classes of List interface mainly include ArrayList, LinkedList, Vector, Stack, etc.
Father-son relationship.
List is an interface that ArrayList inherits and implements.
I usually use ArrayList when I use it. I have never used List. I can use it like this :List List = new ArrayList();
The Collection interface
Collection is the most basic Collection interface. A Collection represents a group of objects, namely Elements of the Collection. Some collections allow the same elements and others do not. Some sort and some don't. The JavaSDK does not provide classes that directly inherit from the Collection, and the classes provided by JavaSDK are "sub-interfaces" that inherit from the Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: a constructor with no arguments to create an empty Collection, and a constructor with a Collection argument to create a new Collection that has the same elements as the incoming Collection. The latter constructor allows the user to copy a Collection.
How do I iterate through each element in the Collection? Regardless of the actual type of the Collection, it supports an iterator() method that returns an iterator that accesses each element of the Collection one by one. Typical usage:
The Iterator it = collection. The Iterator (); // gets an iterator
While (it. HasNext ()) {
The Object obj = it. Next (); // gets the next element
}
The two interfaces derived from the Collection interface are List and Set.
The List interface:
A List is an ordered Collection, and this interface allows you to precisely control where each element is inserted. The user can access the elements in a List using an index (the position of the elements in a List, similar to an array index), which is similar to an array in Java.
Unlike the sets mentioned below, a List is allowed to have the same elements.
In addition to the mandatory iterator() method with the Collection interface, the List also provides a listIterator() method that returns a listIterator interface. Compared with the standard iterator interface, listIterator has a few more methods like add(), allows you to add, delete, set elements, and iterate back and forth.
Common classes that implement the List interface are LinkedList, ArrayList, Vector, and Stack.
LinkedList class
LinkedList implements the List interface, allowing null elements. Additionally LinkedList provides additional get, remove, and insert methods at the beginning or end of a LinkedList. These actions enable LinkedList to be used as a stack, queue, or two-way queue.
Note that there is no synchronized method on LinkedList. If multiple threads access a List at the same time, you must implement the access synchronization yourself. One solution is to construct a synchronized List when creating a List:
List the List = Collections. SynchronizedList (new LinkedList (...). );
ArrayList class
ArrayList implements arrays of variable size. It allows all elements, including null. The ArrayList is not synchronized.
Size, isEmpty, get, set methods run at constant time. But the add method costs a amortized constant, and it takes O(n) to add n elements. Other methods run linearly.
Each ArrayList instance has a Capacity, the size of the array used to store the 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 before insertion to increase the capacity of the ArrayList to improve insertion efficiency.
Like LinkedList, ArrayList is unsynchronized.
conclusion
List should be considered if you are involved in stack, queue, etc. LinkedList should be used if you need to insert and delete elements quickly, and ArrayList should be used if you need to access elements randomly and quickly.
Try to return the interface instead of the actual type, such as a List instead of an ArrayList, so that the client code doesn't change if you later need to replace the ArrayList with a LinkedList. This is programming against the abstract.