Singly linked lists are a fundamental data structure in computer science, offering dynamic flexibility and memory efficiency. In Java, understanding and mastering them is key to unlocking efficient algorithms and problem-solving skills. This blog aims to guide you from basic concepts to advanced techniques, transforming you from a linked list novice to a ninja!

Anatomy of a Singly Linked List

Each node in a singly linked list comprises two parts: data and a reference to the next node. This pointer-based structure enables dynamic growth and memory management. The first node is called the head, and the last node has a null reference as its next node.

In a singly linked list, each node points to the next node in the sequence, forming a linear chain. The last node typically points to a null reference, indicating the end of the list.

How to represent a Linked List in Java ?

A linked list is a fundamental data structure employed for the storage of a series of elements, objects, or nodes, characterized by the following attributes:

1. Sequential arrangement of nodes.
2. Each node comprises data along with a pointer to the subsequent node.
3. The initial node serves as the head node.
4. The final node contains data and points to null.

| data | next | ===> | data | next | ===> | data | next | ===> null

Visualizing Nodes: Unraveling the Building Blocks

In the intricate world of linked lists, nodes take center stage, acting as the fundamental units that store data and guide traversals. Let’s dissect the visual representation you provided:

Node Structure:

| data | next |===>

• data: This field holds the actual value, serving as the heart of the information a node carries. Its contents can vary depending on the application, from simple integers to complex objects.
• next: This crucial pointer acts as the bridge to the next node in the sequence. By following these references, we can navigate the entire linked list, one node at a time. The arrow -----> represents this connection, visually depicting the flow from one node to the next.

Linked List Illustration

head ====> |10|===>|8|===>|9|===>|11|===> null

• head: The special node marking the beginning of the linked list. Think of it as the entrance gate, providing the entry point for accessing the list’s elements.
• Nodes: Each rectangular box, labeled with |data|====>|next|, represents a node in the chain. The values inside the data field indicate the stored values (10, 8, 9, 11).
• null: This unique value, often denoted by null, signifies the end of the list. Just like reaching the end of a road, encountering null indicates there are no more nodes to follow.

public class SinglyLinkedList {

  private ListNode head; // head node to hold the list
  
  // It contains a static inner class ListNode
  private static class ListNode {
     private int data;
     private ListNode next;

     public ListNode(int data) {
          this.data = data;
          this.next = null;
     }
  }

  public static void main(String[] args) {
   
  }
}

This Java code defines a class named SinglyLinkedList with a private member variable head, which represents the starting node of the linked list. Inside this class, there is a static inner class named ListNode, which encapsulates the data and reference to the next node. The constructor of ListNode initializes the data and sets the next node reference to null.

The main method serves as the entry point, although it’s currently devoid of content. We will proceed to furnish it with creation code shortly.

How to create a singly linked list in java ?

head ---> 10 ---> 8 ---> 1 ---> 11 ---> null

Now, let’s see how we created it:

1. Initially, the head node points to null because the linked list is empty, i.e., head —> null.
2. Let’s create the first node with data 10, which also points to null, i.e., 10 —> null.
3. To hold nodes one by one, the head points to the node with 10. At this stage, the our list contains one node, i.e., head —> 10 —>.
4. Let’s create the second node with data 8 and next pointing to null, i.e., 8 —> null.
5. Connect the head node to the second node so that the list will contain 2 nodes, i.e., head –> 10 –> 8 –> null.
6. Create the third node with data 1 and next pointing to null, i.e., 1 –> null.
7. Here, we connect the third node to the second node so that the list contains 3 nodes, i.e., head –> 10 –> 8 –> 1 –> null.
8. Finally, create the fourth node with data 11 and next pointing to null, i.e., 11 –> null.
9. Connect this fourth node with the third node. Now, the linked list size is 4, i.e., head –> 10 –> 8 –> 1 –> 11 –> null.

Lets write code in above SinglyLinkedList empty main method.

// Let's create a linked list demonstrated in the comment below

// 10 --> 8 --> 1 --> 11 --> null
// 10 as head node of linked list

ListNode head = new ListNode(10);
ListNode second = new ListNode(8);
ListNode third = new ListNode(1);
ListNode fourth = new ListNode(11);

// Attach them together to form a list 

head.next = second;      // 10 --> 8
second.next = third;     // 10 --> 8 --> 1
third.next = fourth;     // 10 --> 8 --> 1 --> 11 --> null

This code snippet demonstrates the creation of a linked list with four nodes, where each node contains an integer value. The comments above describe the structure of the linked list being created, and the subsequent lines of code link the nodes together to form the desired sequence.

Final code look like:

public class SinglyLinkedList {

    private ListNode head; // head node to hold the list

    // It contains a static inner class ListNode
    private static class ListNode {
        private int data;
        private ListNode next;

        public ListNode(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public static void main(String[] args) {

        // 10 --> 8 --> 1 --> 11 --> null
        // 10 as head node of linked list

        ListNode head = new ListNode(10);
        ListNode second = new ListNode(8);
        ListNode third = new ListNode(1);
        ListNode fourth = new ListNode(11);

        // Attach them together to form a list 

        head.next = second; // 10 --> 8
        second.next = third; // 10 --> 8 --> 1
        third.next = fourth; // 10 --> 8 --> 1 --> 11 --> null

    }
}

How to print elements of Singly Linked List in java

As we know, to print all elements in a linked list, we need to traverse through all nodes in the linked list until the end of the linked list.

So,

head –> 10 –> 8 –> 1 –> 11 –> null

Algorithm & Execution

current = head;
while(current != null)
{
    Sop(current.data);
    current = current.next;
}

1. Let’s create a current node which initially points to null, i.e., current –> null. At this point, the output is null.
2. Now we will assign the head node of the linked list to this current node, i.e., current = head.
3. To traverse the list node by node until the end of the list, we will use a while loop which checks whether the current node is null. If it is null, that means we reached the end of the list.
4. So, for every iteration, we will print that particular node’s data and also shift the current node pointer to the next node so that we traverse to the next node.

Code

// Given a ListNode, prints all elements it hold 
public void display(ListNode head)
{
  if(head == null)
  {
    return;
  }

  ListNode current = head;
  
 // loop each element till end of the list 
 // last node points to null

  while(current != null)
  {
    System.out.println(current.data + " --> ");   // prints current element's data
    // move to next element
    current = current.next;
  }
  System.out.print(current);  // here current wil be null 
  
  
  

Run with -->

SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.display(head);


o/p : 10 --> 8 --> 1 --> 11 --> null

This code snippet defines a method display within the SinglyLinkedList class, responsible for printing all elements of the linked list starting from the provided head node. It iterates through the linked list nodes, printing each node’s data, and ends with printing “null” once the end of the list is reached. Finally, the method is invoked with a head node, displaying the elements of the linked list.

How to find the length of singly linked list in java?

Let’s determine the length of the linked list programmatically

Head –> 10 –> 8 –> 1 –> 11 –> null

Algorithm & Execution

current = head;
int count = 0;
while(current != null)
{
  count++;
  current = current.next;
}

1. We will create a temporary node called current, initially pointing to null.
2. The current node is set to point to the head of the linked list.
3. We create a count variable to keep track of the number of nodes present in the list, initialized as int count = 0.
4. Execute the while loop until the current node reaches the end of the list. We check if the current node equals null; if yes, it means we’ve reached the end. For each iteration, we increment the count variable by 1, and the current node pointer moves to the next node.

Code

// Given a ListNode head, find out the length of the linked list 
public int length(ListNode head) {
  if (head == null) {
    return 0;
  }

  // Create a count variable to hold the length
  int count = 0;

  // Loop through each element and increment the count until the list ends 
  ListNode current = head;
  whi le (current != null) {
    count++;
    // Move to the next node 
    current = current.next;
  }
  
  return count;
}

Here, code snippet defines a method length within the SinglyLinkedList class, which calculates the length of the linked list starting from the provided head node. It iterates through the linked list nodes, incrementing a count variable for each node encountered, until it reaches the end of the list. Finally, it returns the count representing the length of the linked list.

Singly Linked List Insertion Operation

One of the primary operations performed on singly linked lists is insertion, which involves adding new nodes at various positions within the list. Let’s explore their complexities, implementation techniques, and best practices.

How to inser node at the beginning of singly linked list in java

Inserting a new node at the beginning of a singly linked list is a straightforward operation. It involves creating a new node with the desired data value and adjusting the pointers to ensure proper linkage.

Head –> 10 –> 8 –> 1 –> 11 –> null

Algorithm & Execution

ListNode newNode = new ListNode(15);
newNode.next = head;
head = newNode;

1. The first step creates a new node with data 15 and next pointing to null, i.e., newNode –> 15 –> null.
2. To insert the new node at the beginning of the list, update the next pointer of the new node to point to the current head node. This means connecting the new node’s next reference to the head node of the list, i.e., newNode –> 15 –> head.
3. The final step updates the head pointer to point to the new node, making the new node the head node of the linked list.After execution, the linked list becomes: head –> 15 –> 10 –> 8 –> 1 –> 11 –> null.”

Code

public ListNode insertAtBeginning(ListNode head, int data) {
  ListNode newNode = new ListNode(data);
  if (head == null) {
    return newNode;
  }
  newNode.next = head;
  head = newNode;
  return head;   // this head will be the new head, having the new node at the beginning  
}

This method insertAtBeginning is designed to insert a new node with the provided data at the beginning of the linked list. If the list is initially empty (i.e., head is null), the new node becomes the head of the list. Otherwise, the new node is inserted before the current head, and the head pointer is updated to point to the new node. Finally, the updated head is returned.

How to insert a node at the end of singly linked list in java?

Inserting a new node at the end of a singly linked list requires traversing the list until reaching the last node, then updating the last node’s reference to point to the new node.

Algorithm & Execution

ListNode newNode = new ListNode(15);
ListNode current = head;
while(null != current.next)
{
 current = current.next;
}
current.next = newNode;

1. Creates a new node with data 15 and next pointing to null, i.e., newNode –> 15 –> null.
2. To insert the new node at the end of the list, we need to traverse the list till the end and then assign the new node to the last node’s next pointer. For this, we create a temporary node called current, which initially points to null. Then we make this current node point to the head of the list, i.e., ListNode current = head.
3. We use a while loop to reach the last node of the list. For each iteration, we check whether the current node’s next pointer points to null or not. Also, for each iteration, we update current to its next pointer. When we reach the last node, we stop and terminate the while loop.

while(current.next != null)
{
  current = current.next;
}

Finally, we assign the new node to current.next pointer because at this point, current is the last node of the list.

Code

public ListNode insertAtEnd(ListNode head, int data) {
  ListNode newNode = new ListNode(data);
  if (head == null) {
    return newNode;
  }
  ListNode current = head;
  // Loop until the last node of the list (Note: it's not until the end of the list; in this case, current == null. Here, current.next being null means we're at the last node of the list.)
  while (current.next != null) {
    current = current.next;  // Move to the next node 
  }
  current.next = newNode;    // Assign the new node to the last node 
  return head;
}

This method insertAtEnd is designed to insert a new node with the provided data at the end of the linked list. If the list is initially empty (i.e., head is null), the new node becomes the head of the list. Otherwise, it traverses the list until it reaches the last node. Then, it assigns the new node as the next node of the last node and returns the head of the list.

How to insert a node in singly linked list after a given node in java ?

In this scenario, the initial step involves traversing the linked list until the preceding node of the insertion point is reached. Subsequently, node pointers are adjusted accordingly.

Algorithm & Execution

ListNode newNode = new ListNode(15);
newNode.next = previous.next;
previous.next = newNode;

1. Creates a new node with data 15 and its next pointer pointing to null.
2. Since we’re inserting the new node between the specified previous node and its next node, we first assign the previous node’s next pointer to the new node’s next pointer. This means connecting the new node’s next pointer to the node that was originally after the previous node, i.e., newNode –> 15 –> 11 –> null.
3. Finally, we update the previous node’s next pointer to point to the new node, so that the new node is placed between the specified previous node and its next node.After execution, the linked list becomes: head –> 10 –> 8 –> 15 –> 11 –> null.

Code

public void insertAfter(ListNode previous, int data) {
  if (previous == null) {
    System.out.println("The given previous node cannot be null.");
    return;
  }

  ListNode newNode = new ListNode(data);
  newNode.next = previous.next;
  previous.next = newNode;
}

This method insertAfter is designed to insert a new node with the provided data after a specified node in the linked list. It first checks if the given previous node is not null. If it is null, it prints an error message and returns. Otherwise, it creates a new node with the provided data, links it to the node following the specified previous node, and then updates the next reference of the previous node to point to the new node.

How to insert a node in singly linked list at a given position in java?

Inserting a node at a specific position in a singly linked list involves traversing the list to find the desired position, then adjusting the pointers accordingly.

head –> 10 –> 8 –> 11 –> null

Given a linked list with three nodes, where the first node contains the value 10 and points to position 1, the second node contains the value 8 and points to position 2, we need to insert a new node at position 3. Therefore, to insert the new node at position 3, we must traverse the linked list until we reach position 2 and then insert the new node after position 2.

Algorithm & Execution

ListNode newNode = new ListNode(15);
ListNode previous = head;
int count = 1;
while(count < position - 1)
{
  previous = previous.next;
  count++;
}
ListNode current = previous.next;
newNode.next = current;
previous.next = newNode;

1. Creates a new node with data 15 and its next pointer pointing to null, i.e., 15 –> null.
2. To insert the new node at the given position, we need to traverse until position – 1.
3. We create a temporary node named previous and point it to the head of the list, i.e., previous –> head.
4. To track the number of nodes traversed, we create a count variable and initialize it to 1, because the first node has already been traversed by the previous node, i.e., int count = 1.
5. Let’s execute a few steps within the while loop. We traverse until just before the given position node, checking how many nodes we’ve traversed using the while loop until position – 1.

while(count < position - 1)   // When we reach position - 1, the loop will terminate (when count = 2), and at this point, our 'previous' will point to position - 1.
{
  previous = previous.next;
  count++;    // As 'previous' moves forward, we increment count by one.
}

1. Moving ahead, we create a temporary node named current, which will hold the next node after ‘previous’, i.e., current –> 11, and previous –> 8.
2. The next pointer of the new node will point to the ‘current’ node, establishing a new connection between the new node and the ‘current’ node, i.e., newNode –> 15 –> 11.
3. The final step is to set the next pointer of ‘previous’ to point to the new node, i.e., previous –> 8 –> newNode –> 15.

Output: head –> 10 –> 8 –> 15 –> 11 –> null. So, we inserted 15 at position 3, where ‘previous’ –> 8 and ‘current’ –> 11, and newNode –> 15 will be between the ‘previous’ and ‘current’ node.

Code

public ListNode insertAtPosition(ListNode head, int data, int position) {
   // Perform boundary checks 
   int size = length(head);      // We use the already defined length method which returns the size of the list
   if (position > size + 1 || position < 1) {   // If the position is greater than the number of nodes in the list or less than 1, then it is an invalid position 
     System.out.println("Invalid position");
     return head;
   }

   ListNode newNode = new ListNode(data);
   if (position == 1) {                     // If position == 1, it means the list contains only one node and we want to insert at that position. Then we assign newNode next to head and return newNode as the new head of the list 
     newNode.next = head;
     return newNode;
   }
   else {
     // Else we perform our regular algorithm 
    ListNode previous = head;
    int count = 1;
    while (count < position - 1) {
       previous = previous.next;
       count++;
    }

    ListNode current = previous.next;
    newNode.next = current;
    previous.next = newNode;
    return head;
   }
 }
}

This method insertAtPosition is designed to insert a new node with the provided data at a specified position in the linked list. It first performs boundary checks to ensure that the position is valid. If the position is valid, it creates a new node with the provided data. If the position is 1, indicating that the node needs to be inserted at the beginning of the list, it updates the new node’s next reference to the current head and returns the new node as the new head of the list. Otherwise, it traverses the list to the node just before the specified position, updates the next reference of the new node to the current node at the specified position, and updates the next reference of the previous node to the new node. Finally, it returns the head of the list.

Singly Linked List Deletion Operation

Deletion operations play a crucial role in managing linked lists efficiently. In this section, we’ll delve into the intricacies of deleting nodes from singly linked lists, exploring various scenarios, implementation techniques, and best practices.

How to delete first node from a singly linked list in java?

Deleting a node from the beginning of a singly linked list is a straightforward operation. It involves updating the reference of the head node to point to the next node in the list.

head –> 10 –> 8 –> 1 –> 11 –> null;

Algorithm & Execution

ListNode temp = head;
head = head.next;
temp.next = null;

1. Let’s create a temporary node named temp and point it to head, i.e., ListNode temp = head.
2. In order to delete the first node from the list, we need to remove the reference to the first node from the head pointer. Thus, we update the head pointer to point to the next node in the list, i.e., head = head.next.
3. We disconnect the first node from the linked list by assigning null to the temp node’s next pointer, i.e., temp.next = null.

Output: head --> 8 --> 1 --> 11 --> null.

Initially, the list has 5 nodes. After deleting the first node, only three nodes remain.

Code

public ListNode deleteFirst(ListNode head) {
   if (head == null) {
      return head;
   }

   ListNode temp = head;
   head = head.next;
   temp.next = null;
   return temp;
}

This method deleteFirst is designed to delete the first node of the linked list. If the list is empty (i.e., head is null), it returns null. Otherwise, it stores the reference to the current head node in a temporary variable temp, updates the head to the next node in the list, sets the next reference of the original head to null, and then returns the deleted node.

How to delete last node of singly linked list in java?

Deleting a node from the end of a singly linked list requires traversing the list until reaching the second-to-last node, then updating its reference to NULL.

head –> 10 –> 8 –> 11 –> null

Algorithm & Execution

ListNode last = head;
ListNode previousToLast = null;
while(last.next != null)
{
  previousToLast = last;
  last = last.next;
}
previousToLast.next = null; // Disconnect the last node from the list

1. First, we create a temporary node called last, which initially points to the head node, i.e., ListNode last = head.
2. We create another temporary node called previousToLast and assign null to it.
3. We traverse until the last node’s next pointer points to null, so that last becomes the last node of the list and previousToLast points to the second last node of the list.

while(last.next != null)
{
   previousToLast = last;  // Becoming the previous node of the current last node 
   last = last.next;       // Move to the next node to become the last node for every iteration.
}

1. In the final step, we disconnect the second last node from the last node by assigning null to its next pointer, i.e., previousToLast.next = null.
2. Optionally, you can return the deleted last node if such a requirement exists, for example, for printing purposes.

Code

public ListNode deleteLast(ListNode head) {
   if (head == null) {
       return head;
   }

   ListNode last = head;
   ListNode previousToLast = null;Singly 
  
   while (last.next != null) {
     previousToLast = last;
     last = last.next;
   }

   previousToLast.next = null;
   return last;
}

This method deleteLast is designed to delete the last node of the linked list. If the list is empty (i.e., head is null), it returns null. Otherwise, it traverses the list to find the last node (last) and the node just before it (previousToLast). It then updates the next reference of previousToLast to null, effectively removing the last node from the list. Finally, it returns the deleted node.

How to delete a node from Singly Linked List at a given position in Java?

Deleting a specific node from a singly linked list involves finding the node to be deleted and adjusting the pointers of its neighboring nodes to bypass it.

head –> 10 –> 8 –> 15 –> 11 –> null

Algorithm & Execution

Listwhile(count < position - 1)
{
  previous = previous.next;
  count++;
}
Node previous = head;
int count = 1;
while(count < position - 1)
{
  previous = previous.next;
  count++;
}

ListNode current = previous.next;
previous.next = current.next;
current.next = null;

1. We create a temporary node called previous, which initially points to the head.
2. To keep track of the number of nodes we traverse, we use a count variable. Initially, it’s 1 because the first node has already been traversed by the previous node, which points to 10.
3. We traverse until the node before the position we want to delete. This means we stop at position – 1.

while(count < position - 1)
{
  previous = previous.next;
  count++;
}

1. When the while loop terminates, we are at position – 1, which is the node before the node we want to delete.
2. We create a temporary node called current, which holds the reference of the node to be deleted.
3. To delete the node, we make previous.next point to current.next, effectively bypassing the current node in the linked list.
4. Finally, we set current.next to null to disconnect it from the list.

Output: head --> 10 --> 8 --> 11 --> null.

As a result of deleting the node at position 3, which contains 15, the linked list becomes head --> 10 --> 8 --> 11 --> null.

Code

public ListNode deleteAtPosition(ListNode head, int position) {
  int size = length(head);  // Used the already defined method to find out the size of the list 
  if (position > size || position < 1) {
     System.out.println("Invalid position");
  }

  if (position == 1) {     
    // If position is 1, it means we will apply delete first node logic 
    ListNode temp = head;
    head = head.next;
    temp.next = null;
    return temp;
  }
  else {
    ListNode previous = head;
    int count = 1;
    while (count < position - 1) {
      previous = previous.next;
      count++;
    }

    ListNode current = previous.next;
    previous.next = current.next;
    current.next = null;
   
    return current;
  }
}

This method deleteAtPosition is designed to delete a node at the specified position in the linked list. It first finds the size of the list using the already defined length method and performs a boundary check to ensure that the position is valid. If the position is invalid, it prints an error message. If the position is 1, indicating that the first node needs to be deleted, it applies the logic of deleting the first node. Otherwise, it traverses the list to find the node just before the specified position (previous). It then updates the next reference of previous to skip the node to be deleted and returns the deleted node.

Conclusion

By mastering singly linked lists in Java, you’ll not only enhance your understanding of fundamental data structures but also improve your problem-solving skills and become a more proficient programmer. With the comprehensive knowledge provided in this guide, you’ll be well-equipped to tackle a wide range of programming challenges and develop efficient and elegant solutions.