What is an advantage of an ArrayList when compared to a linked list?

Difference between ArrayList and LinkedList

ArrayList and LinkedList both implements List interface and maintains insertion order. Both are non synchronized classes.

However, there are many differences between ArrayList and LinkedList classes that are given below.

Example of ArrayList and LinkedList in Java

Let's see a simple example where we are using ArrayList and LinkedList both.

Output:

ArrayList vs LinkedList in Java

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. However, the limitation of the array is that the size of the array is predefined and fixed. There are multiple ways to solve this problem. In this article, the difference between two classes that are implemented to solve this problem named ArrayList and LinkedList is discussed.

ArrayList is a part of the collection framework. It is present in the java.util package and provides us dynamic arrays in Java. Though, it may be slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed. We can dynamically add and remove items. It automatically resizes itself. The following is an example to demonstrate the implementation of the ArrayList.

Example

Java

// Java program to Illustrate Working of an ArrayList // Importing required classes import java.io.*; import java.util.*; // Main class class GFG { // Main driver method public static void main(String[] args) { // Creating an ArrayList of Integer type ArrayList<Integer> arrli = new ArrayList<Integer>(); // Appending the new elements // at the end of the list // using add () method via for loops for (int i = 1; i <= 5; i++) arrli.add(i); // Printing the ArrayList System.out.println(arrli); // Removing an element at index 3 // from the ArrayList // using remove() method arrli.remove(3); // Printing the ArrayList after // removing the element System.out.println(arrli); } }

Output

[1, 2, 3, 4, 5] [1, 2, 3, 5]

LinkedList is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node. Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. The following is an example to demonstrate the implementation of the LinkedList.

Note: This class implements the LinkedList Data Structure.

Example

Java

// Java program to Demonstrate Working of a LinkedList // Importing required classes import java.util.*; // Main class class GFG { // main driver method public static void main(String args[]) { // Creating an object of the // class linked list LinkedList<String> object = new LinkedList<String>(); // Adding the elements to the object created // using add() and addLast() method // Custom input elements object.add("A"); object.add("B"); object.addLast("C"); // Print the current LinkedList System.out.println(object); // Removing elements from the List object // using remove() and removeFirst() method object.remove("B"); object.removeFirst(); System.out.println("Linked list after " + "deletion: " + object); } }

Output: [A, B, C] Linked list after deletion: [C]

Now after having an adequate understanding of both of them let us do discuss the differences between ArrayList and LinkedList in Java

ArrayList	LinkedList
This class uses a dynamic array to store the elements in it. With the introduction of generics, this class supports the storage of all types of objects.	This class uses a doubly linked list to store the elements in it. Similar to the ArrayList, this class also supports the storage of all types of objects.
Manipulating ArrayList takes more time due to the internal implementation. Whenever we remove an element, internally, the array is traversed and the memory bits are shifted.	Manipulating LinkedList takes less time compared to ArrayList because, in a doubly-linked list, there is no concept of shifting the memory bits. The list is traversed and the reference link is changed.
This class implements a List interface. Therefore, this acts as a list.	This class implements both the List interface and the Deque interface. Therefore, it can act as a list and a deque.
This class works better when the application demands storing the data and accessing it.	This class works better when the application demands manipulation of the stored data.

Article Tags :

Difference Between

Java

Java-ArrayList

Java-Collections

java-LinkedList

java-list

Practice Tags :

Java

Java-Collections

1. Overview

When it comes to collections, the Java standard library provides plenty of options to choose from. Among those options are two famousListimplementations known asArrayListandLinkedList,each with their own properties and use-cases.

In this tutorial, we're going to see how these two are actually implemented. Then, we'll evaluate different applications for each one.

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation.get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.

4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.

There are fewsimilarities betweenthese classes which are as follows:

1. Both ArrayList and LinkedList are implementation of List interface.
2. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
3. Both these classes are non-synchronized and can be made synchronized explicitly by usingCollections.synchronizedList method.
4. The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).

When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

References:

• ArrayList documentation
• LinkedList Javadoc

What is ArrayList?

ArrayList is the simplest list that can store different types of data. To understand ArrayList, consider the following data stored in an array –

where Student is a class that holds information about students of a college like a name, age, subject, average marks, email id, gender, and whether they have distinguishing marks or not.

Details of each Student are stored in an array, names. The array size is fixed as 5. However, what happens if there are more students than 5?

With ArrayList, this problem will not occur. ArrayList is a dynamic array, which grows in size as the number of elements increases.

