An Introduction of Java LinkedList with examples

Java LinkedList is a part of a Java collection framework. It implements the List interface in a doubly LinkedList manner. By inheriting AbstractSequentialList class, It implements all List operations.

LinkedList class also implements the Deque interface (which in turn extends the Queue interface) and provides double-ended queue behavior.

Structure of Java LinkedList

Like ArrayList, LinkedList linearly stores the elements, but not contiguous manner. Rather, it stores the data in form of the Node (or Element). Each Node points to the next and previous Linked List Node as follows.

Explanation

• Each element in LinkedList is known as a Node or Element. It is also described as a collection of Nodes.
• The node comprises data, previous and next node pointer.
• LinkedList maintains a pointer (called Head) to the first Node.
• Prev pointer stores the address of the previous Node and the Next pointer stores the next Node address.
• The last Node will always have null as the next Node pointer.

Features of Java LinkedList

Below are some important features of LinkedList that you need to keep a note of.

• Nodes in LinkedList are not required to be allocated contiguous manner.
• Memory allocation happens at runtime in Heap memory rather than at compile time.
  • No Random access is allowed. Only Sequential access is allowed.  Due to this, the Reading performance depends on how far the node is from the head (or End, whichever is closer).
• Addition and Deletion operations are faster than ArrayList if used with an iterator.
• Since LinkedList is ordered collections, It preserves the insertion order of the data.
• Duplicate and Null values are allowed.
• It provides an implementation of a double-ended queue.
• Since it provides Queue implementation, LinkedList can be used as Stack by using the push() and pop() method.
• Types of LinkedList are
  • Singly LinkedList
  • Doubly LinkedList
  • Circular Linked List
• As LinkedList inherits List behavior, we can use Iterator and ListIterator to traverse the LinkedList data. However, they are fail-fast, meaning after creating Iterator if LinkedList is modified then it throws ConcurrentModificationException.
• LinkedList is non–synchronized – meaning two threads can access it simultaneously. This leads to an exception in case if one thread is modifying it while the other is reading.
  • However, you can retrieve the synchronized version with Collections.synchronized as follows.

List linkedList = Collections.synchronizedList(new LinkedList(...));

ArrayList vs LinkedList in Java

Although ArrayList and LinkedList both implement the List interface, the way they arrange the data makes them different. This will surely impact the decision of choosing the one. Below are a few aspects of comparing ArrayList vs LinkedList

Data Structure

• The ArrayList internally uses an Array to store the data. Whereas, LinkedList uses a doubly linked list mechanism to store the data.
• The ArrayList only implements a List interface. On the other hand, LinkedList implements both the List and Queue interface. So apart from List, you will see a Queue-like behavior in LinkedList.

Memory arrangement and consumption

• Since ArrayList is backed by an Array, it has to store the elements in a contiguous memory location. LinkedList on the other hand stores the elements in the Node structure. Since the Nodes are linked using pointers, they are not required to be in a contiguous memory location.
• An ArrayList requires comparatively less memory to store the element. In LinkedList, a node contains pointers to another node (along with data). Due to this, it consumes more memory to store equal data than ArrayList.
• However, ArrayList consumes as much memory as it’s allocated for the capacity (remember capacity is increased when size is reached to threshold) regardless of actual data added to it or not.

Performance

The data storing mechanism of ArrayList vs LinkedList make them the best fit for specific operations while not recommended for others. To understand how it impacts the performance, let’s understand the internal mechanism.

ArrayList

• An ArrayList holds the data into the underlying Array with default size (10 after Java 8 ) while initializing. When it reaches its threshold (75% full of its capacity), it creates a new array with 1.5 times the size and copies elements from the old Array to the new Array.
• Though this brings great flexibility of dynamically growing the list, it comes with the cost of space and time consumption every time it hits the threshold. Due to this, after certain volumes of data, Write operations become slow.
• In the case of the Delete operation, it has to re-index everything. Due to this ArrayList is also not preferable for frequent Delete operation.
• However, retrieval is index-based due to contiguous memory storage and gives consistent random access (index-based) performance regardless of its size.
• So you should avoid using ArrayList to store huge data which continuously keeps added.
• It’s the best choice for heavy Read operations with good random access performance and time complexity O(1) – grab any element with constant timing.

