Java

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.