Hello, young coders! Today, we’re going to explore the world of data structures using Java, specifically, Singly Linked Lists. Don’t worry if you’re new to this; we’ll take it slow and easy. So, let’s get started!
Table of Contents
What is a Singly Linked List?
A Singly Linked List is a type of data structure that holds a sequence of nodes. Each node contains some data and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence.
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
In the code above, we define a Node class, which has two attributes: data and next. data stores the information, and next is a pointer to the next node in the list.
Why Use Singly Linked Lists?
Singly linked lists are particularly useful when you need to maintain an ordered list of items, but you don’t know how many items there will be. They’re great for things like creating a playlist in a music player, or managing the history of web browser sessions.
How to Use a Singly Linked List?
Let’s create a simple singly linked list with three nodes.
class LinkedList {
Node head; // head of list
// Method to insert a new node
public void push(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
}
public class Main {
public static void main(String[] args) {
LinkedList llist = new LinkedList();
llist.push(7);
llist.push(1);
llist.push(3);
llist.push(2);
}
}
In the code above, we first create a LinkedList class, which will be used to create new linked lists. Its only property is head, which points to the first node in the list. Then, we create four nodes and manually link each node to its successor using the push method.
Insertion and Deletion
Hello again, young coders! As promised, we’re back with another article on Singly Linked Lists. This time, we’ll learn about various operations we can perform on these lists using Java. Let’s get started!
Insertion in a Singly Linked List
Inserting a new node in a linked list can be done in three ways:
- At the front of the linked list
- After a given node
- At the end of the linked list
Let’s see how we can do this:
class LinkedList {
Node head; // head of list
// Method to insert a new node at the front
public void push(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Method to insert a new node after a given node
public void insertAfter(Node prev_node, int new_data) {
if (prev_node == null) {
System.out.println("The given previous node cannot be null");
return;
}
Node new_node = new Node(new_data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}
// Method to append a new node at the end
public void append(int new_data) {
Node new_node = new Node(new_data);
if (head == null) {
head = new Node(new_data);
return;
}
new_node.next = null;
Node last = head;
while (last.next != null)
last = last.next;
last.next = new_node;
return;
}
}
Deletion in a Singly Linked List
Deletion is another important operation in a linked list. It involves removing a node from the list. We can delete a node in two ways:
- Delete a node by key
- Delete a node at a position
Here’s how we can implement these operations:
class LinkedList {
Node head; // head of list
// ...
// Method to delete a node by key
void deleteNode(int key) {
Node temp = head, prev = null;
if (temp != null && temp.data == key) {
head = temp.next;
return;
}
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
if (temp == null) return;
prev.next = temp.next;
}
// Method to delete a node at a position
void deleteNodeAtPosition(int position) {
if (head == null)
return;
Node temp = head;
if (position == 0) {
head = temp.next;
return;
}
for (int i=0; temp!=null && i<position-1; i++)
temp = temp.next;
if (temp == null || temp.next == null)
return;
Node next = temp.next.next;
temp.next = next;
}
}
Traversal and Searching
Hello again, young coders! We’re back with another article on Singly Linked Lists. This time, we’ll learn about traversal and searching operations in these lists using Java. Let’s get started!
Traversal in a Singly Linked List
Traversal is the process of going through each element in the list, one after the other. Here’s how we can do this:
class LinkedList {
Node head; // head of list
// ...
// Method to print the LinkedList
public void printList() {
Node tnode = head;
while (tnode != null) {
System.out.print(tnode.data + " ");
tnode = tnode.next;
}
}
}
In the code above, we start from the head of the list and keep moving to the next node until we reach the end of the list.
Searching in a Singly Linked List
Searching is the operation of finding a particular element in the list. Here’s how we can implement this operation:
class LinkedList {
Node head; // head of list
// ...
// Method to search a node
public boolean search(Node head, int x) {
Node current = head;
while (current != null) {
if (current.data == x)
return true;
current = current.next;
}
return false;
}
}
In the code above, we start from the head of the list and keep moving to the next node until we find the element or reach the end of the list.
Singly Linked Lists in Java: Reversal and Sorting
Hello again, young coders! We’re back with another article on Singly Linked Lists. This time, we’ll learn about reversal and sorting operations in these lists using Java. Let’s get started!
Reversal of a Singly Linked List
Reversing a linked list means making the last node to be the first one and the first node to be the last one. Here’s how we can do this:
class LinkedList {
Node head; // head of list
// ...
// Method to reverse the LinkedList
public void reverse() {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
}
In the code above, we start from the head of the list and keep reversing the next pointer of each node until we reach the end of the list.
Sorting a Singly Linked List
Sorting a linked list means arranging the elements in a specific order (either ascending or descending). Here’s how we can implement this operation:
class LinkedList {
Node head; // head of list
// ...
// Method to sort the LinkedList
public void sort() {
head = mergeSort(head);
}
private Node mergeSort(Node h) {
// Base case : if head is null
if (h == null || h.next == null) {
return h;
}
// Get the middle of the list
Node middle = getMiddle(h);
Node nextofmiddle = middle.next;
// Set the next of middle node to null
middle.next = null;
// Apply mergeSort on left list
Node left = mergeSort(h);
// Apply mergeSort on right list
Node right = mergeSort(nextofmiddle);
// Merge the left and right lists
Node sortedlist = sortedMerge(left, right);
return sortedlist;
}
// Utility function to get the middle of the linked list
private Node getMiddle(Node h) {
if (h == null)
return h;
Node fastptr = h.next;
Node slowptr = h;
while (fastptr != null) {
fastptr = fastptr.next;
if(fastptr!=null) {
slowptr = slowptr.next;
fastptr=fastptr.next;
}
}
return slowptr;
}
private Node sortedMerge(Node a, Node b) {
Node result = null;
if (a == null)
return b;
if (b == null)
return a;
if (a.data <= b.data) {
result = a;
result.next = sortedMerge(a.next, b);
} else {
result = b;
result.next = sortedMerge(a, b.next);
}
return result;
}
}
In the code above, we use the Merge Sort algorithm to sort the linked list. We first split the list into two halves, sort them separately, and then merge them.
Detecting and Removing Loops
Hello again, young coders! We’re back with another article on Singly Linked Lists. This time, we’ll learn about detecting and removing loops in these lists using Java. Let’s get started!
Detecting a Loop in a Singly Linked List
A loop in a linked list occurs when the next pointer of a node points back to a previous node in the list. Here’s how we can detect a loop:
class LinkedList {
Node head; // head of list
// ...
// Method to detect loop in the LinkedList
public boolean detectLoop() {
Node slow_p = head, fast_p = head;
while (slow_p != null && fast_p != null && fast_p.next != null) {
slow_p = slow_p.next;
fast_p = fast_p.next.next;
if (slow_p == fast_p) {
return true;
}
}
return false;
}
}
In the code above, we use two pointers, slow_p and fast_p. slow_p moves one step at a time while fast_p moves two steps at a time. If there is a loop, fast_p will meet slow_p at some point.
Removing a Loop in a Singly Linked List
If a loop is detected in the linked list, we can remove it. Here’s how we can implement this operation:
class LinkedList {
Node head; // head of list
// ...
// Method to remove loop in the LinkedList
public void removeLoop(Node loop_node) {
Node ptr1 = loop_node;
Node ptr2 = loop_node;
// Count the number of nodes in loop
int k = 1, i;
while (ptr1.next != ptr2) {
ptr1 = ptr1.next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to k nodes after head
ptr2 = head;
for (i = 0; i < k; i++) {
ptr2 = ptr2.next;
}
/* Move both pointers at the same pace,
they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
// Get pointer to the last node
while (ptr2.next != ptr1) {
ptr2 = ptr2.next;
}
/* Set the next node of the loop ending node
to fix the loop */
ptr2.next = null;
}
}
In the code above, we first count the number of nodes in the loop. Then, we fix one pointer to the head and the other pointer to k nodes after the head. We move both pointers at the same pace until they meet at the loop starting node. Finally, we set the next node of the loop ending node to null to fix the loop.
Merging and Splitting
Hello again, young coders! We’re back with another article on Singly Linked Lists. This time, we’ll learn about merging and splitting operations in these lists using Java. Let’s get started!
Merging Two Singly Linked Lists
Merging is the process of combining two linked lists into one. Here’s how we can do this:
class LinkedList {
Node head; // head of list
// ...
// Method to merge two sorted linked lists
public static Node sortedMerge(Node head1, Node head2) {
Node result;
if (head1 == null)
return head2;
if (head2 == null)
return head1;
if (head1.data <= head2.data) {
result = head1;
result.next = sortedMerge(head1.next, head2);
} else {
result = head2;
result.next = sortedMerge(head1, head2.next);
}
return result;
}
}
In the code above, we start from the heads of both lists and keep choosing the smaller node from both lists until we reach the end of one list.
Splitting a Singly Linked List
Splitting is the process of dividing one linked list into two. Here’s how we can implement this operation:
class LinkedList {
Node head; // head of list
// ...
// Method to split the linked list into two halves
public void splitList(LinkedList list1, LinkedList list2) {
Node slow_ptr = head, fast_ptr = head;
if (head == null)
return;
while (fast_ptr.next != null && fast_ptr.next.next != null) {
fast_ptr = fast_ptr.next.next;
slow_ptr = slow_ptr.next;
}
list1.head = head;
list2.head = slow_ptr.next;
slow_ptr.next = null;
}
}
In the code above, we use two pointers, slow_ptr and fast_ptr. slow_ptr moves one step at a time while fast_ptr moves two steps at a time. When fast_ptr reaches the end of the list, slow_ptr will be at the middle of the list. We then split the list into two at the middle.
Intersection and Union
Hello again, young coders! We’re back with another article on Singly Linked Lists. This time, we’ll learn about intersection and union operations in these lists using Java. Let’s get started!
Intersection of Two Singly Linked Lists
Intersection of two linked lists is a list of nodes common to both lists. Here’s how we can find the intersection:
class LinkedList {
Node head; // head of list
// ...
// Method to get intersection of two linked lists
public static LinkedList getIntersection(LinkedList list1, LinkedList list2) {
LinkedList result = new LinkedList();
Node resultNode = new Node(0);
result.head = resultNode;
Node temp1 = list1.head, temp2 = list2.head;
while (temp1 != null && temp2 != null) {
if (temp1.data == temp2.data) {
resultNode.next = new Node(temp1.data);
resultNode = resultNode.next;
temp1 = temp1.next;
temp2 = temp2.next;
} else if (temp1.data < temp2.data) {
temp1 = temp1.next;
} else {
temp2 = temp2.next;
}
}
return result;
}
}
In the code above, we start from the heads of both lists and keep moving to the next node until we reach the end of one list. If the data of both nodes are the same, we add it to the result list.
Union of Two Singly Linked Lists
Union of two linked lists is a list of all nodes from both lists. Here’s how we can find the union:
class LinkedList {
Node head; // head of list
// ...
// Method to get union of two linked lists
public static LinkedList getUnion(LinkedList list1, LinkedList list2) {
LinkedList result = new LinkedList();
Node resultNode = new Node(0);
result.head = resultNode;
Node temp1 = list1.head, temp2 = list2.head;
while (temp1 != null && temp2 != null) {
if (temp1.data == temp2.data) {
resultNode.next = new Node(temp1.data);
resultNode = resultNode.next;
temp1 = temp1.next;
temp2 = temp2.next;
} else if (temp1.data < temp2.data) {
resultNode.next = new Node(temp1.data);
resultNode = resultNode.next;
temp1 = temp1.next;
} else {
resultNode.next = new Node(temp2.data);
resultNode = resultNode.next;
temp2 = temp2.next;
}
}
while (temp1 != null) {
resultNode.next = new Node(temp1.data);
resultNode = resultNode.next;
temp1 = temp1.next;
}
while (temp2 != null) {
resultNode.next = new Node(temp2.data);
resultNode = resultNode.next;
temp2 = temp2.next;
}
return result;
}
}
In the code above, we start from the heads of both lists and keep moving to the next node until we reach the end of both lists. If the data of both nodes are the same, we add it to the result list. If the data of one node is less than the other, we add it to the result list and move to the next node in that list.
Pairwise Swap and Move Last Element to Front
Hello again, young coders! We’re back with another article on Singly Linked Lists. This time, we’ll learn about pairwise swapping and moving the last element to the front in these lists using Java. Let’s get started!
Pairwise Swap of Nodes in a Singly Linked List
Pairwise swapping involves swapping every two adjacent nodes in the list. Here’s how we can do this:
class LinkedList {
Node head; // head of list
// ...
// Method to pairwise swap nodes of the LinkedList
public void pairwiseSwap() {
Node temp = head;
/* Traverse further only if there are at least two left */
while (temp != null && temp.next != null) {
/* Swap the data */
int k = temp.data;
temp.data = temp.next.data;
temp.next.data = k;
temp = temp.next.next;
}
}
}
In the code above, we start from the head of the list and keep swapping the data of each pair of nodes until we reach the end of the list.
Move Last Element to Front in a Singly Linked List
This operation involves moving the last element of the list to the front. Here’s how we can implement this operation:
class LinkedList {
Node head; // head of list
// ...
// Method to move the last element to the front of the LinkedList
public void moveToFront() {
/* If LinkedList is not null or has more than one node */
if (head != null && head.next != null) {
Node secLast = null;
Node last = head;
/* Traverse till the end of the LinkedList */
while (last.next != null) {
secLast = last;
last = last.next;
}
/* Set the next of second last as null */
secLast.next = null;
/* Set the next of last as head */
last.next = head;
/* Change head to point to last node */
head = last;
}
}
}
In the code above, we first traverse to the end of the list. Then, we set the next of the second last node as null, the next of the last node as head, and finally change the head to point to the last node.
Conclusion
Singly linked lists are a fundamental data structure in computer science and are the stepping stone to understanding more complex structures. They might seem a bit tricky at first, but with practice, you’ll get the hang of it. Remember, every expert was once a beginner. Keep practicing.