Side Notes

• The add (int index, E element) method gives a performance with time-complexity O(n) (with n/2 steps on average).
• Similarly, the remove( E element) method also gives a performance with time-complexity O(n) (with n/2 steps on average).
• On their counterpart methods with iterator – Iterator.remove() and ListIterator.add() gives a performance with time-complexity O(n) (with n/2 steps on average).

LinkedList

• LinkedList stored the data in a Node structure and it has the pointer of the next and previous Node. This model gives flexibility to stores the Nodes anywhere in the heap memory. They are not required to be in a contiguous memory location.
• The Addition and Deletion of Nodes are efficient as it’s just a matter of swapping the pointers. Remember that, to take this benefit, you need to use an iterator. There is no need of resizing an array or updating the index. The memory allocation would be absolutely dynamic.
• So LinkedList can be used for relatively high Add / Delete operations with an iterator.
• However, the downside is, the Read would be sequential. Meaning, if you wanted to reach to 1000th element, you need to start sequentially from the 1st element (or last element) and traverse through all the elements till you reach to 1000th. No random access is supported.
• So LinkedList must be avoided for heavy Read operation as it gives O(n) performance, meaning the Read response depends on the number of Nodes in LinkedList.

Side Notes

• Though Java LinkedList doesn’t great for retrieving the elements, we can get the first or last element relatively faster with the help of getFirst() and getLast() methods respectively. Time complexity is O(1) in this case.
• Adding an element to a specific position with method – add ( int index, E element ) will still require traversing up to that index.  This gives O(n) (with n/4 steps on average) performance. Adding elements at the first or last index, however, is faster and gives good performance with time complexity O(1).
• This is also applicable to the remove ( int index ) method. It gives O(n) (with n/4 steps on average) normally but O(1) for the first and last position.
• LinkedList is efficient in adding or removing the elements. But searching for a position is time-consuming as it requires traversing a linked list from the beginning (or end whichever is closer).

Special Case

• If you are sequentially accessing Java LinkedList with the iterator, it takes constants time for adding or deleting the element. In short, this happens only while using iterator with sequential read. Moreover, you can traverse the list either in the forwarding or backward direction.
• Adding or deleting on a particular index will take proposal time to the size of the list – O(n) complexity.
• For LinkedList, Javadoc says – all the index-based operations will traverse the list from either beginning or end, whichever is closer. That’s why it gives O(n) – n/4 steps – half the steps than the ArrayList.
• For non-index-based operations, however, the time complexity is O(n) with n/2 steps.
• Moreover, You can gain true benefits of LinkedList by re-using the existing iterator to insert or remove the element.

Usage

Let’s quickly see some commonly used LinkedList methods as follows.

Methods and Time complexity

Just remember – to gain the benefits of insertion and deletion in LinkedList, you need to use an iterator.

Method execution

Let’s quickly see some of the common methods used as follows.

Creation

// with default constructor
 List<String> defaultLinkedList = new LinkedList<>();

// from existing collection
 List<String> fromExistingLinkedList = new LinkedList<>(defaultLinkedList);


// with reference type as Queue
 Queue<String> withQueueLinkedList = new LinkedList<>();


// with reference type as Deque
 Deque<String> withDequeLinkedList = new LinkedList<>();

• Just like ArrayList, LinkedList in Java can be created with the default constructor and from other collections.
• LinkedList implements the List and Deque (which extends Queue) interface. So reference type can be either List, Queue, Deque, or LinkedList itself.
• You can access only those methods which are defined in a reference type. For example, if the reference is of type List, you can’t access the Queue-specific methods on LinkedList.

