Data Structures and Algorithms and Java

Difference between ArrayList vs LinkedList

Posted in Data Structures and Algorithms, Java
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<String> 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,

namesList.add(2, "Joseph");

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”.

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 node’s 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(<index>) 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<String> lnkdlst = new LinkedList<String>();
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 don’t 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 - Mac

The 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 doesn’t 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.

Head-to-head comparison: Arraylist vs LinkedList

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:

Gaurav Gupta

Gaurav Gupta

Gaurav was one of the earliest software developers at SlideShare-LinkedIn which was followed by working for companies like Naukri.com, Educomp, Tata Institute of Fundamental Research etc. He is a techie not only by profession but also my passion and believes that going online is the future of education. View all posts by the Author

Leave a comment

Your email will not be published
Cancel