@project_java

Linked Lists in Java

Previously, we had seen what is a List, why we need it and how to implement one using arrays in Java. We had implemented a dynamic list in Java as well. To bring you back on track for this article, a List is a data structure, sequentially storing the elements and growing/shrinking the size dynamically as and when its needed.

Why should we move on from a conventional ArrayList?

Talking about the insertion and deletion operations inside of an ArrayList, it is comparatively slower than other operations. Since it can dynamically shrink in size, deletion of an element at a position other than the first and last index would mean the shifting of elements after it. This means that if there are 8 elements in an arraylist and I delete the 2nd element, i would need to shift the remaining 6 elements to the right in order to free the space and allow the list to shrink in size. This is the same for insertion operation. Hence we need a data structure which allows easy insertion and deletion of elements into the collection.

Moreover, ArrayList is an ordered collection, which means that when it is created, it allocates some contiguous space on the memory. Imagine that you’re running short of memory and you have isolated memory spaces which are available and not contiguous. In these situations, you need to make use of such a data structure that can effectively span throughout the memory to store data wherever it finds an isolated space.

LinkedList

A LinkedList is a type of List which makes use of references to memory locations in order to store data efficiently by harnessing the leftover memory spaces. It makes sure that no redundant memory allocation takes place by making use of pointers internally.

It makes use of another very fundamental object called Node to implement its unique structure. Let’s now understand what a Node is.

Node

A Node is a basic building block which comprises the address of another node and the data. It can be said that a collection of Node in which every successor node is linked with its previous node via references(pointer) makes a LinkedList.

It is not just used for linked lists but many other data structures like trees and graphs. Its implementation in the linked lists depends upon the type of LinkedList. For example, in case of a singly linked list, a Node contains the address of successor node and the data whereas in case of a doubly linked list, it also contains address of the predecessor node.

Singly Linked List Node

Doubly Linked List Node

This is how a Node would look like:

import lombok.Getter;
import lombok.Setter;

@Getter
@Setter
public class Node {
    private int val;
    private Node next, previous;
    public Node(int val) {
        this.val = val;
        this.next = this.previous = null;
    }
}

If you’re wondering what @Getter and @Setter is, then these are annotations of the Lombok project. Using project Lombok, we can reduce the boilerplate code as it generates the getter and setter methods for the data members of the class during compile time.

Singly Linked List

A Singly Linked List is the basic type of LinkedList in which each node has the address of the successor node. It is called “singly” as its nodes stores the reference to only their successor node. This data structure allows efficient insertion and deletion of elements at the beginning and end of list. However accessing elements from the middle of the list is not easy. It has to be traversed in order to access a particular element of a list. It has inefficient list reversal and searching operations.

This kind of a list have a reference wherefrom the list can be accessed. This reference stores the address of the head node of the linked-list. This head node serves as the starting point of the linkedlist from where all the other elements can be accessed. Similarly, there is a tail node of the linkedlist wherefrom navigation isn’t possible as the address portion of the tail node stores null. This can easily be understood with an example of a train with multiple train cars interconnected to each other. Every train car has its own seating capacity, and a link that connects it to the previous car and the succeeding car. In this representation, the train engine is the head of linked list and the caboose is the tail of linked list.

Since a LinkedList is a type of List, it must implement all the methods of the List interface that we defined in the previous post. Let us now construct our LinkedList class around the List interface.

We will override all the methods part-by-part to better understand the working behind it.

Class Structure

public class LinkedList<T> implements List<T> {
  private Node<T> head;
  private int size;

  public LinkedList<T>() {
	this.size = 0;
  }
}

Yes, that’s it. We need a head node through which we could access the start of the singly linked list in order to perform operations on it.

Note: We will be using a temporary Node<T> currHead on which we will perform several operations. We do this to ensure that the actual head isnt affected by the operations we perform. As you might think, we would copy the address of the head into currHead to continue with our further operations and methods.

Adding Element to the End of List.

This sounds easy to do. But the interesting part is the edge-cases. Let’s discuss what can the edge-cases of adding an element could be.

• If head is null - This means that the element we are going to add to the list is going to be the first element to the list. Hence, it has to be the head of the list.
• If head is not null - This means that element needs to be added as the last element of the non empty list. Hence we need to iterate till the end node of the list and then set the next of the tail node to the new node that we’ve created with the value of element.

This sounds good, let’s actually implement in code.

@Override
public boolean add(T element) {
    Node<T> newNode = new Node<>(element);
    if (this.head == null) {
        this.head = newNode;
    } else {
        Node<T> currHead = this.head;
        while (currHead.getNext() != null) {
            currHead = currHead.getNext();
        }
        currHead.setNext(newNode);
    }
    this.size++;
    return true;
}

Everything remains the same, except the fact that we increment the size of the list as well. The loop iterates until we reach the tail of the list. It is then that we set the next node after the tail to the newly made node newNode.

Adding multiple elements at once.

We have known about for-each loop in Java. Accepting the data values at once in the form of a T[] array as an argument of the addAll method would be helpful in many ways. Here’s how you will do it.

@Override
public boolean addAll(T[] elements) {
    for(T element : elements){
        this.add(element);
    }
    return true;
}

Since we are adding elements to the end of the linked list one by one, we can choose to add element to the list by invoking the above built add(T element) method.

Fetching the value of Node via its index.

Let’s analyze the edge-cases for fetching the element at a given index.

• If index is out of range: This is simple. We will return null.
• If index is zero(0) : We will return the value of the head Node.
• If index is anything other than the above mentioned: We will iterate till the index is reached and then return the value of the currHead node.

Here’s how we would implement it.