Insertion

LinkedList<String> names = new LinkedList<>();

// adding without index
names.add("Peter");
names.add("James");
names.add("Harry");
names.add("Kiran");

System.out.println("Linked List :: "+names);

// adding to first index
names.addFirst("Nilang");

System.out.println("After adding to first element :: "+names);

// adding to last index
names.addLast("Komal");

System.out.println("After adding to last element :: "+names);

names.add(3, "Bhakti");

names.add(4, "Harmi");

System.out.println("Adding to specific index :: "+names);

The output is as follows.

Linked List :: [Peter, James, Harry, Kiran]
After adding to first element :: [Nilang, Peter, James, Harry, Kiran]
After adding to last element :: [Nilang, Peter, James, Harry, Kiran, Komal]
Adding to specific index :: [Nilang, Peter, James, Bhakti, Harmi, Harry, Kiran, Komal]

• The add(Object o) method will add the element at the last. Same as addLast(Object o) method.
• The addFirst(Object o) method will change the head of the LinkedList.
• The addLast(Object o) method will add the element at the last. Same as add(Object o) method.
• The add(int index, Object o) will add the element to a specific index.

Deletion

LinkedList<String> names = new LinkedList<>();

names.add("Peter");
names.add("James");
names.add("Harry");
names.add("Kiran");
names.addFirst("Nilang");
names.addLast("Komal");
names.add(3, "Bhakti");
names.add(4, "Harmi");
names.add("Harry");
names.add("Harmi");
names.add("Nikhil");
names.add("Krista");

System.out.println("Original Linked List                      :: "+names);

names.remove();
System.out.println("After removing default (first) element    :: "+names);

names.remove(2);
System.out.println("After removing from index 2               :: "+names);

names.remove("Kiran");
System.out.println("After removing specific object - 'Kiran'  :: "+names);

names.removeFirst();
System.out.println("After removing from first position        :: "+names);

names.removeLast();
System.out.println("After removing from last position         :: "+names);

names.removeFirstOccurrence("Harry");
System.out.println("After removing first occurance of 'Harry' :: "+names);

names.removeLastOccurrence("Harmi");
System.out.println("After removing last occurance of 'Harmi'  :: "+names);

The output is as follows.

Original Linked List                      :: [Nilang, Peter, James, Bhakti, Harmi, Harry, Kiran, Komal, Harry, Harmi, Nikhil, Krista]
After removing default (first) element    :: [Peter, James, Bhakti, Harmi, Harry, Kiran, Komal, Harry, Harmi, Nikhil, Krista]
After removing from index 2               :: [Peter, James, Harmi, Harry, Kiran, Komal, Harry, Harmi, Nikhil, Krista]
After removing specific object - 'Kiran'  :: [Peter, James, Harmi, Harry, Komal, Harry, Harmi, Nikhil, Krista]
After removing from first position        :: [James, Harmi, Harry, Komal, Harry, Harmi, Nikhil, Krista]
After removing from last position         :: [James, Harmi, Harry, Komal, Harry, Harmi, Nikhil]
After removing first occurance of 'Harry' :: [James, Harmi, Komal, Harry, Harmi, Nikhil]
After removing last occurance of 'Harmi'  :: [James, Harmi, Komal, Harry, Nikhil]

• The remove() will remove the first element. It’s the same as removeFirst().
• The remove(int index) will remove from a specific position.
• The remove(Object o) will remove the first occurrence. It’s the same as removeFirstOccurrence() method.
• The removeFirst() and removeSecond() methods remove first and last elements respectively.
• Special methods, removeFirstOccurrence(Object o) and removeLastOccurrence(Object o) remove the first and last occurrence from the list.

Iterating LinkedList

