1. LinkedList vs ArrayList

In this example, we will learn about Java’s LinkedList Collection and will compare that with the ArrayList. We will study how each structure holds its merits & demerits in terms data structure change and data fetch.

The Java’s LinkedList Collection implements both List and Dequeue. In the past example, we saw an ArrayList which implements only the List interface. As LinkedList also implements the List, we can get same behaviour offered by ArrayList in LinkedList as well. In this example, we will see the List implementation over the LinkedList and compare its performance with ArrayList.

LinkedList is fast in data structure modification. This means, add and delete of the elements are faster when compared with ArrayList. Whereas the data retrieval is slow. We will look at the Dequeue in the next coming examples. Below is the List implementation (Same as ArrayList) functions which we are trying to learn here:

Method & Description

boolean add(E e) – Adds Element E to the Collection.

boolean remove(E e) – Removes an Element E from the Collection.

void clear() – Removes all the elements. Keeps the Collection Empty.

boolean isEmpty() – Tells collection is empty or not.

int size() – Returns number of elements in the Collection.

boolean contains(Object o) – Tells Object o is part of Collection or not

Iterator<E> iterator – Returns an iterator to iterate over Collection of Elements E

2. Memory Layout – LinkedList vs ArrayList

In ArrayList, the items are piled in continuous memory location. Have a look at the below picture which shows the memory layout for ArrayList:

Here, you can see three items in the ArrayList with index ending at 2. Java packs all the items in the ArrayList in consecutive memory slots. This means, when one item ends, other one starts in the immediate next memory slot. So, for ArrayList the memory layout is continuous. Now look at the memory layout for the LinkedList below:

Here in the above memory layout, we see three elements are placed at random memory location and they need not be next to each other. But LinkedList links these elements with next and previous links. Let us take Obj2, which is in the middle of the LinkedList. It involves 4 links in which two are outgoing and two are incoming. This middle item obj2 owns the outgoing links and incoming links are owned by some other items in the linked list.

In the outgoing link, one is the forward link to reach next item and other one is the reverse link to reach previous element. So, from element 2 we can go to its next element which is obj3 or reach previous element which is Obj2. Java LinkedList is Two-Way Traversal List.

3. ArrayList Data Read – Performance

The ArrayList performance is fast in data fetch and to learn it how, have a look at the below picture:

Now, let us say, we want to fetch the element Obj3. We pass the index location 2 to the ArrayList function to get the element. ArrayList will not travel its internal data structure visiting Obj1 and Obj2. Since it knows the index, and elements are in the continuous memory location, it calculates the offset and gets the element in a single go. It does not matter how many elements are there in the ArrayList, the ArrayList fetches the elements at a specific index just by calculating the offset. This way the Performance of the ArrayList is good for data fetch.

4.LinkedList Data Read – Performance

The data read based on an index has some performance overhead in the linked list. Let us see how? Have a look at the below picture:

Let us say there are 100 objects in the linked list, and the picture shows first three. We want to get element at index location 2. In Java LinkedList element are stored at random memory location and they are linked through next & previous references. Here, calculating the offset does not work as elements are not contiguous. So, Java Algo traverse the list from index location 0 and ends at the claimed index 2. It visits all the nodes in between. Here, the traverse is from 0->1->2. Finally, the element at index location 2 is returned to the user. Visiting these intermediate nodes is the performance overhead in LinkedList, especially when the List is huge.

Since java implements the LinkedList as 2-Way List, the direction of traverse is either from the start location or end location depending on the claimed location of the index. If the index is close to the end, then Java goes over the list in the reverse path for performance reason. Either way, since offset is not possible, it has to visit all the crossing nodes in the traverse direction.

5. Structure Manipulation – ArrayList

Adding or removing an item in the ArrayList is a costly action because of unbroken memory location. These two actions involve copying the objects (shifting) to maintain the packed adjacent memory location. Let us see this. Have a look at the below picture:

Here, we have an ArrayList with three elements: Obj1, Obj2 & Obj3. We want to add element Obj4 at index location 2 (i.e.) as the second element in the list. This means, in the pack of memory location, a slot is allocated towards the end and existing objects at index location 1 and 2 will move towards the right. This copy is a costly operation when you imagine there are millions of elements that need to be moved. After this copy action, the new element sits at index location 1. Below is the array after inserting the Obj4:

6. Structure Manipulation – LinkedList

The skeletal data manipulation (i.e.) adding and removing items in the linked is faster compared to ArrayList. Let us see how?

In the above picture, we can see a LinkedList with three items. Even though the memory for the items are in random locations, they are connected via reference links. Now, we want to add an element obj4 at index location 1.

In the past section, we saw the ArrayList made object copy from one location to other location to keep all items together for easy referencing by index. But the LinkedList only alters the forward & back links to keep the Obj4 as second item. In other words, the memory sites for Obj1, Obj2 and Obj3 are intact. LinkedList does structural change like adding and removing an item with no data copy like ArrayList. So, Java LinkedList is faster in adding & deleting the items as it involves shifting the links not memory locations. The below picture shows LinkedList after adding the element Obj4.

7. Code Reference

The example is same as ArrayList. The only difference is below:

Watch this example as video below:

• ArrayList – Java Collection
• Using Java Queue via LinkedList

Categories: Java

Tags: ArrayList, LinkedList, Performance

This site uses Akismet to reduce spam. Learn how your comment data is processed.