As we see, there is no initial size given to the list. It can just add elements as the list grows. In fact, any type of manipulation is easy with ArrayList. If you want to access any element of the list, you can easily get it using the index. The first index is always zero. Suppose, you want to replace the name “Mary” to “Maryln”, you could do the following –

We have removed the previous name and added the new one in the same place. You can also add elements at any location. For example,

This will not replace ‘Maryln’ but will move it to the next index. If you print the list you will get –

This means to accommodate ‘Joseph’, all the other elements have been shifted to the right. Same way, when we removed Mary, all the other elements had to be moved to the left.

Duplicate values are perfectly acceptable in ArrayList. If we add another element with the same name, the list size will grow and the value will be displayed without any issue.

ArrayList implements the List interface which in turn extends the interface Collection. The collection is extended by the Iterable interface. The hierarchy of ArrayList is as follows

Source: Javadocs

It is also easy to sort objects in ascending or descending order with ArrayList using the method sort of the Java .util.Collections class.

ArrayList is not synchronized, which means if multiple threads change a list at the same time, the result could be unpredictable. We can also add a value of null to an ArrayList, which will be displayed at its position as “null”.

One of the most famous interview questions for beginners as well as Java developers with two-three years of experience is the difference between ArrayList and LinkedList.

Before getting into differences, let’s understand the similarities between ArrayList and LinkedList so that it will not be challenging to know the differences. Some of the similarities are as follows:

• Both implements List interface and they got default behaviour of list interface, i.e., both are ordered collection, and they will maintain insertion order.
• Both allow inserting null as well as different types of objects.
• Both implements cloneable interface both the elements themselves are not cloned.
• Both are not synchronised collections which can be synchronised through using Collections.synchronisedList()method.
• Iterator and list Iterator methods for both are fail-fast which will throw ConcurrentModificationException whereas fail-safe will not throw that.

Now let’s have a brief introduction about “What is ArrayList?” and “What is LinkedList?” ArrayList is a growable array which has an initial capacity of ten. After reaching its maximum capacity, a new ArrayList is created with increased capacity, and all the records will be copied in the new ArrayList. The formula for new ArrayList’s capacity is New Capacity = Current capacity*1.5+1 ArrayList can be created with the required initial capacity. Since ArrayList implements a random access interface, it is good to use when its elements are fetched frequently. ArrayList is not good to use for frequent addition and deletion of elements due to multiple shift operations.

LinkedList internally maintains doubly-linked lists which store the memory address of previous and next object, so there will be no kind of structure which will keep memory address of the previous node and next node. There is no initial capacity defined for LinkedList, and it is not implementing a RandomAccess interface. LinkedList is faster than ArrayList while inserting and deleting elements, but it is slow while fetching each element.

Apples and Oranges are different –
Let’s get into the differences between ArrayList and LinkedList.

Applications and Limitations
In an ArrayList, the maximum number of elements in the data structure should be none else
you cannot opt for ArrayList. You can initialise with an initial capacity which protects duplicating
and wrong array allocations. ArrayList is indexed by int. So, it can go up to 32bits. Hence in an
ArrayList, it is not possible to store elements that are more than 2^32.

LinkedList works better even when the addition rate is greater than the read rate. For instance,
let us take a list with a time sequence. You will get numerous answers at each second. In this
type of case, LinkedList is considered a better choice since the addition rate is higher.