Since Java LinkedList is part of the collection framework, we can use Iterator to traverse its elements. Let’s see how to manipulate LinkedList with Iterator as follows.

    LinkedList<String> names = new LinkedList<>();

    names.add("Peter");
    names.add("James");
    names.add("Harry");
    names.add("Kiran");
    names.add("Nikhil");
    names.add("Krista");
    
    
    System.out.println(" Original List                      :: "+names);
    
    ListIterator<String> listIterator = names.listIterator();
    
    System.out.print(" Iterating in forward direction     :: [");
    
// 1. Iterating in Forward direction 
    while(listIterator.hasNext()) {
        if(listIterator.nextIndex() == names.size()-1) {
            System.out.print(listIterator.next()+ "]");
        }else {
            System.out.print(listIterator.next()+ ", ");
        }
    }
    
    System.out.println();
    
    System.out.print(" Iterating in backward direction    :: [");
    
// 2. Iterating in Reverse direction
    while(listIterator.hasPrevious()) {
        if(listIterator.previousIndex() == 0) {
            System.out.print(listIterator.previous()+ "]");
        }else {
            System.out.print(listIterator.previous()+ ", ");
        }
    }
    
    System.out.println();
    
// 3. Updating existing record while Iterating
    listIterator.next();
    listIterator.set("Sachin");
    
    System.out.println(" Updating record at first position  :: "+names);

    //Stepping back
    listIterator.previous();
    
// 4. Adding new record after position 2 - James
    listIterator.next();
    listIterator.next();
    listIterator.add("Virat");
    
    System.out.println(" Adding new record after James      :: "+names);
    
// 5. Removing record at position 4 - Harry
    listIterator.next();
    listIterator.remove();
    
    System.out.println(" Removing record - Harry            :: "+names);

The output is as follows.

Original List                      :: [Peter, James, Harry, Kiran, Nikhil, Krista]
Iterating in forward direction     :: [Peter, James, Harry, Kiran, Nikhil, Krista]
Iterating in backward direction    :: [Krista, Nikhil, Kiran, Harry, James, Peter]
Updating record at first position  :: [Sachin, James, Harry, Kiran, Nikhil, Krista]
Adding new record after James      :: [Sachin, James, Virat, Harry, Kiran, Nikhil, Krista]
Removing record - Harry            :: [Sachin, James, Virat, Kiran, Nikhil, Krista]

Quick observations

• We have used ListIterator which is only available for the collection of type List. It has additional methods over the Iterator.
• We can use ListIterator to traverse the LinkedList either in the forwarding or backward direction.
• Adding, updating, or removing the existing record is quite possible with ListIterator.
• While using ListIterator, LinkedList provides the best performance for adding, updating, or removing existing records. It’s because we don’t have to traverse to the index or the element explicitly. Meaning ListIterator.remove() is more efficient than LinkedList.remove(Object o). The same is applicable for adding and updating methods.

Sorting a LinkedList

Let’s see how we can sort the LinkedList with various methods.

LinkedList<String> firstNamesList = new LinkedList<>();

    firstNamesList.add("Peter");
    firstNamesList.add("James");
    firstNamesList.add("Jay");
    firstNamesList.add("Yuan");
    firstNamesList.add("Jo");
    firstNamesList.add("Nilang");
    
    System.out.println(" Original List                                   :: "+firstNamesList);
    
// 1. Sorting by Collection.sort()
    Collections.sort(firstNamesList);
    
    System.out.println(" Sorting in natural order with Collection.sort   :: "+firstNamesList);
    
    
    LinkedList<String> secondNamesList = new LinkedList<>();

    secondNamesList.add("Peter");
    secondNamesList.add("James");
    secondNamesList.add("Jay");
    secondNamesList.add("Yuan");
    secondNamesList.add("Jo");
    secondNamesList.add("Nilang");
    
// 2. Sorting by list.sort()
    secondNamesList.sort(null);
    
    System.out.println(" Sorting in natural order with list.sort         :: "+secondNamesList);
    
    LinkedList<String> thirdNamesList = new LinkedList<>();

    thirdNamesList.add("Peter");
    thirdNamesList.add("James");
    thirdNamesList.add("Jay");
    thirdNamesList.add("Yuan");
    thirdNamesList.add("Jo");
    thirdNamesList.add("Nilang");
    
