WikiGalaxy
Singly Linked List Structure
Introduction:
A singly linked list is a linear data structure where each element, called a node, contains data and a reference to the next node in the sequence. It allows for efficient insertion and deletion of elements.
Step 1: Initialize the head with null.
Step 2: Add a new node at the beginning.
Step 3: Traverse the list to find the position for insertion.
Step 4: Insert the new node and update pointers.
Step 5: Repeat for additional nodes.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public void insert(int newData) {
Node newNode = new Node(newData);
newNode.next = head;
head = newNode;
}
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.insert(10);
list.insert(20);
list.insert(30);
list.printList();
}
}
Console Output:
30 20 10
Detailed Explanation:
The above code defines a simple singly linked list with nodes containing integer data. The insertion method adds new nodes at the beginning of the list, and the printList method traverses the list to display its elements.
Adding Nodes at the End
Introduction:
To add nodes at the end of a singly linked list, traverse to the last node and update its next pointer to the new node.
Step 1: Initialize the head with null.
Step 2: Traverse to the last node.
Step 3: Create a new node and link it to the last node.
Step 4: Repeat for additional nodes.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public void append(int newData) {
Node newNode = new Node(newData);
if (head == null) {
head = newNode;
return;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = newNode;
}
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList();
}
}
Console Output:
10 20 30
Detailed Explanation:
In this example, the append method is used to add nodes at the end of the linked list. The method traverses to the last node and updates its next pointer to point to the new node.
Deleting a Node
Introduction:
Deleting a node from a singly linked list involves adjusting the pointers of the preceding node to skip the node to be deleted.
Step 1: Find the node to be deleted.
Step 2: Adjust the pointers of the previous node.
Step 3: Remove references to the node.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public 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;
}
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.deleteNode(20);
list.printList();
}
}
Console Output:
10 30
Detailed Explanation:
In this example, the deleteNode method removes a node with a specific key from the linked list. It adjusts the pointers of the previous node to bypass the node to be deleted.
Reversing a Linked List
Introduction:
Reversing a singly linked list involves changing the direction of the pointers within the list.
Step 1: Initialize three pointers: prev, current, and next.
Step 2: Traverse the list and reverse the pointers.
Step 3: Update the head to the last processed node.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
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;
}
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.reverse();
list.printList();
}
}
Console Output:
30 20 10
Detailed Explanation:
The reverse method reverses the linked list by iterating through the list and changing the next pointers of each node to point to the previous node, effectively reversing the list's direction.
Finding a Node
Introduction:
Finding a node in a singly linked list involves traversing the list and comparing each node's data to the target value.
Step 1: Start from the head node.
Step 2: Traverse through each node.
Step 3: Compare the node's data with the target value.
Step 4: Return the node if found.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public boolean findNode(int key) {
Node current = head;
while (current != null) {
if (current.data == key) {
return true;
}
current = current.next;
}
return false;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
System.out.println(list.findNode(20)); // true
System.out.println(list.findNode(40)); // false
}
}
Console Output:
true
false
Detailed Explanation:
The findNode method traverses the linked list and checks each node's data against the target value. If a match is found, it returns true; otherwise, it returns false.
Counting Nodes
Introduction:
Counting the number of nodes in a singly linked list involves traversing the list and incrementing a counter for each node encountered.
Step 1: Initialize a counter to zero.
Step 2: Traverse the list from the head node.
Step 3: Increment the counter for each node.
Step 4: Return the counter value.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public int countNodes() {
int count = 0;
Node current = head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
System.out.println("Number of nodes: " + list.countNodes());
}
}
Console Output:
Number of nodes: 3
Detailed Explanation:
The countNodes method iterates through the linked list, incrementing a counter for each node, and returns the total number of nodes in the list.
Finding Middle Node
Introduction:
Finding the middle node of a singly linked list can be done using two pointers: a slow pointer and a fast pointer. The slow pointer advances one step at a time, while the fast pointer advances two steps.
Step 1: Initialize two pointers, slow and fast, at the head.
Step 2: Move slow by one step and fast by two steps.
Step 3: When fast reaches the end, slow will be at the middle.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public int findMiddle() {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.data;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.append(40);
list.append(50);
System.out.println("Middle node: " + list.findMiddle());
}
}
Console Output:
Middle node: 30
Detailed Explanation:
The findMiddle method uses two pointers to find the middle node. The slow pointer moves one step at a time, while the fast pointer moves two steps, ensuring that when the fast pointer reaches the end, the slow pointer is at the middle.
Detecting a Loop
Introduction:
Detecting a loop in a singly linked list can be efficiently done using Floyd's Cycle-Finding Algorithm, which employs two pointers moving at different speeds.
Step 1: Initialize two pointers, slow and fast, at the head.
Step 2: Move slow by one step and fast by two steps.
Step 3: If they meet, a loop exists.
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public boolean detectLoop() {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.head.next.next.next = list.head; // Creating a loop for testing
System.out.println("Loop detected: " + list.detectLoop());
}
}
Console Output:
Loop detected: true
Detailed Explanation:
The detectLoop method uses two pointers to detect a loop. If the slow and fast pointers meet, it indicates the presence of a loop in the linked list.
Removing Duplicates
Introduction:
Removing duplicates from a singly linked list involves iterating through the list and keeping track of seen values using a hash set.
Step 1: Initialize a hash set to store seen values.
Step 2: Traverse the list and check each node's data.
Step 3: If data is seen, remove the node; otherwise, add it to the set.
import java.util.HashSet;
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class LinkedList {
Node head;
public void removeDuplicates() {
HashSet set = new HashSet<>();
Node current = head;
Node prev = null;
while (current != null) {
if (set.contains(current.data)) {
prev.next = current.next;
} else {
set.add(current.data);
prev = current;
}
current = current.next;
}
}
public void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(10);
list.append(20);
list.append(10);
list.append(30);
list.removeDuplicates();
list.printList();
}
}
Console Output:
10 20 30
Detailed Explanation:
The removeDuplicates method uses a hash set to track seen values and removes any duplicates encountered during traversal of the linked list.