@Override
public T get(int index) {
    if(index < 0 || index > this.size+1) {
       return null;
    } else {
        if(index == 0)
            return this.head.getVal();
        Node<T> currHead = this.head;
        for(int i=0; i<=index; i++) {
            currHead = currHead.getNext();
        }
        return currHead.getVal();
    }
}

Removing the element at a given index.

Now that we know how to add elements and fetch a value at a given index, we need to learn how we could remove an element present at a given index.

• If index is out of range - Well, we dont need to do anything but return null as no Node is present at that index.
• If index is 0 - We have to set the next node of the head node to the next node.
• If index is some value other than the above ones - In this case, we need to iterate from 0 to index-1 to get the node before the node we want to remove. Now, we store the value of the next node as we will lose that value once we remove the node. Furthermore, we need to update the currHead ’s next node to the node successor to the removed node.

Let’s now implement the same logic in the code.

@Override
public T remove(int index) {
    if (index<0 || index>=this.size) {
        return null;
    }
    
    T removedValue;
    
    if (index == 0) {
        removedValue = this.head.getVal();
        this.head = this.head.getNext();
    } else {
        Node<T> currHead = this.head;
        for (int i=0; i<index-1;i++) {
            currHead = currHead.getNext();
        }
        removedValue = currHead.getNext().getVal();
        currHead.setNext(currHead.getNext().getNext());
    }

    this.size--;
    return removedValue;
}

Sorting the List in Ascending Order

This is the most important part of LinkedList. It can be really difficult to imagine of an algorithm to do this task when you just have one access point to the list. We would consider using the best of sorting algorithms out there based on Divide and Conquer technique, namely Merge Sort.

Merge sort is a sorting technique based on dividing the array of elements into several unielement arrays(which are obviously sorted) and then merge them together to get one sorted array.

Now, with the help of a pseudo code, we will see how we implement this. Since the pseudo code is divided into several methods, we would go step by step in each method.

mergeSort(head) {
  if head is null or head.next is null
    return head
	
  //Step 1 : Divide the list into two halves from the middle.
  middle = findMiddleNode(head)
  leftHalf = head
  rightHalf = middle.next
  middle.next = null

  //Step 2 : Recursively sort each half
  leftSorted = mergeSort(leftHalf)	
  rightSorted = mergeSort(rightHalf)
  //Step 3 : Merge the two sorted halves and return the sorted list.
  sortedList = merge(leftSorted, rightSorted)
  return sortedList
}

Step 1 : Divide

We break the linked list from the middle in two halves and set the leftHalf as head and the rightHalf as the next node after the middle node. Now in order to actually separate these two linked lists, we need to break the link between them which is joined via middle.next

Step 2 : Sort

Breaking every element till it reaches the base condition wherefrom the sorted sublists would arise. We conquer the problem statement by having leftSorted and rightSorted linked lists, ready to be merged.

Step 3 : Merge

This final step is to merge the two sorted halves of the linked list. This method would combine the two lists while maintaining the sorted order, hence creating a single merged and sorted linked list.

findMiddleNode(head) {
  slowNode = fastNode = head
	
  while fastNode.next is not null and fastNode.next.next is not null
  	slowNode = slowNode.next
  	fastNode = fastNode.next.next
  return slowNode
}

Here, we use two pointer approach with the pointers namely slowNode and fastNode, initially pointing to the head of linked list. In the loop, the fastNode moves two steps at a time while slowNode moves one step at a time.

Now, the loop continues until either of the conditions meet: -

• fastNode reaches end of linked list but fastNode.next is null - In this case, the lst has odd number of nodes and slowNode will point exactly to the middle node.
• fastNode reaches the end of list but fastNode.next.next is null - In this case, the list has even number of nodes and the slowNode will be the first middle node of the two middle nodes.

Once the loop exits, we have our middle node reference stored in slowNode. And hence we return the middle node.

merge(leftSorted, rightSorted):
    create a tempNode with value -1
    set currNode to tempNode

    while leftSorted is not null and rightSorted is not null:
        if leftSorted.value < rightSorted.value:
            set currNode.next to leftSorted
            leftSorted = leftSorted.next
        else:
            set currNode.next to rightSorted
            rightSorted = rightSorted.next
        currNode = currNode.next  // Move to the next node

    // Attach any remaining elements
    if leftSorted is not null:
        set currNode.next to leftSorted
    if rightSorted is not null:
        set currNode.next to rightSorted

    return tempNode.next

Here in this merge method, we create a temporary node namely tempNode which will help us start building the merged list. We then create a node with the name currNode and initialize it with the reference to tempNode.

The loop compares the values of the nodes in the leftSorted and rightSorted lists and merge them into the currNode list in sorted order.

During each iteration, if the value of the node in leftSorted is less than the value of node in the rightSorted, we set the currNode.next to the leftSorted and move leftSorted one step forward denoting that we have sorted that node. But let’s suppose if the value of rightSorted is less than or equal to the value of node in the leftSorted, we set the currNode.next to the node from rightSorted linked list and move rightSorted one step forward indicating that the node has been sorted.

Well, even after this, there are chances that there are still some elements in either of the two linked lists. In that case we need to append the remaining nodes to the end of currNode list.

Finally, we return the merged list by skipping the tempNode and returning the tempNode.next which is actually starting node of the merged and sorted linked list.

Conclusion

Linked lists have been very powerful data structure, capable of providing efficient solutions to a wide array of problems in computer. While linked lists may not be the best choice for every scenario, their ability to handle dynamic datasets with ease and optimize specific algorithms makes them a crucial tool in programmer’s toolkit.

This is it for this article, you have to implement the code of sorting a linked list in ascending order on your own using Java and the pseudo code that was mentioned in the article. Thank you!

If a person was named linked-list, he would never want to get married. Comment the reason below. ;)

Instagram: @project_java , Discord: Venkat.#3841