// 3. Sorting in reverse natural sorting order 		
    thirdNamesList.sort(Comparator.reverseOrder());
    
    System.out.println(" Sorting in reverse natural order                :: "+thirdNamesList);
    
    
    LinkedList<String> fourthNamesList = new LinkedList<>();

    fourthNamesList.add("Peter");
    fourthNamesList.add("James");
    fourthNamesList.add("Jay");
    fourthNamesList.add("Yuan");
    fourthNamesList.add("Jo");
    fourthNamesList.add("Nilang");
    
// 4. Custom sorting - by length of name using Collections.sort()
    Collections.sort(fourthNamesList, 
            ( v1, v2) -> v1.length() - v2.length() );

The output is as follows.

Original List                                   :: [Peter, James, Jay, Yuan, Jo, Nilang]
Sorting in natural order with Collection.sort   :: [James, Jay, Jo, Nilang, Peter, Yuan]
Sorting in natural order with list.sort         :: [James, Jay, Jo, Nilang, Peter, Yuan]
Sorting in reverse natural order                :: [Yuan, Peter, Nilang, Jo, Jay, James]
Custom Sorting with comparator                  :: [Jo, Jay, Yuan, Peter, James, Nilang]

Quick observations.

• Sorting by Collections.sort()
  • This is the most straightforward way of sorting a Linked List.
  • The Collecions is a utility class (in java.util package) that provides various helpful methods. The Collections.sort() method takes List as an argument and sorts its elements.
  • Since we are using List of String, we don’t need a comparator explicitly. In the case of a custom class, you need to provide a Comparator.
  • For sorting of type List, the Collections class internally uses list.sort().
• Sorting by list.sort()
  • Starting from Java 8, the List interface provides a default method called sort(). This method is called within Collections.sort() method.
  • Sorting can be customized by passing the Comparator to list.sort() method. In the case of passing null, it sorts in the natural order.
• Reverse sorting
  • Reversing a Linked list is quite possible. It can be done by passing Comparator.reverseOrder() to either either Collections.sort() or list.sort() method.
• Custom sorting
  • Custom sorting can be possible with custom Comparator implementation.
  • It is second argument of Collections.sort() method. In case of list.sort(), you can directly pass the comparator.
  • We have used Java 8 lambda expression to provide Comparator implementation in functional style.
  • The comparator logic will sort the names based on the length of the name in ascending order. You can write any custom sorting logic as per your requirement.

Queue specific methods

LinkedList provides many methods. Most of them are familiar to users who already using List. It also implements Deque (which extends Queue) interface. So it provides various queue specific methods like addFirst(), addLast(), getFirst(), getLast(), removeFirst() and removeLast(). Additionally, there are a few more as follows.

• push() – adding element on top (first) position. Stack like implementation.
• peek() – Returns the first element (Head element) from list. No deletion happens.
• poll() – Returns and remove first element. Stack like implementation.
• pop() – Same as poll() but returns NoSuchElementException() if list is empty. Whereas poll() just return null if list is empty.
• offer() – add element at the end of list. Similar to add().

For a complete method list, you can check the official documentation here.

Summing up

In this article, we familiarize ourselves with Java LinkedList implementation in Java. We also understand how it’s different from the most commonly used collection – ArrayList.

• In most of the places, we are using ArrayList. However, in certain cases, LinkedList is the best fit.
• In the collection, if modification is too frequent then you should use LinkedList.
• You can utilize the existing Iterator (ListIterator) to get the best performance of adding, deleting, or updating existing records.
• Always consider the time complexity of the operation while choosing the right collection type for your need.
• Apart from List, LinkedList provides queue-like behavior. So it can be used as a stack implementation.
• In this article, we took a String as a generic class. As an exercise, you can try with more complex or custom types.