Data Structures and Algorithms and Java

Difference Between ArrayList and LinkedList

Posted in Data Structures and Algorithms, Java
Difference Between ArrayList and LinkedList

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

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

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:

C Data Types

Difference between Structure and Union

Float vs Double

Top Data Structure Interview Questions & Answers

What is Python Arrays?

Python Data Structure

Quick Sort in C

Binary Search in C

Merge Sort in C

Bubble Sort in C

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
Marianne Newton
Marianne Newton

How ArrayList increase its size?

Lauren Reese
Lauren Reese

Where do we use linked list?

Brooke Fuller
Brooke Fuller

Is ArrayList better than array?

Alfredo Norman
Alfredo Norman

Is ArrayList synchronized?

Clarence Clark
Clarence Clark

Is ArrayList ordered Java?

Karen Pope
Karen Pope

Why do we need linked lists?

Eva Robbins
Eva Robbins

Why insertion is faster in linked list?

Priscilla Carr
Priscilla Carr

Is ArrayList thread safe?

Viola Fleming
Viola Fleming

Which is better ArrayList or HashMap?

Jimmy Barrett
Jimmy Barrett

Is linked list faster than ArrayList?