LinkedList

LinkedList stores a group of elements and it maintains order of insertion. For LinkedList we don’t specify the size, as we add elements, the size gets bigger automatically. Also LinkedList allows duplicates.

This might sound similar to ArrayList. But the internal data structure is different for both of them.  ArrayList maintains an array inside it. All the elements are stored at a particular index of that array. But in the case of LinkedList, elements are stored containers called Nodes. That node not only contains the element, it also contains the link to the next and previous nodes. When we add an element, that element is placed into a new node.

Let’s understand the LinkedList with an analogy. Consider a cargo train. It has an engine car at the beginning and many other cars to carry different types of commodities like coal, sugar, fertilizer etc. Individual cars are attached to each other in a specific order. This is similar to a LinkedList. Individual cars can be considered as Nodes.

LinkedList

The LinkedList is a collection that can contain objects of the same type, just like the ArrayList. Please remember –

1. LinkedList can only store Objects.
2. Duplicates are allowed in LinkedList.
3. LinkedList preserves the order of the elements in which they are inserted.
4. Methods of LinkedList are not synchronized. So they are not thread-safe.

How to create a LinkedList?

How does LinkedList internally work?

As we said earlier, LinkedList stores elements inside containers called Nodes. Node not only contains the element, it also contains the link to the next and previous nodes. In terms of code, Node is nested class of LinkedList class. Node class contains three attributes –

• item – It holds the actual element.
• next – It holds the reference of the next node.
• prev – It holds the reference of the previous node.

class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Here E is the type of element that LinkedList is going to hold.

Below are few important instance variables that LinkedList class have –

The add() Method

When we add the very first element to a LinkedList, an instance of Node class is created. As this is the single element, no next or previous link exists. So –

1. Value of the Node class instance variable item would be the value that we have added to the LinkedList.
2. Value of the Node class instance variable next would be null, as there is no next node.
3. Value of the Node class instance variable prev would be null, as there is no previous node.
4. Value of the LinkedList instance variable size becomes 1.
5. LinkedList instance variable first and last will refer to the very first node that has been created.

Now when we add the second element, again an instance of  Node class is created.

1. Value of the Node class instance variable item would be the value that we are trying to add to the linked list.
2. The instance variable prev will refer to Node 1. 
3. The instance variable next would be null as there is nothing next to it.
4. Also, the value of next of Node 1 will be updated with Node 2.
5. Value of the LinkedList instance variable size becomes 2.
6. LinkedList instance variable first will refer to Node 1 and last will refer to Node 2.

If we add more elements, the same thing happens as in the case of the second node.

The remove() method

When we try to remove an element, the LinkedList iterates over the nodes starting from the first node to get the node and compare the value of the Node class instance variable item with the value we have provided in remove() method.

Once the node is identified, get the instance variable value next (next node) and prev (previous node) of the node to be removed and update the references of those nodes. In our example, following changes will happen –

There are two special cases –

1. If prev is null, then the node to be removed must be the first node. So mark the next node as the first node of the LinkedList class.
2. If next is null, then the node to be removed must be the last node. So mark the previous node as the last node of the LinkedList class.

Also, subtract the size of LinkedList by 1.

Create a LinkedList and add/remove elements

public class JavaDemo {
    public static void main(String[] args) {
        LinkedList<String> friends = new LinkedList<String>();
        friends.add("Bob");
        friends.add("Sarah");
        friends.add("Michael");
        friends.add("Matt");
        friends.add(1, "Lisa");
        friends.remove("Sarah");
        System.out.println(friends);
    }
}

Output: [Bob, Lisa, Michael, Matt]

How to iterate over a LinkedList?

There are three frequently used  approaches to traverse through the elements of a LinkedList. 

1. Using for loops
2. Using for-each loop
3. Using Iterator

public class JavaDemo {
    public static void main(String[] args) {
        LinkedList<String> friends = new LinkedList<String>();
        friends.add("Bob");
        friends.add("Sarah");
        friends.add("Michael");
        friends.add("Matt");

        // 1. Using for loop
        for (int i = 0; i < friends.size(); i++) {
            System.out.println(friends.get(i));
        }

        // 2. Using for-each loop
        for (String friend : friends) {
            System.out.println(friend);
        }

        // 3. Using Iterator
        Iterator<String> iterator = friends.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

All the above three approach will give same output:

Bob
Sarah
Michael
Matt

Fail-fast Iterator

Let’s execute below code:

LinkedList<String> friends = new LinkedList<String>();
friends.add("Bob");
friends.add("Sarah");
friends.add("Michael");
friends.add("Matt");

for (String friend : friends) {
	friends.add("Lisa");
	System.out.println(friend);
}

Output:

Bob
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.LinkedList$ListItr.checkForComodification(Unknown Source)
at java.util.LinkedList$ListItr.next(Unknown Source)

But why the exception?

All the implementations of Iterator in Collection classes including LinkedList are fail-fast except the concurrent collection classes like ConcurrentHashMap and CopyOnWriteArrayList.

Fail-fast Iterators fail as soon as they realize that the structure of the Collection has been modified by adding or removing elements since iteration has started.

During the first iteration we have added a new element and printed the first element from the original list. So, Bob is printed. Then during the second iteration the iterator realizes that the original collection is modified and throws the exception.

Other frequently used methods

Differences between LinkedList and ArrayList

We have already discussed, internal data structure is different for both of them. Now, let’s try to understand the difference in performance in different situations.

Get an element

ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. But, LinkedList has to traverse the list from the beginning to get to the n-th element. So the get() method is slower in the case of LinkedList. Only exception is, if you try to get the very first element (index: 0), performance will be the same.

Remove an element

Let’s assume, we are removing an element from the middle of the list. ArrayList has to move the elements having higher index to occupy the free slot. But LinkedList just has to manipulate a couple of references of previous and next nodes. So the remove operation is faster in LinkedList. Only exception is, if we remove from the last element, performance will be similar as no element shifting is required for ArrayyList.

Insert an element

When we add an element without specifying the index, ArrayList first checks if the internal array has a slot left. If yes, just add that element next to the last element. Otherwise, create a new array with a bigger size, then copy the elements from the old array to this bigger array and then add the element next to the last element. But in the case of a LinkedList, it first creates a Node object and adds it next to the last Node. Also, there are few reference manipulations involved.

So, if the ArrayList has a slot left, add operation will be faster in ArrayList than LinkedList. Otherwise, performance of add operation will be slower in ArrayList as multiple extra operations (e.g. create new array with bigger size, copy elements etc.) are involved.

If we try to add an element in the middle, LinkedList just adds the new node in that position and updates a few references of previous and next node. But in the case of ArrayList, all the element having higher index has to be shifted one place right to create the empty slot and then adds the element to that empty slot. So performance will be faster in LinkedList. 

That’s it for now. Hope you have enjoyed this tutorial. If you have any doubt, please ask in the comment section. I will try to answer that as soon as possible. Till then, bye bye.