• Implementation: ArrayList is a growable array implementation and implements RandomAccess interface while LinkedList is doubly-linked implementation and does not implement RandomAccess interface. Example: Having a collection of 10 million objects, implementing the RandomAccess interface takes the same time to retrieve the 9th element and 16599th element. This makes ArrayList more powerful. Elements from both LinkedList and ArrayList can be accessed randomly; however, ArrayList’s time complexity is O(1), and LinkedList is O(n).
• Capacity and Fetching of elements: Initial capacity for Array list is ten which can be changed while in LinkedList there is no initial capacity. ArrayList is useful for fetching elements from the middle of the collection. But it is not suitable for addition or deletion of elements while LinkedList is excellent for adding and deleting elements from the centre of the collection.
• Memory Consumption: ArrayList consumes less memory than LinkedList as it stores only data of a particular index. In comparison, LinkedList consumes more memory than ArrayList as it holds the address of previous and next object and value of the actual item. ArrayList elements are stored in consecutive memory locations, while LinkedList nodes are stored randomly in memory locations. ArrayList holds real data and its index while LinkedList holds data on each node. Link-list would be better since it doesn’t double in size when the max is reached. Let’s say you have 251 names and then the array doubles to 500 when you get 250. you then allocated 249 different spots in memory for nothing. In the long run, LinkedList is better compared to ArrayList as far as memory goes.
• Based on Data structure: ArrayList is indexed based data structure where an array index is put to access a particular element. E.g.: [5] where 5 is the index, you can access the element with the help of the index. LinkedList is a reference-based data structure whereby knowing the address only; you can go into a particular location and find the data. ArrayList is a static data structure where elements are allocated during compile time while LinkedList is a dynamic data structure where node position is assigned during run time.
• Accessing of elements: In ArrayList elements can be directly or randomly accessed while in LinkedList, the elements can be accessed only sequentially. E.g., In ArrayList let us say A6 is given and if you want to go to the third element, you can write A[2], and it directly goes to the third element, but it’s not possible in LinkedList.
• Speed of operation – Who’s the fastest: Comparing the speed of operation between ArrayList and LinkedList, check with the use of add() get() remove(). Complexity of time in ArrayList can be tested with the usage of get() – O(1) , add() – O(1) , remove() – O(n) and in LinkedList get() – O(n) , add() – O(1) , remove() – O(n). Testing your code with these examples will help you determine the time difference between ArrayList and LinkedList. Observing the test codes, you can be clear that LinkedList is faster in add and remove compared to ArrayList. ArrayList is faster in get(). Elements to be added or removed are too large, go for LinkedList. Usage of get() is more, go for ArrayList. Again, if you don’t have element access in a large number, go for LinkedList.
• Performance of ArrayList and LinkedList: Both have pros and cons in it. In a LinkedList, adding the elements is unlimited while in an ArrayList, it is restricted to a specific value as it is constrained. It can also be resized but resizing is a bit costly operation, and you can go with LinkedList in this case. Removing the elements in a LinkedList is easy too, but in an ArrayList, eliminating elements will leave empty memory spaces which are wastage in your device. In a LinkedList, the node contains both the data it has and the data to the adjacent node. Hence, LinkedList holds more memory space. LinkedList could be used for large lists of data since the total elements vary accordingly. In an ArrayList, the maximum elements in the list will be known, and it can be used for small lists.
• Interfaces in the two: In an ArrayList, list interface is implemented by the class. List interface is the inherited interface of the collection. It stores the collection in sequence. It implements the list interface which extends to the collection. In a LinkedList, both list interface and deque interface are implemented by the class. “Double-ended queue” is abbreviated as Deque. Its interface is a branch of queue interface. It supports adding and removing the elements from both ends of the data. Removing/ adding can be done either in a queue or stack. In a queue, the data works in First-in-first-out (FIFO) and a stack, the data fits in last-in-first-out (LIFO). Data adding or data removal is double-ended in Deque. LinkedList and ArrayDeque implement the Deque interface which extends to the queue interface, then to the collection, finally it extends to the iterable interface. ArrayList and LinkedList based on operations performed. If you are using retrieval operations frequently, go for ArrayList. Retrieval operation means collecting the data from a data structure, which can be stored, viewed and printed. ArrayList performs shift operations internally, so the insertion of data in the middle or deletion in the middle is complicated. If you are opting these operations, ArrayList won’t be the best. It stores elements in different memory locations, and hence the process of retrieval will be convenient. If you are performing insertion of data in the middle or deletion of data in the middle is relatively easy, hence go for LinkedList. It works best for frequent addition or deletion in the middle. They do not store elements in different memory locations, and therefore, if you are looking for more Retrieval operations, LinkedList is not the best one. In a retrieval operation, the elements should be stored in consecutive memory locations else it won’t be easy.
• Applications and Limitations: In an ArrayList, the maximum number of elements in the data structure should be none else you cannot opt for ArrayList. You can initialise with an initial capacity which protects duplicating and wrong array allocations. It is indexed by int. So, it can go up to 32bits. Hence in an ArrayList, it is not possible to store elements that are more than 2^32. LinkedList works better even when the addition rate is greater than the read rate. For instance, let us take a list with a time sequence. You will get numerous answers at each second. In this type of case, LinkedList is considered a better choice since the addition rate is higher.

Conclusion
As you’ve reached the end of this article, we hope you are now familiar with the pros and cons of the two. It is dependent on the usage of the list and your requirement. We have summarised implementation, some of the main applications and limitations to make it easier for you to take the first few steps in mastering these concepts. You decide to choose the better option for your use-case.

To explore more topics to read, click here.

When to use ArrayList vs LinkedList in Java