WikiGalaxy
Singly Linked List Operations
Introduction:
A singly linked list is a linear data structure consisting of nodes where each node contains data and a pointer to the next node in the sequence. This structure allows for efficient insertions and deletions.
Operations Overview:
Common operations include insertion at the front, end, or middle, and deletion from the front, end, or middle.
Step 1: Insert at Front
[New Node | Next] -> [Head | Next] -> ... -> [Data | Null]
Step 2: Insert at End
[Head | Next] -> ... -> [New Node | Null]
Step 3: Insert at Middle
[Head | Next] -> ... -> [New Node | Next] -> ... -> [Data | Null]
Step 4: Delete from Front
[Head | Next] -> ... -> [Data | Null]
Step 5: Delete from End
[Head | Next] -> ... -> [Data | Null]
Step 6: Delete from Middle
[Head | Next] -> ... -> [Data | Next] -> ... -> [Data | Null]
class Node {
int data;
Node next;
Node(int d) { data = d; next = null; }
}
class SinglyLinkedList {
Node head;
// Insert at front
public void insertFront(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Insert at end
public void insertEnd(int new_data) {
Node new_node = new Node(new_data);
if (head == null) {
head = new_node;
return;
}
Node last = head;
while (last.next != null) last = last.next;
last.next = new_node;
}
// Delete a node
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;
}
}
Detailed Explanation:
The above code defines a basic singly linked list with operations to insert at the front and end, and to delete a node by value. The list starts with a head node, and each node points to the next in the list.
Insertion at Front:
To insert a node at the front, create a new node and point it to the current head. Then update the head to be the new node.
Insertion at End:
To insert at the end, traverse the list until the last node is reached, then set its next pointer to the new node.
Deletion:
For deletion, locate the node to be deleted by traversing the list and adjust the pointers to exclude the node from the list.
Console Output:
List after operations: 3 -> 5 -> 10
Conceptual Diagram of Code:
The diagram illustrates the linked list before and after each operation, showing how nodes are added or removed.
