Are you looking to know the difference between ArrayList vs. LinkedList
Lists provide easy ways to manipulate, store, and retrieve data. Lists are used extensively in all programming languages like C, C++, Java, Python, etc. The list is an interface extended from the generic Collection interface.
In this article, we will learn about ArrayList and LinkedList is used in Java, with examples and then go on to compare both of them to understand how each of these is used for different situations.
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
String[] names = new String[5];names[0] = "Mac";
names[1] = "Jony";
names[2] = "Mary";
names[3] = "Donald";
names[4] = "Phoebe";
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.
ArrayList namesList = new ArrayList[];namesList.add["Mac"];
namesList.add["Jony"];
namesList.add["Mary"];
namesList.add["Donald"];
namesList.add["Phoebe"];
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
namesList.remove[namesList.get[2]];namesList.add[2, "Maryln"];
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
[Mac, Jony, Joseph, Maryln, Donald, Phoebe]0 1 2 3 4 5
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.
What is LinkedList?
LinkedList is a linear data structure where each element of the list is referred to as a node that contains the element value and the pointer to the previous and next node. In Java, LinkedList is implemented as a doubly-linked list internally [although, Java also supports Singly Linked List]. In a doubly-linked list, each node has a reference to its next and previous nodes, other than containing the nodes actual value. Here is a quick diagram that represents a doubly linked list
The demarcation on the left of each item indicates previous pointer, and the demarcation on the right indicates the next pointer. Item 1 has the previous node pointer as null, whereas next points to item 2 in the list. item 2 has a previous pointer to item 1 and next to item 3. Since item 3 is the last element, the next pointer [of item3] is null and the previous pointer [of item3] is the same as the next pointer of item 2. This means both are same values and determine the sequence of the list.
The other types of LinkedList are Singly Linked List and Circular Linked List.
LinkedList has same features as ArrayList. For example, you get can objects using index using the get[] method, you can add, remove elements and store as many objects as you need. While coding, you will not see much difference between ArrayList and LinkedList. Our earlier example, when executed with LinkedList is as follows
LinkedList lnkdlst = new LinkedList[];lnkdlst.add["Mac"];
lnkdlst.add["Jony"];
lnkdlst.add["Mary"];
lnkdlst.add["Donald"];
lnkdlst.add["Phoebe"];
lnkdlst.add["Mac"];
System.out.println["The first element is - " + lnkdlst.get[0]];
System.out.println["The last element is - " + lnkdlst.get[lnkdlst.size[]-1]];
Collections.sort[lnkdlst];
System.out.println["Sorted linked list - " + lnkdlst];
lnkdlst.add[1, "Joana"];
lnkdlst.remove["Mac"];
System.out.println["After additions and deletions - " + lnkdlst];
As you will notice, we can add duplicates, and also the name Joana has been added at the index position 1. If we dont specify any index, elements are added to the end of the list. The insertions can be done anywhere in a LinkedList without having to change the index of every single item only the pointer needs to be updated thus making it faster.
Here is the sample output if you run the above code -
The first element is - MacThe last element is - Mac
Sorted linked list - [Donald, Jony, Mac, Mac, Mary, Phoebe, Steve]
After additions and deletions - [Donald, Jony, Mac, Mary, Phoebe, Steve, Joana, null]
Just like ArrayList, LinkedList is also not synchronized and can hold null values.
Here is the hierarchy of LinkedList
Source Javadocs
Here comes the first difference whereas ArrayList only implements List, LinkedList implements List and Queue both! Therefore, LinkedList is an implementation of both Deque and List and it inherits certain methods of Deque as well. One common example of that is the descendingIterator[] method which is not present in ArrayList. This method reverses the order of the list and returns an iterator i.e. the elements will be shown from tail to head
Iterator itr = lnkdlst.descendingIterator[];while [itr.hasNext[]] {
System.out.println["Value is : " + itr.next[]];
}
However, this doesnt change the original linked list.
What is Deque?
Deque is a double-ended queue. By implementing Deque, LinkedList can be used as a stack, list or queue. If you want to see more about this additional functionality of LinkedList, this page has some great insights to offer.
When to use an Array List?
If the project or application requires more of a search operation than to perform updates like add or delete then one must use array list over linked list as it requires a constant time i.e, O[1] time complexity for a search operation whereas a linked list has O [n/2] complexity.
When to use Linked List?
If the project or application requires more of an update operation like adding or deleting an element than to perform search then one must use linked list over array list as it requires a constant time for an update operation. Linked list along with manipulation also offers a dequeue
Operation which an array list does not implement. Linked List class has a Deque interface to get the functionality of a double ended queue in LinkedList. The ArrayList class doesn't implement the Deque interface.
Head-to-Head Comparison: Arraylist vs LinkedList in Java
Now that we have some knowledge of both, let us come to the differences:
| ArrayList | LinkedList |
| Implemented as a dynamic array using an array of objects to store elements sequentially | Implemented as a doubly-linked list [in Java], consists of pointers to previous and next nodes. |
| Implements the List interface | Implements List and Deque [double ended Queue] which gives it additional functionality |
| Faster to store and access data using index | Retrieval and storage are a bit slow as the list has to traverse through each node to identify the correct one. |
| Removal and addition are slow because all the other items have to be shifted left or right accordingly. | Faster and more efficient for data manipulation like adding and removing elements from any part of the list |
| Removing an item while iterating through the list is slower because all the other elements have to be shuffled to fill the gaps in the list created by the removed elements | Removing an element while iterating is simple and only the next and previous nodes have to be adjusted. |
| You can specify the size of the initial ArrayList using ArrayList[int capacity] constructor. The size can still grow later, however, an initial amount can be set. ArrayList works even faster if the capacity specified is not exceeded. | LinkedList supports only no-argument constructor LinkedList[] |
| No provision for getting the methods of Queue or Deque. | Implements Deque, that provides descendingIterator[] that returns iterator having list value in reverse sequence. Same way methods like peek[], poll[] and offer[] [and its variants] are available so that the list function as a queue. |
| ArrayList cannot be used as a Stack. | As Deque also supports the methods push[], peek[] and pop[], LinkedList can be used as a Stack. |
Conclusion
While there is no right or wrong answer to this question, it certainly depends on your requirements. If you are not going to modify the list too much once it is created, ArrayList is a better choice. If there is a lot of manipulation involved, LinkedList is faster. There are many other features that LinkedList has because it implements a Deque interface, which can be an added advantage. Both the data structures follow the same principle in other languages like C or C++. Learn more about data structures here.
People are also reading: