Java

Linked lists are a fundamental data structure in computer science, offering flexibility and efficiency in managing collections of data. Among the variations of linked lists, the circular linked list stands out for its unique structure and applications. In this blog post, we’ll delve into the concept of circular linked lists, explore their implementation in Java, and discuss their advantages and use cases.

Understanding Circular Linked Lists

A circular linked list is similar to a regular linked list, with the key distinction being that the last node points back to the first node, forming a circle. Unlike linear linked lists, which have a NULL pointer at the end, circular linked lists have no NULL pointers within the list itself. This circular structure allows for traversal from any node to any other node within the list.

The basic components of a circular linked list include:

• Node: A unit of data that contains both the data value and a reference (pointer) to the next node in the sequence.
• Head: A reference to the first node in the list. In a circular linked list, this node is connected to the last node, forming a circle.
• Tail: Although not always explicitly maintained, it refers to the last node in the list, which points back to the head.

How to represent a circular singly linked list in java?

A Circular Singly Linked List is similar to a singly linked list, with the difference that in a circular linked list, the last node points to the first node and not null. Instead of keeping track of the head, we keep track of the last node in the circular singly linked list.

For example:

In a Singly Linked List:

head –> 1 –> 8 –> 10 –> 16 –> null

In a Circular Singly Linked List:

last --> 16 --> 1 --> 8 --> 10 --> 
    ^____________________________|

last –> 16 –> 1 –> 8 –> 10 –> 16 // Please refer to the actual diagram for clarification.

We can insert nodes at both the end and beginning with constant time complexity.

How to implement a Circular Singly Linked List in a java ?

public class CircularSinglyLinkedList {

  private ListNode last;        // Keep track of the last node of the circular linked list   
  private int length;           // Hold the size of the circular singly list

  private class ListNode {
    private int data;
    private ListNode next;

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

  public CircularSinglyLinkedList() {
    last = null;       // When we initialize the circular singly linked list, we know the last points to null and that time the list is empty 
    length = 0;        // So the length is also 0;
  }

  // Gives the size of the circular singly linked list 
  public int length() {
    return length;
  }

  // Check whether the circular list is empty or not 
  public boolean isEmpty() {
    return length == 0;
  }


  public void createCircularLinkedList() {
    ListNode first = new ListNode(1);
    ListNode second = new ListNode(5);
    ListNode third = new ListNode(10);
    ListNode fourth = new ListNode(15);
 
    first.next = second;
    second.next = third;
    third.next = fourth;
    fourth.next = first;      // Here we make the list in circular nature by assigning the first node 

    last = fourth;         // Last node points to the fourth node
  }


  public static void main(String[] args) {
     CircularSinglyLinkedList csll = new CircularSinglyLinkedList();
     csll.createCircularLinkedList();
  }
}

This Java class CircularSinglyLinkedList defines a circular singly linked list. It includes inner class ListNode for representing each node in the list. The class provides methods to create a circular linked list, check its length, and check whether it is empty. The main method demonstrates creating a circular linked list instance and initializing it.

How to traverse and print a circular linked list in java ?

last --> 16 --> 1 --> 8 --> 10 --> 
    ^____________________________|

Algorithm & Execution

if (last == null) {
    return;
}
ListNode first = last.next;
while (first != last) {
    System.out.println(first.data + "");
    first = first.next;
}
System.out.println(first.data + "");

The basic idea here is to find the first node using the last node, and then traverse the list from the first node to the last node. When the first node equals the last node, at that point, we are at the last node, but our while loop terminates, so we couldn’t print the last node’s data. That’s why we print it separately after the loop.

Code

public void display() {
   if (last == null) {
      return;
   }
   ListNode first = last.next;
   while (first != last) {
     System.out.println(first.data + "");
     first = first.next;
   }
   System.out.println(first.data + "");
}

This method display is designed to print the elements of the circular singly linked list. It starts from the first node, which is the node after the last node. Then, it traverses the list until it reaches the last node, printing the data of each node. Finally, it prints the data of the last node itself. If the list is empty (i.e., last is null), the method simply returns without performing any operation.

How to insert node at the beginning of a circular Singly Linked List in java ?

ListNode temp = new ListNode(data);
if (last == null) {
    last = temp;
} else {
    temp.next = last.next;
}
last.next = temp;
length++;

1. We create a temporary node (temp) which we will insert at the beginning of the circular list.
2. If the last node is null, it means our list is empty. In this case, we assign the temp node to be the last node. Both last and temp now point to the same new node we inserted. We update the last.next pointer to point to temp, forming the circular nature for the first node.
3. If the list is not empty (last is not null), we create a new temp node with the given data, and it points to null initially. Then, we update temp.next to point to last.next, so it will be added at the beginning of the last node. Even now, last and temp.next will point to the last node. We need to update the last node’s next pointer to temp so that the circular list nature remains intact.
4. Finally, we increment the length by 1 because every time we add a new node at the beginning of the last node.

Code

public void insertFirst(int data) {
  ListNode temp = new ListNode(data);
  if (last == null) {
      last = temp;
  } else {
      temp.next = last.next;
  }
  last.next = temp;
  length++;
}

This method insertFirst is designed to insert a new node with the given data at the beginning of the circular singly linked list. If the list is empty (i.e., last is null), the new node becomes both the first and last node. Otherwise, the new node is inserted after the last node, and its next reference is updated to point to the node originally after the last node. Finally, the length of the list is incremented.

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

ListNode temp = new ListNode(data);
if (last == null) {   // list is empty
   last = temp;
   last.next = last;
} else {              // if list is non-empty
   temp.next = last.next;
   last.next = temp;
   last = temp;
}
length++;

1. First, we create a new temporary node (temp) with the given data value.
2. Initially, the circular list is empty, so last will point to null, i.e., last --> null.
3. When we insert a new node, we check whether we are inserting into an empty list or a non-empty list.
4. If the list is empty, we point last to our temporary node, i.e., last = temp.
5. To create a circular structure, we need to make last.next point to last itself, i.e., last.next = last.
6. After that, we increment the length by 1 as we successfully inserted a new node into the list.
7. Now, let’s consider the scenario of a non-empty circular list. In this case, first, we assign last.next to the last node itself when there is only one node. If there is more than one node, then last.next will point to the first node, and temp.next will point to null.
8. Then, we attach the new temporary node to the end by assigning it as last.next. Previously, it pointed to itself because there was only one node. If there are more than one node, it will point to the temp node because the last node becomes the first, and temp will always become the last node to maintain the circular chain nature.
9. Finally, temp becomes our new last because it is added at the end.

So, the basic logic is to add the temporary node at the end and always make that newly inserted node the last one.

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

if (isEmpty()) {
   throw new NoSuchElementException();
}
ListNode temp = last.next;
if (last.next == last) {
   last = null;
} else {
   last.next = temp.next;
}
temp.next = null;
length--;
return temp;

1. If the list is empty, meaning there are no elements to remove, we throw a NoSuchElementException.
2. We create a temporary node temp which will store the node to be removed, i.e., the first node (last.next).
3. If last.next points to last itself, it means there is only one node in the list. In this case, we remove the last node by assigning null to last.
4. If last.next doesn’t point to last, it means there are multiple nodes in the list. We remove the first node by updating last.next to point to the second node (temp.next).
5. We then set temp.next to null to detach temp from the list.
6. We decrement the length of the list by 1 since we have successfully removed a node.
7. Finally, we return the removed node temp.

So, the main logic is to remove the first node by adjusting pointers and then returning the removed node.

Advantages of Circular Linked Lists

Circular linked lists offer several advantages over their linear counterparts:

1. Efficient Insertion and Deletion: Insertion and deletion operations can be performed quickly, especially at the beginning or end of the list, as there’s no need to traverse the entire list.
2. Circular Traversal: With a circular structure, traversal from any point in the list to any other point becomes straightforward.
3. Memory Efficiency: Circular linked lists save memory by eliminating the need for a NULL pointer at the end of the list.

Use Cases of Circular Linked Lists

Circular linked lists find applications in various scenarios, including:

• Round-Robin Scheduling: In operating systems, circular linked lists are used to implement round-robin scheduling algorithms, where tasks are executed in a circular order.
• Music and Video Playlists: Circular linked lists can be used to implement circular playlists, allowing seamless looping from the last item to the first.
• Resource Management: In resource allocation systems, circular linked lists can represent a pool of resources where allocation and deallocation operations are frequent.

Conclusion

Circular linked lists provide an elegant solution to certain problems by leveraging their circular structure and efficient operations. In Java, implementing a circular linked list involves managing node connections carefully to maintain the circular property. Understanding the strengths and applications of circular linked lists can aid in designing efficient algorithms and data structures for various computational tasks.

Singly linked lists are versatile data structures that offer efficient insertion, deletion, and traversal operations. However, beyond the basic CRUD (Create, Read, Update, Delete) operations, there lies a realm of logical operations that can be performed on singly linked lists. In this detailed blog, we’ll explore some of the most important logical operations that can be applied to singly linked lists in Java, providing insights into their implementation and usage.

How to search an element in a Singly Linked List in Java?

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

ListNode current = head;
while(current != null)
{
  if(current.data == searchKey)
  {
    return true;
  }
  current = current.next;
}
return false;

As the main logic, we need to traverse the list node by node. While traversing, we check each node’s data. If it matches the search key, then we’ve found the key; otherwise, we haven’t found it.

1. We create a temporary node current to traverse the list until the end. Initially, it’s set to the head node, i.e., ListNode current = head.
2. Using a while loop, we traverse until the end of the list. If current becomes null, it means we’ve reached the end, and we terminate the loop. During traversal, we check each node’s data with the search key. If we find a match, we return true immediately and exit the loop.

while( current  != null )
{
  if(current.data == searchKey)
  {
   return true;
  }
  current = current.next;      // Move to the next node in each iteration 
}

1. Finally, if we haven’t found the exact search key after traversing the entire list, we return false.

Output:

• If the search key is 1, then it is found.
• If the search key is 12, then it is not found.

Code

public boolean find(ListNode head, int searchKey) {
  if (head == null) {
    return false;
  }

  ListNode current = head;
  while (current != null) {
    if (current.data == searchKey) {
      return true;
    }
    current = current.next; // Move to the next node
  }
  return false;
}

This method find is designed to search for a specific key value (searchKey) within the linked list. It returns true if the key is found, and false otherwise. If the list is empty (i.e., head is null), it immediately returns false. Otherwise, it traverses the list, comparing the data value of each node (current.data) with the search key. If a match is found, it returns true. If the end of the list is reached without finding the key, it returns false.

How to reverse a singly linked list in java

Input:

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

Output:

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

ListNode current = head;
ListNode previous = null;
ListNode next = null;
while(current != null)
{
  next = current.next;
  current.next = previous;
  previous = current;
  current = next;
}
return previous;

The main logic is to traverse the list until the end and apply a logic that reverses the pointing of each node. Ultimately, we obtain the reversed list.

1. We create three temporary nodes:
   • current points to head.
   • previous initially points to null.
   • next also initially points to null.
2. We traverse the list node by node using a while loop. The loop iterates until current becomes null.
3. In each iteration of the while loop, we perform the following operations:

while(current != null)
{
   next = current.next;        // Store the reference to the next node
   current.next = previous;    // Reverse the pointing direction of the current node
   previous = current;         // Move forward: previous becomes current
   current = next;             // Move forward: current becomes next
}

1. • First, we move to the next node by assigning next to current.next.
   • Second, we reverse the reference of the current node to point to the previous node.
   • Third, we update previous to be the current node, preparing for the next iteration.
   • Finally, we move forward by assigning next to current.
   This process effectively reverses the pointing direction of each node in the list.
2. When the while loop terminates, we have reversed the entire list, and the last previous node becomes the new head of the list. So, we return previous.

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

After the reversal, the list becomes reversed.

Code

public ListNode reverse(ListNode head)
{
   if(head == null)
   {
      return head;
   }
   
   ListNode current = head;
   ListNode previous = null;
   ListNode next = null;

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

This method reverse is designed to reverse the linked list. If the list is empty (i.e., head is null), it immediately returns null. Otherwise, it iterates through the list, changing the next pointer of each node to point to the previous node. At the end of the iteration, it returns the last node encountered, which becomes the new head of the reversed list.

How to find middle node in singly linked list in java ?

To find the middle node in a singly linked list, we employ the same logic for two different cases.

Case 1: List having an even number of nodes:

For example, head –> 10 –> 8 –> 1 –> 11 –> null

In this case, the middle node is 1.

Case 2: List having an odd number of nodes:

For example, head –> 10 –> 8 –> 1 –> 11 –> 15 –> null

Here again, the middle node is 1.

ListNode slowPtr = head;
ListNode fastPtr = head;
while(fastPtr != null && fastPtr.next != null) {
    slowPtr = slowPtr.next;      // Move slow pointer to the next node
    fastPtr = fastPtr.next.next; // Move fast pointer to two nodes ahead
}
return slowPtr; // Return the slow pointer, which points to the middle node

The main logic involves using two different pointers: a slow pointer and a fast pointer. The slow pointer moves to the next node one by one, while the fast pointer moves two nodes ahead at a time. When the fast pointer reaches the end (either pointing to null or its next points to null), the while loop terminates, and we return the slow pointer, which represents the middle node in both cases.

Code

public ListNode getMiddleNode() {
    if (head == null) {
      return null;
    }
    
    ListNode slowPtr = head;
    ListNode fastPtr = head;
 
    while (fastPtr != null && fastPtr.next != null) {
       slowPtr = slowPtr.next;
       fastPtr = fastPtr.next.next;
    }
    return slowPtr;
}

This method getMiddleNode is designed to find and return the middle node of the linked list. It initializes two pointers, slowPtr and fastPtr, both starting at the head of the list. The slowPtr moves one node at a time while the fastPtr moves two nodes at a time. When the fastPtr reaches the end of the list (or null), the slowPtr will be at the middle node. If the list is empty (i.e., head is null), it returns null.

How to detect a loop in Singly Linked List in java ?

In a given singly linked list, if there exists a loop, it can be identified by employing the following logic.

Consider the linked list: head –> 1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 3

As it can be seen, the list loops back to the node with value 3.

The main logic remains the same as before: we use two different pointers, a slow pointer and a fast pointer. However, in this case, we move the fast pointer first, followed by the slow pointer. Due to the loop, these pointers will eventually meet at the same node. Once the slow and fast pointers are equal, pointing to the same node, we can conclude that there exists a loop in the linked list. If the pointers never meet, then the list does not contain any loop.

ListNode fastPtr = head;
ListNode slowPtr = head;
while(fastPtr != null && fastPtr.next != null) {
    fastPtr = fastPtr.next.next; // Move fast pointer two nodes ahead
    slowPtr = slowPtr.next;      // Move slow pointer one node ahead
    if(slowPtr == fastPtr) {     // If slow pointer meets fast pointer, it indicates a loop
        return true;
    }
}
return false; // If loop termination condition is met without meeting points, return false

The main logic is the same as before: we use two pointers, a slow pointer and a fast pointer, to traverse the list. However, in this case, we move the fast pointer two nodes ahead and the slow pointer one node ahead in each iteration. If the pointers meet at any point during traversal, it indicates the presence of a loop in the list, and we return true. If the loop termination condition is met without the pointers meeting, it means there is no loop in the list, and we return false.

Code

public boolean containsLoop() {
  ListNode fastPtr = head;
  ListNode slowPtr = head;

  while (fastPtr != null && fastPtr.next != null) {
    fastPtr = fastPtr.next.next;        // We need to move fast pointer fast so that it will catch the slow pointer if a loop is present   
    slowPtr = slowPtr.next;
   
    if (slowPtr == fastPtr) {
      return true;
    }
  }
  return false;
}

public void createALoopInLinkedList() {
  ListNode first = new ListNode(1);  
  ListNode second = new ListNode(2);
  ListNode third = new ListNode(3);
  ListNode fourth = new ListNode(4);
  ListNode fifth = new ListNode(5);
  ListNode sixth = new ListNode(6);

  head = first;
  first.next = second;
  second.next = third;
  third.next = fourth;
  fourth.next = fifth;
  fifth.next = sixth;
  sixth.next = third;
}

The method containsLoop checks whether a loop exists in the linked list using Floyd’s Cycle Detection Algorithm. It initializes two pointers, fastPtr and slowPtr, both starting at the head of the list. The fastPtr moves twice as fast as the slowPtr. If there is a loop in the list, eventually, the fastPtr will catch up with the slowPtr. If no loop is found, the method returns false.

The method createALoopInLinkedList is a helper method to create a loop in the linked list for testing purposes. It creates a linked list with six nodes and then creates a loop by making the next reference of the last node point to the third node.

How to find nth node from the end of a Singly Linked List in java?

Consider the singly linked list:

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

If we want to find the node that is “n” positions from the end of the list, where “n” is given as 2, then the node containing 11 would be that node.

ListNode mainPtr = head;  // It will move forward when the reference pointer covers the nth position forward from the head 
ListNode referencePtr = head;  // It will move twice: first, it covers the nth distance from the head, then it goes till the end with mainPtr, so that mainPtr will reach the exact position
int count = 0;   // It is to track the number of nodes the reference pointer moved forward
while(count < n) {
    refPtr = refPtr.next;
    count++;
}
while(refPtr != null) {
    refPtr = refPtr.next;
    mainPtr = mainPtr.next;
}

return mainPtr;

The main logic involves using two pointers: a main pointer and a reference pointer. The reference pointer moves forward until it reaches the nth position from the head, while the main pointer remains stationary. After reaching the nth position, the reference pointer continues moving until it reaches the end of the list, while the main pointer moves along with it. When the reference pointer reaches the end of the list, the main pointer will be pointing to the nth node from the end of the list.

Code

public ListNode getNthNodeFromEnd(int n) {

 if (head == null) {
    return null;
 }
 
 if (n <= 0) {
     throw new IllegalArgumentException("Invalid value: n = " + n);
 }

 ListNode mainPtr = head;  // It will move forward when the reference pointer covers the nth position forward from the head  
 ListNode refPtr = head;   // It will move twice: first, it covers nth distance from head, then it goes till the end with mainPtr, so that mainPtr will reach the exact position.

 int count = 0;   // It is to track the number of nodes refPtr moved forward

 while (count < n) {
  if (refPtr == null) {
      throw new IllegalArgumentException(n + " is greater than the number of nodes in the list");
  }

  refPtr = refPtr.next;
  count++;
 }

 while (refPtr != null) {
  refPtr = refPtr.next;
  mainPtr = mainPtr.next;
 }

 return mainPtr;    // The returned mainPtr will be at the nth position from the end of the list
}

This method getNthNodeFromEnd is designed to find and return the nth node from the end of the linked list. It initializes two pointers, mainPtr and refPtr, both starting at the head of the list. The refPtr moves forward n positions from the head. Then, both pointers move forward simultaneously until the refPtr reaches the end of the list. At this point, the mainPtr will be at the nth node from the end. If the list is empty or if the value of n is less than or equal to 0, the method throws an IllegalArgumentException.

How to remove duplicates from sorted Singly Linked List in java?

For the given input of a sorted linked list:

head –> 1 –> 1 –> 2 –> 3 –> 3 –> null

The desired output is a sorted linked list with duplicates removed:

head –> 1 –> 2 –> 3 –> null

ListNode current = head;
while(current != null && current.next != null) {
    if(current.data == current.next.data) {
        current.next = current.next.next; // Connect current to the next next node to remove the duplicate node
    } else {
        current = current.next; // Move to the next node if no duplicate is found
    }
}

The main logic involves traversing the list node by node using a current pointer. While traversing, we check whether the data of the current node is equal to the data of the next node. If they are equal, it means a duplicate node is found, so we connect the current node to the next next node, effectively removing the duplicate node between them. If no duplicate is found, we simply move to the next node. This process continues until we reach the end of the list or the current node becomes null.

Code

public void removeDuplicates() {
  
  if (head == null) {
    return;
  }

  ListNode current = head;

  while (current != null && current.next != null) {
     if (current.data == current.next.data) {
       current.next = current.next.next;
     } else {
       current = current.next;
     }
  }
}

This method removeDuplicates is designed to remove duplicates from a sorted linked list. It iterates through the list using the current pointer. If the current node’s data is equal to the data of the next node, it skips the next node by updating the next reference of the current node to skip the duplicate node. Otherwise, it moves the current pointer to the next node in the list. If the list is empty (i.e., head is null), the method returns without performing any operation.

Now, How to insert a node in a sorted Singly Linked List in java?

Given the sorted linked list:

head –> 1 –> 8 –> 10 –> 16 –> null

And a new node:

newNode –> 11 –> null

We want to insert the new node (11) into the sorted list such that the sorting order remains the same.

After insertion, the updated list would be:

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

ListNode current = head;
ListNode previous = null;
while(current != null && current.data < newNode.data) {
    previous = current;
    current = current.next;
}
// When we reach the insertion point, we have references to current, previous, and newNode.
// Now, we rearrange the pointers so that previous points to newNode and newNode points to current.
newNode.next = current;
if (previous != null) {
    previous.next = newNode;
} else {
    // If previous is null, it means the newNode should become the new head.
    head = newNode;
}
return head;

The main logic involves traversing the sorted linked list until we find the appropriate position to insert the new node while maintaining the sorting order. We traverse the list node by node, comparing the data of each node with the data of the new node. We continue this process until we find a node whose data is greater than or equal to the data of the new node, or until we reach the end of the list.

When we reach the insertion point, we have references to three nodes: the current node, the previous node (the node before the insertion point), and the new node. To insert the new node into the list, we rearrange the pointers so that the previous node points to the new node, and the new node points to the current node.

If the previous node is null, it means that the new node should become the new head of the list. In this case, we update the head pointer to point to the new node.

Code

public ListNode insertInSortedList(int value) {
  ListNode newNode = new ListNode(value);
 
  if (head == null) {
    return newNode;
  }

  ListNode current = head;
  ListNode previous = null;

  while (current != null && current.data < newNode.data) {   // Will go till the end while checking the sorting order between the current node and the new node data 
     previous = current;
     current = current.next;
  }
  
  // When we reach the insertion point, we have our current, previous, and newNode references so we only need to arrange pointers.
  // So that previous will point to newNode and newNode will point to current.
 
  newNode.next = current;
  if (previous == null) { // If the new node is to be inserted at the beginning
    head = newNode;
  } else {
    previous.next = newNode;
  }
  
  return head;    
}

This method insertInSortedList is designed to insert a new node with the provided value into a sorted linked list. If the list is empty (i.e., head is null), the new node becomes the head of the list. Otherwise, it traverses the list to find the correct position to insert the new node while maintaining the sorted order. Once the insertion point is found, it updates the pointers to insert the new node. Finally, it returns the head of the list.

How to remove a given key from singly linked list in java?

Given the linked list:

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

Suppose our key is 11, and we want to remove it from the list.

After removal, the updated list would be:

head –> 1 –> 8 –> 10 –> 16 –> null

ListNode current = head;
ListNode previous = null;

// Traverse the list to find the node with the key value
while(current != null && current.data != key) {
   previous = current;
   current = current.next;
}

// If we reached the end of the list without finding the key, return
if(current == null) {
  return;
}

// If we found the key, remove the node by adjusting the previous node's next reference
if(previous != null) {
  previous.next = current.next;
} else {
  // If the key is found at the head, update the head pointer to skip the current node
  head = current.next;
}

The main logic involves traversing the linked list until we find the node with the specified key value. While traversing, we keep track of the previous node as well.

If we reach the end of the list without finding the key, it means the key doesn’t exist in the list, so we return without performing any removal.

If we find the node with the key value, we remove it from the list by adjusting the next reference of the previous node to skip over the current node. However, if the key is found at the head of the list, we update the head pointer to skip over the current node.

Code

public void deleteNode(int key) {
 
  ListNode current = head;
  ListNode previous = null;

  // If we find our key at the first node that is head, just update head to point to the next node.
  if (current != null && current.data == key) {
     head = current.next;
     return;
  }

  while (current != null && current.data != key) {
    previous = current;
    current = current.next;
  }
 
  // If we reached the end of the list (current == null), the key was not found, so return without performing any operation.
  if (current == null) {
    return;
  }

  // If we found the key, update the next reference of the previous node to point to the next node of the current node, effectively removing the current node.
  previous.next = current.next;
}

This method deleteNode is designed to delete a node with the given key value from the linked list. It iterates through the list using the current pointer to find the node with the specified key value while keeping track of the previous node using the previous pointer. If the key is found at the first node (head), it updates the head to point to the next node. If the key is found in the middle of the list, it updates the next reference of the previous node to skip the current node. If the key is not found in the list, the method simply returns without performing any operation.

Bonus: Two Sum Problem in java

Problem: Given an array of integers, return the indices of the two numbers such that they add up to a specific target.

Example: Given array of integers: {2, 11, 5, 10, 7, 8}, and target = 9.

Solution: Since arr[0] + arr[4] = 2 + 7 = 9, we return {0, 4} as the indices.

The main logic involves using a map for fast lookup of stored values to find the exact sum of the target. We require one map for lookup purposes and one result array to store the indices of the two numbers that add up to the target sum from the given array. Here’s how it works:

1. We iterate through the array, examining each element.
2. At each element, we calculate the difference between the target and the current element.
3. We check if this difference exists in the map. If it does, it means we have found the two numbers that add up to the target.
4. We return the indices of the current element and the element with the required difference.
5. If the difference is not found in the map, we store the current element’s value along with its index in the map for future lookups.

Algorithm & Executions

int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>();

for(int i = 0; i < numbers.length; i++) {
    int complement = target - numbers[i];
    if(map.containsKey(complement)) {
        result[0] = map.get(complement);
        result[1] = i;
        return result;
    }
    map.put(numbers[i], i);
}

return result;

The main logic involves using a hash map to store the indices of elements in the array. We traverse the array and, for each element, check if its complement (target – current number) exists in the hash map. If it does, it means we have found two numbers that add up to the target, so we return their indices. If not, we add the current number and its index to the hash map for future reference.

Code

public static int[] twoSum(int[] numbers, int target) {
  int[] result = new int[2];
  Map<Integer, Integer> map = new HashMap<>();
 
  for (int i = 0; i < numbers.length; i++) {
    if (!map.containsKey(target - numbers[i])) {
      map.put(numbers[i], i);
    } else {
      result[1] = i;
      result[0] = map.get(target - numbers[i]);
      return result;
    }     
  }

  throw new IllegalArgumentException("Two numbers not found");
}

This method twoSum is designed to find and return the indices of the two numbers in the numbers array that add up to the target value. It utilizes a hashmap to store the difference between the target and each element of the array along with its index. It iterates through the array, checking if the hashmap contains the difference between the target and the current element. If not, it adds the current element and its index to the hashmap. If it finds the difference in the hashmap, it retrieves the index of the other number and returns the indices as the result. If no such pair of numbers is found, it throws an IllegalArgumentException.

Note: Why is this Array Manipulation problem being discussed here?

While the problem of finding two numbers in an array that add up to a specific target is not directly related to singly linked list operations, the underlying logic and problem-solving techniques used in solving array manipulation problems can indeed be helpful in solving problems related to singly linked lists.

Many problem-solving techniques and algorithms used in array manipulation, such as iterating over elements, using hash maps for fast lookups, or employing two-pointer approaches, can also be applied to singly linked list problems. Additionally, understanding how to efficiently manipulate data structures and analyze patterns in data is a fundamental skill that can be transferred across various problem domains.

In the context of computer science and algorithmic problem-solving, building a strong foundation in problem-solving techniques through various types of problems, including those involving arrays, linked lists, trees, graphs, and more, can enhance your ability to tackle a wide range of problems effectively.

So, while the specific problem discussed may not directly relate to singly linked lists, the problem-solving skills and techniques learned from array manipulation problems can certainly be beneficial in solving problems related to singly linked lists and other data structures.

Conclusion

By mastering the logical operations of singly linked list in Java, programmers can unlock the full potential of this versatile data structure. Whether it’s searching, reversing, merging, or detecting loops, understanding these operations equips developers with powerful tools for solving complex problems and building efficient algorithms. With the insights provided in this blog, programmers can elevate their skills and become more proficient in leveraging singly linked lists for various applications.

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.

Linked lists are fundamental data structures in computer science that provide dynamic memory allocation and efficient insertion and deletion operations. In Java, linked lists are commonly used for various applications due to their flexibility and versatility. In this blog post, we will explore linked lists in Java in detail, covering their definition, types, operations, and implementation.

What is a Linked List?

A linked list is a linear data structure consisting of a sequence of elements called nodes. Each node contains two parts: the data, which holds the value of the element, and a reference (or link) to the next node in the sequence. Unlike arrays, which have fixed sizes, linked lists can dynamically grow and shrink as elements are added or removed.

Key Concepts

• Node: The fundamental building block of a linked list. Each node consists of:
  • Data: The actual information you store (e.g., integer, string).
  • Next pointer: References the next node in the list.
  • Previous pointer (for doubly-linked lists): References the preceding node, enabling bidirectional traversal.
• Head: The starting point of the list, pointing to the first node.
• Tail: In singly-linked lists, points to the last node. In doubly-linked lists, points to the last node for forward traversal and the first node for backward traversal.

Types of Linked Lists

1. Singly Linked List

In a singly linked list, each node has only one link, which points to the next node in the sequence. Traversal in a singly linked list can only be done in one direction, typically from the head (start) to the tail (end) of the list. Singly-linked lists are relatively simple and efficient in terms of memory usage.

2. Doubly Linked List

In a doubly linked list, each node has two links: one points to the next node, and the other points to the previous node. This bidirectional linking allows traversal in both forward and backward directions. Doubly linked lists typically require more memory per node due to the additional reference for the previous node.

3. Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circular structure. Circular linked lists can be either singly or doubly linked and are useful in scenarios where continuous looping is required.

How to represent a LinkedList in Java ?

Now we know that, A linked list is a data structure used for storing a collection of elements, objects, or nodes, possessing the following properties:

1. It consists of a sequence of nodes.
2. Each node contains data and a reference to the next node.
3. The first node is called the head node.
4. The last node contains data and points to null.

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

Implementation Of a Node in a linked list

Generic Type Implementation

public class ListNode<T> {
    private T data;
    private ListNode<T> next;
}

In the generic type implementation, the class ListNode<T> represents a node in a linked list that can hold data of any type. The line public class ListNode<T> declares a generic class ListNode with a placeholder type T, allowing flexibility for storing different data types. The private member variable data of type T holds the actual data stored in the node, while the next member variable is a reference to the next node in the linked list, indicated by ListNode<T> next. This design enables the creation of linked lists capable of storing elements of various types, offering versatility and reusability.

Integer Type Implementation

public class ListNode {
    private int data;
    private ListNode next;
}

In contrast to the generic type, the integer type implementation, represented by the class ListNode, is tailored specifically for storing integer data. The class ListNode does not use generics and defines a private member variable data of type int to hold integer values within each node. Similarly, the next member variable is a reference to the next node in the linked list, indicated by ListNode next. This implementation is more specialized and optimized for scenarios where the linked list exclusively stores integer values, potentially offering improved efficiency due to reduced overhead from generics.

Node Diagram

| data | next |===>

This node diagram depicts the structure of each node in the linked list. Each node consists of two components: data, representing the value stored in the node, and next, a pointer/reference to the next node in the sequence. The notation | data | next |===> illustrates this structure, where data holds the value of the node, and next points to the subsequent node in the linked list. The arrow (===>) signifies the connection between nodes, indicating the direction of traversal from one node to another within the linked list.

Representation of Linked List

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

The representation of the linked list illustrates a sequence of nodes starting from the head node. Each node contains its respective data value, with arrows (===>) indicating the connections between nodes. The notation head ===> |10| ===> |8| ===> |9| ===> |11| ===> null shows the linked list structure, where head denotes the starting point of the list. The data values (10, 8, 9, 11) are enclosed within nodes, and null signifies the end of the linked list. This representation visually demonstrates the organization and connectivity of nodes within the linked list data structure.

Code Implementation

public class LinkedList
{

  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)
  {
   
  }
}

The above code snippet outlines the structure of a linked list in Java. The LinkedList class serves as the main container for the linked list, featuring a private member variable head that points to the first node. Within this class, there exists a static inner class named ListNode, which defines the blueprint for individual nodes. Each ListNode comprises an integer data field and a reference to the next node. The constructor of ListNode initializes a node with the given data and sets the next reference to null by default. The main method, though currently empty, signifies the program’s entry point where execution begins. It provides a foundational structure for implementing linked lists, enabling the creation and manipulation of dynamic data structures in Java programs.

Common Operations on Linked Lists

We will see each operation in much detail in the next article, where we will discuss Singly Linked Lists in more detail. Right now, let’s see a brief overview of each operation:

1. Insertion

Insertion in a linked list involves adding a new node at a specified position or at the end of the list. Depending on the type of linked list, insertion can be performed efficiently by updating the references of adjacent nodes.

2. Deletion

Deletion involves removing a node from the linked list. Similar to insertion, deletion operations need to update the references of adjacent nodes to maintain the integrity of the list structure.

3. Traversal

Traversal refers to visiting each node in the linked list sequentially. Traversal is essential for accessing and processing the elements stored in the list.

4. Searching

Searching involves finding a specific element within the linked list. Linear search is commonly used for searching in linked lists, where each node is checked sequentially until the desired element is found.

5. Reversing

Reversing a linked list means changing the direction of pointers to create a new list with elements in the opposite order. Reversing can be done iteratively or recursively and is useful in various algorithms and problem-solving scenarios.

Conclusion

Linked lists are powerful data structures in Java that offer dynamic memory allocation and efficient operations for managing collections of elements. Understanding the types of linked lists, their operations, and their implementation in Java is essential for building robust applications and solving complex problems efficiently. Whether you’re a beginner or an experienced Java developer, mastering linked lists will enhance your programming skills and enable you to tackle a wide range of programming challenges effectively. Happy coding!