Singly Linked List
A singly linked list is a linear data structure consisting of a sequence of elements, called nodes, where each node points to the next node in the sequence. Unlike arrays, elements in a linked list are not stored in contiguous memory locations. Each node contains two fields:
- Data: The value or information stored in the node.
- Next Pointer: A reference (or pointer) to the next node in the sequence.
The singly linked list forms a linear collection of elements where each node points to its successor, and the last node points to NULL, indicating the end of the list. It is a dynamic data structure, meaning it can grow or shrink in size during runtime, as nodes can be added or removed without requiring memory to be reallocated.
The head is the first node in the list, and it serves as the entry point for traversing the list. If the list is empty, the head points to NULL.
Unlike arrays that have a fixed size, a singly linked list dynamically allocates memory for each node when it is created. This means the size of the list can grow or shrink as nodes are added or removed at runtime.
Insertions and deletions of nodes, particularly at the beginning or middle of the list, are more efficient compared to arrays since you do not need to shift elements.
Singly linked lists can only be traversed in one direction, from the head to the tail. There is no way to traverse backward from the tail to the head, which can be a limitation in some use cases.
The nodes in a singly linked list do not need to be stored in contiguous memory locations, unlike arrays. Each node is linked to the next through pointers, and they can be located anywhere in memory.
The size of the linked list is not fixed, and it is determined by the number of nodes present in the list at any given time. This makes it more flexible for applications where the number of elements is unknown or changes frequently.
Each node in a singly linked list requires extra memory for the pointer (next reference), which slightly increases memory usage compared to arrays.
The last node in a singly linked list is called the tail. Its next pointer is set to NULL, indicating that it is the end of the list.
Here's a visual representation of a singly linked list:
Head -> [Data | Next] -> [Data | Next] -> [Data | NULL]In the above representation:
- The
Headpoints to the first node of the list. - Each node contains
Dataand aNextpointer to the next node. - The last node in the list has its
Nextpointer set toNULL, indicating the end of the list.
A simple singly linked list with three nodes could look like this:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL]In the above example:
- The head points to the first node containing the data
10. - The second node contains the data
20and points to the third node. - The third node contains the data
30and points toNULL, indicating the end of the list.
Here's a detailed breakdown of common singly linked list operations:
insertAtBeginning():
- Description: Inserts a new node at the start (or head) of a singly linked list.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to insert the value
5at the beginning of the list. After callinginsertAtBeginning(), the list becomes:
Head -> [5 | Next] -> [10 | Next] -> [20 | Next] -> [30 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity of inserting a node at the beginning of a singly linked list is \(O(1)\) (constant time). The following steps are performed:
- Create a new node.
- If the list is not empty, set the
nextpointer of the new node to point to the current head node (the first node in the list). If the list is empty, set thenextpointer of the new node to point toNULL. - Update the head pointer to point to the new node.
Since no traversal is required, this operation takes constant time, \(O(1)\). - Space complexity: The space complexity of inserting a node at the beginning of a singly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
insertAtEnd():
- Description: Inserts a new node at the end (or tail) of a singly linked list.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to insert the value
40at the end of the list. After callinginsertAtEnd(), the list becomes:
Head -> [10 | Next] -> [20 | Next] -> [30 | Next] -> [40 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity of inserting a node at the end of a singly linked list is \(O(n)\) (linear time) in the general case.
- Best Case (Empty List): If the list is empty, inserting a new node at the end is the same as inserting at the beginning. The following steps are performed:
- Create a new node.
- Set the
nextpointer of the new nodeNULL, as it will be the only node in the list. - Update the head pointer to point to the new node.
Since no traversal is required, this operation takes constant time, \(O(1)\). - Average/Worst Case (Non-Empty List): If the list is not empty, you have to traverse the entire list to reach the last node. The following steps are performed:
- Start from the head node.
- Traverse the list by following the
nextpointers until you reach the last node (the node whosenextpointer isNULL). - Create a new node.
- Set the
nextpointer of the new node toNULL. - Update the
nextpointer of the last node to point to the new node.
The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\).
- Best Case (Empty List): If the list is empty, inserting a new node at the end is the same as inserting at the beginning. The following steps are performed:
- Space complexity: The space complexity of inserting a node at the end of a singly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
insertAfterNode():
- Description: Inserts a new node in a singly linked list immediately after a given node. If the target node doesn't exist, you may opt to do nothing and just return control to the caller without modifying the list.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to insert the value
25after the node containing20. After callinginsertAfterNode(), the list becomes:
Head -> [10 | Next] -> [20 | Next] -> [25 | Next] -> [30 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity for inserting a node after a node in a singly linked list is \(O(1)\) (constant time). The following steps are performed:
- Create a new node.
- Set the
nextpointer of the new node to point to the node that follows the given node. - Update the
nextpointer of the given node to point to the new node.
Since no traversal is required, this operation takes constant time, \(O(1)\). - Space complexity: The space complexity for inserting a node after a node in a singly linked list is \(O(1)\) (constant time). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
insertBeforeNode():
- Description: Inserts a new node before a given node in a singly linked list. If the target node doesn't exist, you may opt to do nothing and just return control to the caller without modifying the list.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to insert the value
25before the node containing20. After callinginsertBeforeNode(), the list becomes:
Head -> [10 | Next] -> [25 | Next] -> [20 | Next] -> [30 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity for inserting a node before a node in a singly linked list is \(O(n)\) (linear time). The following steps are performed:
- Create a new node.
- Locate the preceding node (the node whose
nextpointer points to the target node). - Update the
nextpointer of the new node to point to the target node. - Update the
nextpointer of the preceding node to point to the new node.
The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\). - Space complexity: The space complexity for inserting a node before a node in a singly linked list is \(O(1)\) (constant time). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
insertAtPosition():
- Description: Inserts a new node at a specified position in a linked list. Positions are usually indexed starting from 0 or 1. If the position is 1 (or 0, based on indexing), this implies insertion at the beginning of the list. If the position is greater than the size of the list or less than 1, the function may return an error or take no action since the insertion would be out of range.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to insert a new node with value
35at position3. After callinginsertAtPosition(), the list becomes:
Head -> [10 | Next] -> [20 | Next] -> [35 | NULL] -> [30 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity for inserting a new node at a specified position in a singly linked list is \(O(n)\) (linear time). The following steps are performed:
- Create a new node.
- Locate the preceding node (the node whose
nextpointer points to the target node). - Update the
nextpointer of the new node to point to the target node. - Update the
nextpointer of the preceding node to point to the new node.
The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\). - Space complexity: The space complexity of inserting a new node at a specified position in a linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
deleteAtBeginning():
- Description: Removes a node at the start (or head) of a singly linked list. If the list is empty, it prints a message "List is empty" and returns, since there is no node to delete.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to delete the value
10at the beginning of the list. After callingdeleteAtBeginning(), the list becomes:
Head -> [20 | Next] -> [30 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity for removing a node at the beginning of a singly linked list is \(O(1)\) (constant time). The following steps are performed:
- Set the head pointer to the next node
- Deallocate the memory for the old head node.
Since no traversal is required, this operation takes constant time, \(O(1)\). - Space complexity: The space complexity for removing a node at the beginning of a singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
deleteAtEnd():
- Description: Removes a node at the end (or tail) of a singly linked list. If the list is empty, it prints a message "List is empty" and returns, since there is no node to delete.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to remove the value
30at the end of the list. After callingdeleteAtEnd(), the list becomes:
Head -> [10 | Next] -> [20 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity for removing a node at the end of a singly linked list is \(O(n)\) (linear time). The following steps are performed:
- Start at the head node.
- Traverse until reaching the second-to-last node.
- Update the
nextpointer of the second-to-last node tonull. - Deallocate the memory for the old last node.
- Space complexity: The space complexity for removing a node at the end of a singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
deleteAtPosition():
- Description: Removes a node at a specified position in a linked list. Positions are usually indexed starting from 0 or 1. If the position to delete is 0, it means the head node should be removed. If the specified position is out of bounds, and a message is printed.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - You want to remove a node at position
3. After callingdeleteAtPosition(), the list becomes:
Head -> [10 | Next] -> [20 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity for removing a node at a specified position in a singly linked list is \(O(n)\) (linear time). The following steps are performed:
- Start at the head node.
- Traverse until reaching the node before the target position.
- Update the
nextpointer of the preceding node to point to the node after the target node. - Deallocate the memory for the removed node.
- Space complexity: The space complexity for removing a node at a specified position in a singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
traverse():
- Description: Visits each node in a singly linked list and perform an action, such as printing the node's value.
- Time complexity: The time complexity of traverse function in a linked list is \(O(n)\) (linear time). The function iterates through each node in the linked list exactly once, from the head to the end (
NULL). Thus, the number of operations performed is directly proportional to the number of nodes. - Space complexity: The space complexity of traverse function in a linked list is \(O(1)\) (constant space). The function only uses a constant amount of space to store variables such as the current node reference during the traversal. Regardless of the size of the linked list, the amount of extra space used does not change.
reverse():
- Description: Reverses the order of nodes in a singly linked list.
- Example:
- Suppose you have the following linked list:
Head -> [10 | Next] -> [20 | Next] -> [30 | NULL] - After calling
reverse(), the list becomes:
Head -> [30 | Next] -> [20 | Next] -> [10 | NULL]
- Suppose you have the following linked list:
- Time complexity: The time complexity of reverse function in a linked list is \(O(n)\) (linear time). The function traverses each node of the linked list exactly once. Thus, the number of operations performed is directly proportional to the number of nodes.
- Space complexity: The space complexity of reverse function in a linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space for variables, such as pointers for the current, previous, and next nodes. This amount of space does not depend on the size of the linked list.
search():
- Description: Finds whether a specific element (or key) exists in a singly linked list.
- Time complexity: The time complexity of search function in a singly linked list is \(O(n)\) (linear time).The search function traverses the linked list node by node. In the worst case, it may need to look at every node in the list to find the key (or determine that it is not present).
- Space complexity: The space complexity of search function in a singly linked list is \(O(1)\) (constant space). The function uses a constant amount of extra space to store variables, such as pointers for the current node. The space required does not depend on the size of the list because the function does not use any additional data structures or dynamic memory allocations for the search process.
size():
- Description: Calculates and returns the number of nodes in a singly linked list.
- Time complexity: The time complexity of size function in a singly linked list is \(O(n)\) (linear time). The function traverses the entire linked list to count the number of nodes, where \(n\) is the number of nodes in the list.
- Space complexity: The space complexity of size function in a singly linked list is \(O(1)\) (constant space). The function uses a constant amount of space for variables regardless of the size of the linked list.
get():
- Description: Retrieves the value of a node in a singly linked list at a specified index. If the end of the list is reached before finding the specified index, a message is printed indicating that the index is out of range.
- Time complexity: The time complexity of get function in a singly linked list is \(O(n)\) (linear time). The function traverses the linked list until it reaches the specified index. In the worst case, it might have to go through all the nodes if the index is at the end of the list or if the list is very long.
- Space complexity: The space complexity of get function in a singly linked list is \(O(1)\) (constant space). The function only uses a constant amount of space for variables, such as the pointer to the current node and the index being tracked. This space requirement does not depend on the size of the list.
set():
- Description: Updates the value of a node at a specified index in a singly linked list. If the end of the list is reached before finding the specified index, a message is printed indicating that the index is out of range.
- Time complexity: The time complexity of set function in a singly linked list is \(O(n)\) (linear time). The function traverses the linked list until it reaches the specified index. In the worst case, it might have to go through all the nodes if the index is at the end of the list or if the list is very long.
- Space complexity: The space complexity of set function in a singly linked list is \(O(1)\) (constant space). The function only uses a constant amount of space for variables, such as the pointer to the current node and the index being tracked. This space requirement does not depend on the size of the list.
isEmpty():
- Description: Checks whether a singly linked list is empty.
- Time complexity: The time complexity of isEmpty function in a singly linked list is \(O(1)\) (constant time). The
isEmptyfunction checks whether the head pointer of the linked list isNULL. This operation is performed in constant time since it only involves a simple comparison, regardless of the size of the linked list. - Space complexity: The space complexity of isEmpty function in a singly linked list is \(O(1)\) (constant space). The function uses a fixed amount of space to store the result of the comparison (typically a boolean value), regardless of the size of the linked list.
merge():
- Description: Combines two sorted linked lists into a single sorted linked list.
- Time complexity: The time complexity of merge function in a singly linked list is \(O(n + m)\) (linear time). The reason for this complexity is that each node from both lists is visited exactly once. In the worst case, the function will traverse both lists entirely, performing comparisons and linking nodes. Where \(n\) is the number of nodes in the first linked list and \(m\) is the number of nodes in the second linked list.
- Space complexity: The space complexity of merge function in a singly linked list is \(O(n + m)\) (linear space) due to the call stack storing recursive calls. In the worst case, the maximum depth of recursion will be equal to the total number of nodes in both lists combined, leading to \(n + m\) recursive calls.
sort():
- Description: Arranges the elements of a singly linked list, in a specific order (typically ascending or descending).
- Time complexity: The time complexity of sort function in a singly linked list, when using merge sort is \(O(n \log n)\) (linearithmic time) because the algorithm consistently divides the list into halves and requires a linear amount of time \(O(n)\) to merge those halves back together. The logarithmic factor \(\log n\) comes from the number of times the list can be divided in half (depth of recursion).
- Space complexity: The space complexity of sort function in a singly linked list, specifically Merge Sort, is \(O(n)\) (linear space) because it requires additional space for the temporary arrays or linked lists used during the merge process. When merging two halves, the algorithm needs space to hold the merged elements before copying them back to the original array or linked list.
clear():
- Description: Removes all nodes from the list and free up the memory they occupy, effectively making the list empty.
- Time complexity: The time complexity of clear function in a singly linked list is \(O(n)\) (linear time). The function iterates through each node exactly once, freeing its memory. Since it processes all nodes in the list, the time complexity is proportional to the number of nodes.
- Space complexity: The space complexity of clear function in a singly linked list is \(O(1)\) (constant space). The function only requires a fixed amount of extra memory for the iteration, typically for a pointer to traverse the list. No additional memory structures are needed, regardless of the size of the linked list.
Non-Generic Singly Linked List Implementation
Here is the Non-Generic singly linked list implementation in C:
#include <stdio.h>
#include <stdlib.h>
// defines a structure to represent a node in a singly linked list
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** headRef, int data) {
Node* newNode = createNode(data);
newNode->next = *headRef;
*headRef = newNode;
}
// Function to insert a node at the end of the list
void insertAtEnd(Node** headRef, int data) {
Node* newNode = createNode(data);
if (*headRef == NULL) {
*headRef = newNode;
return;
}
Node* temp = *headRef;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to insert a new node after a given previous node
void insertAfterNode(Node* prevNode, int data) {
// Check if the previous node is NULL
if (prevNode == NULL) {
printf("The given previous node cannot be NULL.\n");
return;
}
Node* newNode = createNode(data);
// Insert the new node after the previous node
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// Function to insert a new node before a given next node
void insertBeforeNode(Node** headRef, Node* nextNode, int data) {
if (*headRef == NULL) {
printf("The list cannot be empty\n");
return;
}
if (nextNode == NULL) {
printf("The given next node cannot be NULL\n");
return;
}
Node* newNode = createNode(data);
// If the nextNode is the head node, handle the insertion at beginning
if (*headRef == nextNode) {
newNode->next = *headRef;
*headRef = newNode;
return;
}
// Find the node just before the nextNode
Node* temp = *headRef;
while (temp != NULL && temp->next != nextNode) {
temp = temp->next;
}
if (temp == NULL) {
printf("The given next node is not found in the list\n");
free(newNode);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to insert a node at a specific position (0-based index)
void insertAtPosition(Node** headRef, int data, int position) {
Node* newNode = createNode(data);
// If position is at the beginning
if (position == 0) {
newNode->next = *headRef;
*headRef = newNode;
return;
}
Node* temp = *headRef;
for (int i = 0; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
// If position is greater than the number of nodes
if (temp == NULL) {
printf("Position out of bounds\n");
free(newNode);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to delete a node at the beginning of the list
void deleteAtBeginning(Node** headRef) {
if (*headRef == NULL) {
printf("List is empty\n");
return;
}
Node* temp = *headRef;
*headRef = (*headRef)->next;
free(temp);
}
// Function to delete a node at the end of the list
void deleteAtEnd(Node** headRef) {
if (*headRef == NULL) {
printf("List is empty\n");
return;
}
Node* temp = *headRef;
// If there's only one node in the list
if (temp->next == NULL) {
free(temp);
*headRef = NULL;
return;
}
// Traverse to the second last node
while (temp->next->next != NULL) {
temp = temp->next;
}
// Free the last node
free(temp->next);
temp->next = NULL;
}
// Function to delete a node at a specific position (0-based index)
void deleteAtPosition(Node** headRef, int position) {
if (*headRef == NULL) {
printf("List is empty\n");
return;
}
Node* temp = *headRef;
// If head needs to be removed
if (position == 0) {
*headRef = temp->next; // Change head
free(temp); // Free old head
return;
}
// Find previous node of the node to be deleted
for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
// If position is more than number of nodes
if (temp == NULL || temp->next == NULL) {
printf("Position out of bounds\n");
return;
}
// Node temp->next is the node to be deleted
Node* nextNode = temp->next->next;
free(temp->next); // Free memory
temp->next = nextNode; // Unlink the deleted node from the list
}
// Function to traverse the list and print all elements
void traverse(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Function to search for an element in the list
int search(Node* head, int key) {
Node* temp = head;
while (temp != NULL) {
if (temp->data == key)
return 1; // Key found
temp = temp->next;
}
return 0; // Key not found
}
// Function to reverse the linked list
void reverse(Node** headRef) {
Node *prev = NULL, *current = *headRef, *next = NULL;
while (current != NULL) {
next = current->next; // Store next
current->next = prev; // Reverse current node's pointer
prev = current; // Move pointers one position ahead
current = next;
}
*headRef = prev;
}
// Function to get the size of the linked list
int size(Node* head) {
int size = 0;
Node* temp = head;
while (temp != NULL) {
size++;
temp = temp->next;
}
return size;
}
// Function to check if the list is empty
int isEmpty(Node* head) {
return head == NULL;
}
// Function to access an element at a specific index (0-based)
int get(Node* head, int index) {
int count = 0;
Node* temp = head;
while (temp != NULL) {
if (count == index)
return temp->data;
count++;
temp = temp->next;
}
return -1; // Index out of range
}
// Function to set an element at a specific index (0-based)
void set(Node* head, int index, int newValue) {
Node* current = head;
int count = 0;
// Traverse the list until the specified index
while (current != NULL) {
if (count == index) {
current->data = newValue; // Update the node's value
return; // Exit the function after the update
}
count++;
current = current->next; // Move to the next node
}
printf("Index out of range\n"); // Handle case where index exceeds list length
}
// Function to merge two lists
void merge(Node** headRef, Node* head1, Node* head2) {
if (head1 == NULL) {
//while (head2 != NULL) {
Node* newNode = createNode(head2->data); // Create a new node
*headRef = newNode;
//headRef = &((*headRef)->next);
//head2 = head2->next;
merge(&((*headRef)->next), head1, head2->next);
//}
return;
}
if (head2 == NULL) {
//while (head1 != NULL) {
Node* newNode = createNode(head1->data); // Create a new node
*headRef = newNode;
//headRef = &((*headRef)->next);
//head1 = head1->next;
merge(&((*headRef)->next), head1->next, head2);
//}
return;
}
if (head1->data <= head2->data) {
Node* newNode = createNode(head1->data); // Create a new node
*headRef = newNode;
merge(&((*headRef)->next), head1->next, head2);
} else {
Node* newNode = createNode(head2->data); // Create a new node
*headRef = newNode;
merge(&((*headRef)->next), head1, head2->next);
}
}
// Function to get the middle of the linked list
void middle(Node** mid, Node* head) {
if (head == NULL) return;
Node* slow = head;
Node* fast = head->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*mid = slow; // Update the pointer to the middle node
}
// Function to sort the linked list (using Merge Sort)
void sort(Node** headRef) {
if (*headRef == NULL || (*headRef)->next == NULL)
return;
Node* head = *headRef;
Node* mid = NULL;
middle(&mid, head);
Node* nextToMid = mid->next;
mid->next = NULL;
// Sort the two halves
sort(&head);
sort(&nextToMid);
// Merge the sorted halves
merge(headRef, head, nextToMid);
}
// Function to clear the entire linked list and free memory
void clear(Node** headRef) {
Node* current = *headRef;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*headRef = NULL;
}
// Main function to test the linked list operations
int main() {
Node* list = NULL; // Initialize an empty linked list
// 1. Insert elements at the beginning
insertAtBeginning(&list, 5);
insertAtBeginning(&list, 3);
insertAtBeginning(&list, 1);
printf("List after inserting at the beginning: ");
traverse(list);
// 2. Insert elements at the end
insertAtEnd(&list, 7);
insertAtEnd(&list, 9);
printf("List after inserting at the end: ");
traverse(list);
// 3. Insert element at position 2
insertAtPosition(&list, 4, 2);
printf("List after inserting 4 at position 2: ");
traverse(list);
// 4. Insert element after the second node
Node* secondNode = list->next;
insertAfterNode(secondNode, 6);
printf("List after inserting 6 after the second node: ");
traverse(list);
// 5. Insert element before the node with value 7
Node* temp = list;
while (temp != NULL && temp->data != 7) {
temp = temp->next;
}
insertBeforeNode(&list, temp, 8);
printf("List after inserting 8 before the node with value 7: ");
traverse(list);
// 6. Delete the first node
deleteAtBeginning(&list);
printf("List after deleting the first node: ");
traverse(list);
// 7. Delete the last node
deleteAtEnd(&list);
printf("List after deleting the last node: ");
traverse(list);
// 8. Delete the node at position 2
deleteAtPosition(&list, 2);
printf("List after deleting the node at position 2: ");
traverse(list);
// 9. Check if list is empty
if (isEmpty(list)) {
printf("The list is empty.\n");
} else {
printf("The list is not empty.\n");
}
// 10. Search for an element
int key = 6;
if (search(list, key)) {
printf("Element %d found in the list.\n", key);
} else {
printf("Element %d not found in the list.\n", key);
}
// 11. Reverse the list
reverse(&list);
printf("List after reversing: ");
traverse(list);
// 12. Sort the list
sort(&list);
printf("List after sorting: ");
traverse(list);
// 13. Get the size of the list
printf("Size of the list: %d\n", size(list));
// 14. Access an element at a specific index
int index = 2;
int value = get(list, index);
if (value != -1) {
printf("Element at index %d: %d\n", index, value);
} else {
printf("Index %d is out of range.\n", index);
}
// 15. Set a new value at a specific index
set(list, 2, 10);
printf("List after setting value 10 at index 2: ");
traverse(list);
// 16. Clear the list
clear(&list);
printf("List after clearing: ");
traverse(list);
return 0;
}Here is the Non-Generic singly linked list implementation in C++:
#include <iostream>
using namespace std;
// Node structure for singly linked list
struct Node {
int data;
Node* next;
// Constructor to create a new node
Node(int data) : data(data), next(nullptr) {}
};
// Insert at the beginning
void insertAtBeginning(Node*& head, int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
}
// Insert at the end
void insertAtEnd(Node*& head, int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to insert a new node after a given previous node
void insertAfterNode(Node* prevNode, int data) {
// Check if the previous node is NULL
if (prevNode == nullptr) {
std::cout << "The given previous node cannot be NULL." << std::endl;
return;
}
Node* newNode = new Node(data);
// Insert the new node after the previous node
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// Function to insert a new node before a given next node
void insertBeforeNode(Node*& headRef, Node* nextNode, int data) {
if (headRef == nullptr) {
std::cout << "The list cannot be empty" << std::endl;
return;
}
if (nextNode == nullptr) {
std::cout << "The given next node cannot be NULL" << std::endl;
return;
}
Node* newNode = new Node(data);
// If the nextNode is the head node, handle the insertion at the beginning
if (headRef == nextNode) {
newNode->next = headRef;
headRef = newNode;
return;
}
// Find the node just before the nextNode
Node* temp = headRef;
while (temp != nullptr && temp->next != nextNode) {
temp = temp->next;
}
if (temp == nullptr) {
std::cout << "The given next node is not found in the list" << std::endl;
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Insert at a specific position
void insertAtPosition(Node*& head, int data, int position) {
Node* newNode = new Node(data);
if (position == 0) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
for (int i = 0; i < position - 1 && temp != nullptr; i++) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Position out of bounds\n";
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Delete at the beginning
void deleteAtBeginning(Node*& head) {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
Node* temp = head;
head = head->next;
delete temp;
}
// Delete at the end
void deleteAtEnd(Node*& head) {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node* temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
// Delete at a specific position
void deleteAtPosition(Node*& head, int position) {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
if (position == 0) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
for (int i = 0; i < position - 1 && temp != nullptr; i++) {
temp = temp->next;
}
if (temp == nullptr || temp->next == nullptr) {
cout << "Position out of bounds\n";
return;
}
Node* nextNode = temp->next->next;
delete temp->next;
temp->next = nextNode;
}
// Function to access an element at a specific index (0-based)
int get(Node* head, int index) {
int count = 0;
Node* temp = head;
while (temp != nullptr) {
if (count == index)
return temp->data;
count++;
temp = temp->next;
}
return -1; // Index out of range
}
// Function to set an element at a specific index (0-based)
void set(Node* head, int index, int newValue) {
Node* current = head;
int count = 0;
// Traverse the list until the specified index
while (current != nullptr) {
if (count == index) {
current->data = newValue; // Update the node's value
return; // Exit the function after the update
}
count++;
current = current->next; // Move to the next node
}
cout << "Index out of range\n"; // Handle case where index exceeds list length
}
// Function to check if the list is empty
bool isEmpty(Node* head) {
return head == nullptr;
}
// Traverse the list
void traverse(Node* head) {
Node* temp = head;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL\n";
}
// Search for an element
bool search(Node* head, int key) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == key)
return true;
temp = temp->next;
}
return false;
}
// Reverse the list
void reverse(Node*& head) {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
// Get the size of the list
int size(Node* head) {
int count = 0;
Node* temp = head;
while (temp != nullptr) {
count++;
temp = temp->next;
}
return count;
}
// Merge two sorted lists
void merge(Node*& headRef, Node* head1, Node* head2) {
// Handle base cases for empty lists
if (head1 == nullptr) {
if (head2 != nullptr) {
//std::cout << "head1 is null, adding node from head2 with data: " << head2->data << std::endl;
headRef = new Node(head2->data);
merge(headRef->next, head1, head2->next); // Continue merging head2
}
return;
}
if (head2 == nullptr) {
if (head1 != nullptr) {
//std::cout << "head2 is null, adding node from head1 with data: " << head1->data << std::endl;
headRef = new Node(head1->data);
merge(headRef->next, head1->next, head2); // Continue merging head1
}
return;
}
// Merge the two lists
if (head1->data <= head2->data) {
//std::cout << "Choosing node from head1 with data: " << head1->data << std::endl;
headRef = new Node(head1->data);
merge(headRef->next, head1->next, head2); // Move head1 forward
} else {
//std::cout << "Choosing node from head2 with data: " << head2->data << std::endl;
headRef = new Node(head2->data);
merge(headRef->next, head1, head2->next); // Move head2 forward
}
}
// Find the middle of the list
void middle(Node*& mid, Node* head) {
if (head == nullptr) {
mid = nullptr;
return;
}
Node* slow = head;
Node* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
mid = slow;
}
// Sort the list using merge sort
void sort(Node*& head) {
if (head == nullptr || head->next == nullptr)
return;
Node* mid = nullptr;
middle(mid, head);
Node* nextToMid = mid->next;
mid->next = nullptr;
Node* left = head;
Node* right = nextToMid;
sort(left);
sort(right);
merge(head, left, right);
}
// Clear the list
void clear(Node*& head) {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
int main() {
Node* list = nullptr; // Initialize an empty linked list
// 1. Insert elements at the beginning
insertAtBeginning(list, 5);
insertAtBeginning(list, 3);
insertAtBeginning(list, 1);
std::cout << "List after inserting at the beginning: ";
traverse(list);
// 2. Insert elements at the end
insertAtEnd(list, 7);
insertAtEnd(list, 9);
std::cout << "List after inserting at the end: ";
traverse(list);
// 3. Insert element at position 2
insertAtPosition(list, 4, 2);
std::cout << "List after inserting 4 at position 2: ";
traverse(list);
// 4. Insert element after the second node
Node* secondNode = list->next;
insertAfterNode(secondNode, 6);
std::cout << "List after inserting 6 after the second node: ";
traverse(list);
// 5. Insert element before the node with value 7
Node* temp = list;
while (temp != nullptr && temp->data != 7) {
temp = temp->next;
}
insertBeforeNode(list, temp, 8);
std::cout << "List after inserting 8 before the node with value 7: ";
traverse(list);
// 6. Delete the first node
deleteAtBeginning(list);
std::cout << "List after deleting the first node: ";
traverse(list);
// 7. Delete the last node
deleteAtEnd(list);
std::cout << "List after deleting the last node: ";
traverse(list);
// 8. Delete the node at position 2
deleteAtPosition(list, 2);
std::cout << "List after deleting the node at position 2: ";
traverse(list);
// 9. Check if the list is empty
if (isEmpty(list)) {
cout << "The list is empty." << endl;
} else {
cout << "The list is not empty." << endl;
}
// 10. Search for an element
int key = 6;
if (search(list, key)) {
std::cout << "Element " << key << " found in the list." << std::endl;
} else {
std::cout << "Element " << key << " not found in the list." << std::endl;
}
// 11. Reverse the list
reverse(list);
std::cout << "List after reversing: ";
traverse(list);
// 12. Sort the list
sort(list);
std::cout << "List after sorting: ";
traverse(list);
// 13. Get the size of the list
std::cout << "Size of the list: " << size(list) << std::endl;
// 14. Access an element at a specific index
int index = 2;
int value = get(list, index);
if (value != -1) {
std::cout << "Element at index " << index << ": " << value << std::endl;
} else {
std::cout << "Index " << index << " is out of range." << std::endl;
}
// 15. Set a new value at a specific index
set(list, 2, 10);
std::cout << "List after setting value 10 at index 2: ";
traverse(list);
// 16. Clear the list
clear(list);
std::cout << "List after clearing: ";
traverse(list);
return 0;
}Here is the Non-Generic singly linked list implementation in Java:
public class LinkedList {
// Node structure for singly linked list
static class Node {
int data;
Node next;
// Constructor to create a new node
Node(int data) {
this.data = data;
this.next = null;
}
}
// Insert at the beginning
public static Node insertAtBeginning(Node head, int data) {
Node newNode = new Node(data);
newNode.next = head;
return newNode;
}
// Insert at the end
public static Node insertAtEnd(Node head, int data) {
Node newNode = new Node(data);
if (head == null) {
return newNode;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
return head;
}
// Insert at a specific position
public static Node insertAtPosition(Node head, int data, int position) {
Node newNode = new Node(data);
if (position == 0) {
newNode.next = head;
return newNode;
}
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null) {
System.out.println("Position out of bounds");
return head;
}
newNode.next = temp.next;
temp.next = newNode;
return head;
}
// Insert after a given node
public static void insertAfterNode(Node prevNode, int data) {
if (prevNode == null) {
System.out.println("The given previous node cannot be NULL.");
return;
}
Node newNode = new Node(data);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
// Insert before a given node
public static Node insertBeforeNode(Node head, Node nextNode, int data) {
if (head == null) {
System.out.println("The list cannot be empty");
return head;
}
if (nextNode == null) {
System.out.println("The given next node cannot be NULL");
return head;
}
Node newNode = new Node(data);
if (head == nextNode) {
newNode.next = head;
return newNode;
}
Node temp = head;
while (temp != null && temp.next != nextNode) {
temp = temp.next;
}
if (temp == null) {
System.out.println("The given next node is not found in the list");
return head;
}
newNode.next = temp.next;
temp.next = newNode;
return head;
}
// Delete at the beginning
public static Node deleteAtBeginning(Node head) {
if (head == null) {
System.out.println("List is empty");
return null;
}
return head.next;
}
// Delete at the end
public static Node deleteAtEnd(Node head) {
if (head == null) {
System.out.println("List is empty");
return null;
}
if (head.next == null) {
return null;
}
Node temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
return head;
}
// Delete at a specific position
public static Node deleteAtPosition(Node head, int position) {
if (head == null) {
System.out.println("List is empty");
return null;
}
if (position == 0) {
return head.next;
}
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null || temp.next == null) {
System.out.println("Position out of bounds");
return head;
}
temp.next = temp.next.next;
return head;
}
// Get element at a specific index
public static int get(Node head, int index) {
int count = 0;
Node temp = head;
while (temp != null) {
if (count == index) {
return temp.data;
}
count++;
temp = temp.next;
}
System.out.println("Index out of range");
return -1; // Return -1 if the index is out of range
}
// Set element at a specific index
public static void set(Node head, int index, int newValue) {
int count = 0;
Node temp = head;
while (temp != null) {
if (count == index) {
temp.data = newValue; // Update the value at the index
return;
}
count++;
temp = temp.next;
}
System.out.println("Index out of range");
}
// Traverse the list
public static void traverse(Node head) {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}
// Check if the list is empty
public static boolean isEmpty(Node head) {
return head == null;
}
// Search for an element
public static boolean search(Node head, int key) {
Node temp = head;
while (temp != null) {
if (temp.data == key) {
return true;
}
temp = temp.next;
}
return false;
}
// Reverse the list
public static Node reverse(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Merge two sorted lists
public static Node merge(Node head1, Node head2) {
if (head1 == null) return head2;
if (head2 == null) return head1;
if (head1.data <= head2.data) {
head1.next = merge(head1.next, head2);
return head1;
} else {
head2.next = merge(head1, head2.next);
return head2;
}
}
// Find the middle of the list
public static Node middle(Node head) {
if (head == null) return null;
Node slow = head;
Node fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// Sort the list using merge sort
public static Node sort(Node head) {
if (head == null || head.next == null) return head;
// Find the middle node
Node mid = middle(head);
Node nextToMid = mid.next;
mid.next = null;
// Recursively split and sort both halves
Node left = sort(head);
Node right = sort(nextToMid);
// Merge the sorted halves
return merge(left, right);
}
// Get the size of the list
public static int size(Node head) {
int count = 0;
Node temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
// Clear the entire list
public static Node clear(Node head) {
Node current = head;
while (current != null) {
Node nextNode = current.next; // Save reference to the next node
current.next = null; // Break the link to the next node
current = nextNode; // Move to the next node
}
return null; // Set head to null to indicate the list is empty
}
// Main method to test
public static void main(String[] args) {
Node head = null;
// 1. Insert elements at the beginning
head = insertAtBeginning(head, 5);
head = insertAtBeginning(head, 10);
head = insertAtBeginning(head, 3);
System.out.println("List after inserting at the beginning: ");
traverse(head);
// 2. Insert element at the end
head = insertAtEnd(head, 7);
head = insertAtEnd(head, 2);
System.out.println("List after inserting at the end: ");
traverse(head);
// 3. Insert at a specific position
head = insertAtPosition(head, 4, 2);
System.out.println("List after inserting at position 2: ");
traverse(head);
// 4. Insert after a specific node
insertAfterNode(head.next, 8);
System.out.println("List after inserting 8 after second node: ");
traverse(head);
// 5. Insert before a specific node
head = insertBeforeNode(head, head.next, 12);
System.out.println("List after inserting 12 before second node: ");
traverse(head);
// 6. Delete at the beginning
head = deleteAtBeginning(head);
System.out.println("List after deleting at the beginning: ");
traverse(head);
// 7. Delete at the end
head = deleteAtEnd(head);
System.out.println("List after deleting at the end: ");
traverse(head);
// 8. Delete at a specific position
head = deleteAtPosition(head, 2);
System.out.println("List after deleting at position 2: ");
traverse(head);
// 9. Check if the list is empty
if (isEmpty(head)) {
System.out.println("The list is empty.");
} else {
System.out.println("The list is not empty.");
}
// 10. Search for an element
int key = 7;
if (search(head, key)) {
System.out.println("Element " + key + " found in the list");
} else {
System.out.println("Element " + key + " not found in the list");
}
// 11. Reverse the list
head = reverse(head);
System.out.println("List after reversing: ");
traverse(head);
// 12. Get the size of the list
System.out.println("Size of the list: " + size(head));
// 13. Get element at a specific index
int indexToGet = 2;
int value = get(head, indexToGet);
if (value != -1) {
System.out.println("Element at index " + indexToGet + ": " + value);
}
// 14. Set value at a specific index
int indexToSet = 1;
int newValue = 25;
System.out.println("Setting value at index " + indexToSet + " to " + newValue);
set(head, indexToSet, newValue);
System.out.println("Updated list after set operation:");
traverse(head);
// 15. Sort the list
head = sort(head);
System.out.println("Sorted list:");
traverse(head);
// 16. Clear the list
head = clear(head);
System.out.println("List after clearing: ");
traverse(head);
}
}Here is the Non-Generic singly linked list implementation in C#:
using System;
public class LinkedList
{
// Node structure for singly linked list
public class Node
{
public int Data;
public Node Next;
// Constructor to create a new node
public Node(int data)
{
Data = data;
Next = null;
}
}
// Insert at the beginning
public static Node InsertAtBeginning(Node head, int data)
{
Node newNode = new Node(data)
{
Next = head
};
return newNode;
}
// Insert at the end
public static Node InsertAtEnd(Node head, int data)
{
Node newNode = new Node(data);
if (head == null)
{
return newNode;
}
Node temp = head;
while (temp.Next != null)
{
temp = temp.Next;
}
temp.Next = newNode;
return head;
}
// Insert at a specific position
public static Node InsertAtPosition(Node head, int data, int position)
{
Node newNode = new Node(data);
if (position == 0)
{
newNode.Next = head;
return newNode;
}
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++)
{
temp = temp.Next;
}
if (temp == null)
{
Console.WriteLine("Position out of bounds");
return head;
}
newNode.Next = temp.Next;
temp.Next = newNode;
return head;
}
// Insert after a given node
public static void InsertAfterNode(Node prevNode, int data)
{
if (prevNode == null)
{
Console.WriteLine("The given previous node cannot be null");
return;
}
Node newNode = new Node(data);
newNode.Next = prevNode.Next;
prevNode.Next = newNode;
}
// Insert before a given node
public static Node InsertBeforeNode(Node head, Node nextNode, int data)
{
if (nextNode == null)
{
Console.WriteLine("The given next node cannot be null");
return head;
}
if (head == nextNode)
{
return InsertAtBeginning(head, data);
}
Node temp = head;
while (temp != null && temp.Next != nextNode)
{
temp = temp.Next;
}
if (temp == null)
{
Console.WriteLine("The given next node is not present in the list");
return head;
}
Node newNode = new Node(data);
newNode.Next = nextNode;
temp.Next = newNode;
return head;
}
// Delete at the beginning
public static Node DeleteAtBeginning(Node head)
{
if (head == null)
{
Console.WriteLine("List is empty");
return null;
}
return head.Next;
}
// Delete at the end
public static Node DeleteAtEnd(Node head)
{
if (head == null)
{
Console.WriteLine("List is empty");
return null;
}
if (head.Next == null)
{
return null;
}
Node temp = head;
while (temp.Next.Next != null)
{
temp = temp.Next;
}
temp.Next = null;
return head;
}
// Delete at a specific position
public static Node DeleteAtPosition(Node head, int position)
{
if (head == null)
{
Console.WriteLine("List is empty");
return null;
}
if (position == 0)
{
return head.Next;
}
Node temp = head;
for (int i = 0; i < position - 1 && temp != null; i++)
{
temp = temp.Next;
}
if (temp == null || temp.Next == null)
{
Console.WriteLine("Position out of bounds");
return head;
}
temp.Next = temp.Next.Next;
return head;
}
// Function to access an element at a specific index (0-based)
public static int Get(Node head, int index)
{
int count = 0;
Node temp = head;
while (temp != null)
{
if (count == index)
return temp.Data;
count++;
temp = temp.Next;
}
Console.WriteLine("Index out of range");
return -1; // Index out of range
}
// Function to set an element at a specific index (0-based)
public static void Set(Node head, int index, int newValue)
{
Node current = head;
int count = 0;
// Traverse the list until the specified index
while (current != null)
{
if (count == index)
{
current.Data = newValue; // Update the node's value
return; // Exit the function after the update
}
count++;
current = current.Next; // Move to the next node
}
Console.WriteLine("Index out of range"); // Handle case where index exceeds list length
}
// Check if the list is empty
public static bool IsEmpty(Node head)
{
return head == null;
}
// Traverse the list
public static void Traverse(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.Data + " -> ");
temp = temp.Next;
}
Console.WriteLine("NULL");
}
// Search for an element
public static bool Search(Node head, int key)
{
Node temp = head;
while (temp != null)
{
if (temp.Data == key)
{
return true;
}
temp = temp.Next;
}
return false;
}
// Reverse the list
public static Node Reverse(Node head)
{
Node prev = null;
Node current = head;
Node next = null;
while (current != null)
{
next = current.Next;
current.Next = prev;
prev = current;
current = next;
}
return prev;
}
// Get the size of the list
public static int Size(Node head)
{
int count = 0;
Node temp = head;
while (temp != null)
{
count++;
temp = temp.Next;
}
return count;
}
// Merge two sorted lists
public static Node Merge(Node head1, Node head2)
{
if (head1 == null) return head2;
if (head2 == null) return head1;
if (head1.Data <= head2.Data)
{
head1.Next = Merge(head1.Next, head2);
return head1;
}
else
{
head2.Next = Merge(head1, head2.Next);
return head2;
}
}
// Find the middle of the list
public static Node Middle(Node head)
{
if (head == null) return null;
Node slow = head;
Node fast = head;
while (fast.Next != null && fast.Next.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow;
}
// Sort the list using merge sort
public static Node Sort(Node head)
{
if (head == null || head.Next == null)
return head;
// Find the middle of the list
Node middle = Middle(head);
Node nextToMiddle = middle.Next;
// Split the list into two halves
middle.Next = null;
// Recursively sort the two halves
Node left = Sort(head);
Node right = Sort(nextToMiddle);
// Merge the sorted halves
return Merge(left, right);
}
// Clear the entire list
public static Node Clear(Node head)
{
Node current = head;
while (current != null)
{
Node nextNode = current.Next; // Save reference to the next node
current.Next = null; // Break the link to the next node
current = nextNode; // Move to the next node
}
return null; // Return null to indicate the list is empty
}
// Main method to test
public static void Main(string[] args)
{
Node head = null;
// 1. Insert elements at the beginning
head = InsertAtBeginning(head, 5);
head = InsertAtBeginning(head, 10);
head = InsertAtBeginning(head, 3);
Console.WriteLine("List after inserting at the beginning:");
Traverse(head);
// 2. Insert element at the end
head = InsertAtEnd(head, 7);
head = InsertAtEnd(head, 2);
Console.WriteLine("List after inserting at the end:");
Traverse(head);
// 3. Insert at a specific position
head = InsertAtPosition(head, 4, 2);
Console.WriteLine("List after inserting at position 2:");
Traverse(head);
// 4. Insert after a specific node
InsertAfterNode(head.Next, 8);
Console.WriteLine("List after inserting 8 after second node:");
Traverse(head);
// 5. Insert before a specific node
head = InsertBeforeNode(head, head.Next, 12);
Console.WriteLine("List after inserting 12 before second node:");
Traverse(head);
// 6. Delete at the beginning
head = DeleteAtBeginning(head);
Console.WriteLine("List after deleting at the beginning:");
Traverse(head);
// 7. Delete at the end
head = DeleteAtEnd(head);
Console.WriteLine("List after deleting at the end:");
Traverse(head);
// 8. Delete at a specific position
head = DeleteAtPosition(head, 2);
Console.WriteLine("List after deleting at position 2:");
Traverse(head);
// 9. Check if the list is empty
if (IsEmpty(head))
{
Console.WriteLine("The list is empty.");
}
else
{
Console.WriteLine("The list is not empty.");
}
// 10. Search for an element
int key = 7;
if (Search(head, key))
{
Console.WriteLine($"Element {key} found in the list");
}
else
{
Console.WriteLine($"Element {key} not found in the list");
}
// 11. Reverse the list
head = Reverse(head);
Console.WriteLine("List after reversing:");
Traverse(head);
// 12. Get the size of the list
Console.WriteLine("Size of the list: " + Size(head));
// 13. Get value at a specific index
int indexToGet = 2; // 0-based index
int value = Get(head, indexToGet);
Console.WriteLine($"Value at index {indexToGet}: {value}");
// 14. Set a new value at a specific index
int indexToSet = 2; // 0-based index
int newValue = 99;
Set(head, indexToSet, newValue);
Console.WriteLine($"List after setting index {indexToSet} to {newValue}:");
Traverse(head);
// 15. Sort the list
head = Sort(head);
Console.WriteLine("Sorted list:");
Traverse(head);
// 16. Clear the list
head = Clear(head);
Console.WriteLine("List after clearing:");
Traverse(head);
}
}Generic Singly Linked List Implementation
Here is the Generic singly linked list implementation in C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// StackElement structure to hold data and a toString function pointer
typedef struct {
void* data; // Pointer to hold the actual data
char* toString; // This will be modified to hold the string representation
} StackElement;
// Node structure for singly linked list
typedef struct Node {
StackElement element;
struct Node* next; // Pointer to the next node
} Node;
// Function to create a new node
Node* createNode(StackElement element) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->element = element;
newNode->next = NULL;
return newNode;
}
// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** head, StackElement element) {
Node* newNode = createNode(element);
newNode->next = *head;
*head = newNode;
}
// Function to insert a node at the end of the list (generic)
void insertAtEnd(Node** head, StackElement element) {
Node* newNode = createNode(element);
if (*head == NULL) {
*head = newNode;
return;
}
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to insert a node after a given previous node
void insertAfterNode(Node* prevNode, StackElement element) {
// Check if the previous node is NULL
if (prevNode == NULL) {
printf("The given previous node cannot be NULL\n");
return;
}
// Create the new node with the given StackElement
Node* newNode = createNode(element);
// Insert the new node after prevNode
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// Function to insert a node before a given next node
void insertBeforeNode(Node** head, Node* nextNode, StackElement element) {
// Check if the head is NULL (list is empty)
if (*head == NULL) {
printf("The list cannot be empty\n");
return;
}
// Check if the nextNode is NULL
if (nextNode == NULL) {
printf("The given next node cannot be NULL\n");
return;
}
// Create the new node with the given StackElement
Node* newNode = createNode(element);
// If the nextNode is the head node, handle the insertion at beginning
if (*head == nextNode) {
newNode->next = *head;
*head = newNode;
return;
}
Node* temp = *head;
while (temp != NULL && temp->next != nextNode) {
temp = temp->next;
}
// If temp is NULL, then nextNode is not found in the list
if (temp == NULL) {
printf("The given next node is not found in the list\n");
free(newNode);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to insert a node at a specific position
void insertAtPosition(Node** head, StackElement element, int position) {
Node* newNode = createNode(element);
// If position is at the beginning
if (position == 0) {
newNode->next = *head;
*head = newNode;
return;
}
Node* temp = *head;
for (int i = 0; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}
// If position is greater than the number of nodes
if (temp == NULL) {
printf("Position out of bounds\n");
free(newNode);
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Function to delete a node at the beginning of the list
void deleteAtBeginning(Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
Node* temp = *head; // Temporary pointer to the head node
*head = (*head)->next; // Move the head to the next node
free(temp); // Free the node
}
/// Function to delete a node at the end of the list
void deleteAtEnd(Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
Node* temp = *head;
// If there's only one node in the list
if (temp->next == NULL) {
free(temp); // Free the node
*head = NULL;
return;
}
// Traverse to the second last node
while (temp->next->next != NULL) {
temp = temp->next;
}
free(temp->next); // Free the last node
temp->next = NULL; // Set the second last node's next to NULL
}
// Function to delete a node at a given position
void deleteAtPosition(Node** head, int position) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
Node* temp = *head;
// If head needs to be removed
if (position == 0) {
*head = temp->next; // Change head
free(temp); // Free old head
return;
}
// Find previous node of the node to be deleted
for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}
// If position is more than number of nodes
if (temp == NULL || temp->next == NULL) {
printf("Position out of bounds\n");
return;
}
// Node temp->next is the node to be deleted
Node* nextNode = temp->next->next;
free(temp->next); // Free the node
temp->next = nextNode; // Unlink the deleted node from the list
}
// Function to traverse the list and print all elements
void traverse(Node* head) {
Node* temp = head;
while (temp != NULL) {
char* str = temp->element.toString;
printf("%s -> ", str);
temp = temp->next;
}
printf("NULL\n");
}
// Function to search for an element in the list
int search(Node* head, StackElement keyElement) {
Node* temp = head;
while (temp != NULL) {
// Call toString to get the string representation of the data in the current node
char* currentStr = temp->element.toString;
char* keyStr = keyElement.toString;
// Compare the string representations of the current node's data and the key element's data
if (strcmp(currentStr, keyStr) == 0) {
return 1; // Key found
}
temp = temp->next;
}
return 0; // Key not found
}
// Function to reverse the linked list
void reverse(Node** head) {
Node *prev = NULL, *current = *head, *next = NULL;
while (current != NULL) {
next = current->next; // Store next
current->next = prev; // Reverse current node's pointer
prev = current; // Move pointers one position ahead
current = next;
}
*head = prev;
}
// Function to get the size of the linked list
int size(Node* head) {
int size = 0;
Node* temp = head;
while (temp != NULL) {
size++;
temp = temp->next;
}
return size;
}
// Function to check if the list is empty
int isEmpty(Node* head) {
return head == NULL;
}
// Function to access an element at a specific index (0-based)
StackElement get(Node* head, int index) {
int count = 0;
Node* temp = head;
while (temp != NULL) {
if (count == index)
return temp->element;
count++;
temp = temp->next;
}
StackElement emptyElement = {NULL, ""};
return emptyElement; // Index out of range
}
// Function to set an element at a specific index (0-based)
void set(Node* head, int index, StackElement element) {
Node* current = head;
int count = 0;
// Traverse the list until the specified index
while (current != NULL) {
if (count == index) {
current->element = element; // Update the node's value
return; // Exit the function after the update
}
count++;
current = current->next; // Move to the next node
}
printf("Index out of range\n"); // Handle case where index exceeds list length
}
// Function to merge two lists
void merge(Node** headRef, Node* head1, Node* head2) {
if (head1 == NULL) {
while (head2 != NULL) {
Node* newNode = createNode(head2->element); // Create a new node
*headRef = newNode;
headRef = &((*headRef)->next);
head2 = head2->next;
}
return;
}
if (head2 == NULL) {
while (head1 != NULL) {
Node* newNode = createNode(head1->element); // Create a new node
*headRef = newNode;
headRef = &((*headRef)->next);
head1 = head1->next;
}
return;
}
if (strcmp(head1->element.toString, head2->element.toString) < 0) {
Node* newNode = createNode(head1->element); // Create a new node
*headRef = newNode;
merge(&((*headRef)->next), head1->next, head2);
} else {
Node* newNode = createNode(head2->element); // Create a new node
*headRef = newNode;
merge(&((*headRef)->next), head1, head2->next);
}
}
// Function to get the middle of the linked list
void middle(Node* head, Node** middle) {
if (head == NULL) {
*middle = NULL; // Set middle node to NULL if list is empty
return;
}
Node* slow = head;
Node* fast = head->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*middle = slow; // Update the middle node
}
// Function to sort the linked list (using Merge Sort)
void sort(Node** headRef) {
if (*headRef == NULL || (*headRef)->next == NULL)
return;
Node* head = *headRef;
Node* mid = NULL;
middle(head, &mid);
Node* nextToMid = mid->next;
mid->next = NULL;
// Sort the two halves
sort(&head);
sort(&nextToMid);
// Merge the sorted halves
merge(headRef, head, nextToMid);
}
// Function to clear the entire linked list and free memory
void clear(Node** head) {
Node* current = *head;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*head = NULL;
}
struct Person {
char name[20];
int age;
};
// Main function to test the linked list operations
int main() {
// Create People
struct Person alice = {"Alice", 30};
struct Person john = {"John", 19};
struct Person albert = {"Albert", 28};
struct Person robert = {"Robert", 20};
// Create StackElement for people
StackElement personElement1 = {&alice, "Person{name:\"Alice\", age:30}"};
StackElement personElement2 = {&john, "Person{name:\"John\", age:19}"};
StackElement personElement3 = {&albert, "Person{name:\"Albert\", age:28}"};
StackElement personElement4 = {&robert, "Person{name:\"Robert\", age:20}"};
// Initialize Linked List
Node* personList = NULL;
// 1. **Insert elements at the beginning**
insertAtBeginning(&personList, personElement1);
insertAtBeginning(&personList, personElement2);
// 2. **Insert elements at the beginning**
insertAtEnd(&personList, personElement3);
insertAtEnd(&personList, personElement4);
printf("\nList after inserting elements:\n");
traverse(personList);
// 3. **Insert at a specific position**
StackElement newElement = {&alice, "Person{name:\"Eve\", age:22}"};
insertAtPosition(&personList, newElement, 2);
printf("\nList after inserting at position 2:\n");
traverse(personList);
// 4. **Insert before a node**
insertBeforeNode(&personList, personList->next, newElement);
printf("\nList after inserting before second node:\n");
traverse(personList);
// 5. **Insert after a node**
insertAfterNode(personList->next, newElement);
printf("\nList after inserting after second node:\n");
traverse(personList);
// 6. **Delete the first node**
deleteAtBeginning(&personList);
printf("\nList after deleting first node:\n");
traverse(personList);
// 7. **Delete the last node**
deleteAtEnd(&personList);
printf("\nList after deleting last node:\n");
traverse(personList);
// 8. **Delete at a specific position**
deleteAtPosition(&personList, 1);
printf("\nList after deleting node at position 1:\n");
traverse(personList);
// 9. **Search for an element**
int found = search(personList, personElement3);
printf("\nSearch result for 'Albert': %s\n", found ? "Found" : "Not Found");
// 10. **Get size of list**
printf("\nSize of the list: %d\n", size(personList));
// 11. **Check if list is empty**
printf("\nIs the list empty? %s\n", isEmpty(personList) ? "Yes" : "No");
// 12. **Access an element by index**
StackElement retrievedElement = get(personList, 1);
printf("\nElement at index 1: %s\n", retrievedElement.toString);
// 13. **Modify an element at an index**
StackElement modifiedElement = {&john, "Person{name:\"Updated John\", age:25}"};
set(personList, 1, modifiedElement);
printf("\nList after updating element at index 1:\n");
traverse(personList);
// 14. **Sort the linked list**
printf("\nList before sorting:\n");
traverse(personList);
sort(&personList);
printf("\nList after sorting:\n");
traverse(personList);
// 15. **Reverse the linked list**
reverse(&personList);
printf("\nList after reversing:\n");
traverse(personList);
// 16. **Clear the list**
clear(&personList);
printf("\nList after clearing:\n");
traverse(personList);
return 0;
}Here is the Generic singly linked list implementation in C++:
#include <iostream>
#include <string>
using namespace std;
// Node structure for singly linked list template
template <typename T>
struct Node {
T data;
Node* next;
// Constructor to create a new node
Node(T data) : data(data), next(nullptr) {}
};
// Insert at the beginning
template <typename T>
void insertAtBeginning(Node<T>*& head, T data) {
Node<T>* newNode = new Node<T>(data);
newNode->next = head;
head = newNode;
}
// Insert at the end
template <typename T>
void insertAtEnd(Node<T>*& head, T data) {
Node<T>* newNode = new Node<T>(data);
if (head == nullptr) {
head = newNode;
return;
}
Node<T>* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// Function to insert a node after a given previous node
template <typename T>
void insertAfterNode(Node<T>* prevNode, T element) {
if (prevNode == nullptr) {
cout << "The given previous node cannot be NULL\n";
return;
}
Node<T>* newNode = new Node<T>(element);
newNode->next = prevNode->next;
prevNode->next = newNode;
}
// Function to insert a node before a given next node
template <typename T>
void insertBeforeNode(Node<T>*& head, Node<T>* nextNode, T element) {
if (head == nullptr) {
cout << "The list cannot be empty\n";
return;
}
if (nextNode == nullptr) {
cout << "The given next node cannot be NULL\n";
return;
}
Node<T>* newNode = new Node<T>(element);
if (head == nextNode) {
newNode->next = head;
head = newNode;
return;
}
Node<T>* temp = head;
while (temp != nullptr && temp->next != nextNode) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "The given next node is not found in the list\n";
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Insert at a specific position
template <typename T>
void insertAtPosition(Node<T>*& head, T data, int position) {
Node<T>* newNode = new Node<T>(data);
if (position == 0) {
newNode->next = head;
head = newNode;
return;
}
Node<T>* temp = head;
for (int i = 0; i < position - 1 && temp != nullptr; i++) {
temp = temp->next;
}
if (temp == nullptr) {
cout << "Position out of bounds\n";
delete newNode;
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
// Delete at the beginning
template <typename T>
void deleteAtBeginning(Node<T>*& head) {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
Node<T>* temp = head;
head = head->next;
delete temp;
}
// Delete at the end
template <typename T>
void deleteAtEnd(Node<T>*& head) {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node<T>* temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
// Delete at a specific position
template <typename T>
void deleteAtPosition(Node<T>*& head, int position) {
if (head == nullptr) {
cout << "List is empty\n";
return;
}
if (position == 0) {
Node<T>* temp = head;
head = head->next;
delete temp;
return;
}
Node<T>* temp = head;
for (int i = 0; i < position - 1 && temp != nullptr; i++) {
temp = temp->next;
}
if (temp == nullptr || temp->next == nullptr) {
cout << "Position out of bounds\n";
return;
}
Node<T>* nextNode = temp->next->next;
delete temp->next;
temp->next = nextNode;
}
// Traverse the list
template <typename T>
void traverse(Node<T>* head) {
Node<T>* temp = head;
while (temp != nullptr) {
cout << (temp->data).toString() << " -> "; // Using toString()
temp = temp->next;
}
cout << "NULL\n";
}
// Search for an element
template <typename T>
bool search(Node<T>* head, T key) {
Node<T>* temp = head;
while (temp != nullptr) {
if (temp->data == key)
return true;
temp = temp->next;
}
return false;
}
// Reverse the list
template <typename T>
void reverse(Node<T>*& head) {
Node<T>* prev = nullptr;
Node<T>* current = head;
Node<T>* next = nullptr;
while (current != nullptr) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
}
// Get the size of the list
template <typename T>
int size(Node<T>* head) {
int count = 0;
Node<T>* temp = head;
while (temp != nullptr) {
count++;
temp = temp->next;
}
return count;
}
// Function to access an element at a specific index (0-based)
template <typename T>
T get(Node<T>* head, int index) {
int count = 0;
Node<T>* temp = head;
while (temp != nullptr) {
if (count == index)
return temp->data; // Return the data at the index
count++;
temp = temp->next;
}
throw out_of_range("Index out of range"); // Throw exception if index is invalid
}
// Function to set an element at a specific index (0-based)
template <typename T>
void set(Node<T>* head, int index, T element) {
Node<T>* current = head;
int count = 0;
// Traverse the list until the specified index
while (current != nullptr) {
if (count == index) {
current->data = element; // Update the node's value
return; // Exit the function after the update
}
count++;
current = current->next; // Move to the next node
}
throw out_of_range("Index out of range"); // Throw exception if index is invalid
}
// Function to check if the list is empty
template <typename T>
bool isEmpty(Node<T>* head) {
return head == nullptr;
}
// Function to merge two lists
template <typename T>
void merge(Node<T>*& headRef, Node<T>* head1, Node<T>* head2) {
// Handle base cases for empty lists
if (head1 == nullptr) {
headRef = head2;
return;
}
if (head2 == nullptr) {
headRef = head1;
return;
}
// Merge the two lists based on data comparison (using < operator)
if (head1->data < head2->data) {
headRef = head1;
merge(headRef->next, head1->next, head2);
} else {
headRef = head2;
merge(headRef->next, head1, head2->next);
}
}
// Function to find the middle node of the linked list
template <typename T>
void middle(Node<T>* head, Node<T>*& mid) {
if (head == nullptr) {
mid = nullptr; // Set middle node to nullptr if the list is empty
return;
}
Node<T>* slow = head;
Node<T>* fast = head->next;
while (fast != nullptr) {
fast = fast->next;
if (fast != nullptr) {
slow = slow->next;
fast = fast->next;
}
}
mid = slow; // Update the middle node
}
// Function to sort the linked list (using Merge Sort)
template <typename T>
void sort(Node<T>*& headRef) {
if (headRef == nullptr || headRef->next == nullptr)
return;
Node<T>* mid = nullptr;
middle(headRef, mid);
Node<T>* nextToMid = mid->next;
mid->next = nullptr;
// Sort the two halves
sort(headRef);
sort(nextToMid);
// Merge the sorted halves
Node<T>* mergedHead = nullptr;
merge(mergedHead, headRef, nextToMid);
headRef = mergedHead; // Update the original head reference
}
// Clear the list
template <typename T>
void clear(Node<T>*& head) {
Node<T>* current = head;
while (current != nullptr) {
Node<T>* next = current->next;
delete current;
current = next;
}
head = nullptr;
}
// Person class to demonstrate
class Person {
public:
string name;
int age;
Person(string name, int age) : name(name), age(age) {}
// Define < operator for sorting purposes (sort by name, then by age)
bool operator<(const Person& other) const {
if (name == other.name) {
return age < other.age; // If names are the same, sort by age
}
return name < other.name; // Otherwise, sort by name
}
// Overload the equality operator to compare Person objects
bool operator==(const Person& other) const {
return name == other.name && age == other.age;
}
string toString() const {
return "Person{name: " + name + ", age: " + to_string(age) + "}";
}
};
// Testing the Person class with merge
int main() {
// Create Person objects
Person alice("Alice", 30);
Person john("John", 19);
Person albert("Albert", 28);
Person robert("Robert", 20);
// Initialize the linked list
Node<Person>* head = nullptr;
// 1. Insert elements at the beginning
insertAtBeginning(head, alice);
insertAtBeginning(head, john);
// 2. Insert elements at the beginning
insertAtEnd(head, albert);
insertAtEnd(head, robert);
cout << "\nList after inserting elements:\n";
traverse(head);
// 3. Insert at a specific position
Person eve("Eve", 22);
insertAtPosition(head, eve, 2);
cout << "\nList after inserting at position 2:\n";
traverse(head);
// 4. Insert before a node (insert before the second node)
Node<Person>* secondNode = head->next; // Find the second node
Person george("George", 32);
insertBeforeNode(head, secondNode, george);
cout << "\nList after inserting before second node:\n";
traverse(head);
// 5. Insert after a node (insert after the second node)
Person joyce("Joyce", 27);
insertAfterNode(secondNode, joyce); // Insert after the second node
cout << "\nList after inserting after second node:\n";
traverse(head);
// 6. Delete the first node
deleteAtBeginning(head);
cout << "\nList after deleting first node:\n";
traverse(head);
// 7. Delete the last node
deleteAtEnd(head);
cout << "\nList after deleting last node:\n";
traverse(head);
// 8. Delete at a specific position
deleteAtPosition(head, 2);
cout << "\nList after deleting node at position 2:\n";
traverse(head);
// 9. Search for an element
bool found = search(head, albert);
cout << "\nSearch result for 'Albert': " << (found ? "Found" : "Not Found") << endl;
// 10. Get size of the list
cout << "\nSize of the list: " << size(head) << endl;
// 11. Check if list is empty
if (isEmpty(head)) {
cout << "The linked list is empty.\n";
} else {
cout << "The linked list is not empty.\n";
}
// 12. Get an element
try {
Person p = get(head, 2);
cout << "\nElement at index 2: " << p.toString() << endl;
} catch (const exception& e) {
cout << e.what() << endl;
}
// 13. Set (modify) an element
try {
Person updatedJohn("John", 25);
set(head, 1, updatedJohn);
cout << "\nList after modifying index 1:\n";
traverse(head);
} catch (const exception& e) {
cout << e.what() << endl;
}
// 14. Sort the linked list (by name first, then by age)
sort(head);
cout << "\nList after sorting:" << endl;
traverse(head);
// 15. Reverse the list
reverse(head);
cout << "\nReversed List:" << endl;
traverse(head);
// 16. Clear the list
clear(head);
cout << "\nList after clearing:" << endl;
traverse(head); // Should print NULL, as the list is cleared
return 0;
}Here is the Generic singly linked list implementation in Java:
class LinkedList<T> {
// Node structure for singly linked list
static class Node<T> {
T data;
Node<T> next;
// Constructor to create a new node
Node(T data) {
this.data = data;
this.next = null;
}
}
// Insert at the beginning
public static <T> Node<T> insertAtBeginning(Node<T> head, T data) {
Node<T> newNode = new Node<>(data);
newNode.next = head;
return newNode;
}
// Insert at the end
public static <T> Node<T> insertAtEnd(Node<T> head, T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
return newNode;
}
Node<T> temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
return head;
}
// Insert at a specific position
public static <T> Node<T> insertAtPosition(Node<T> head, T data, int position) {
Node<T> newNode = new Node<>(data);
if (position == 0) {
newNode.next = head;
return newNode;
}
Node<T> temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null) {
System.out.println("Position out of bounds");
return head;
}
newNode.next = temp.next;
temp.next = newNode;
return head;
}
// Insert before a specific node
public static <T> Node<T> insertBeforeNode(Node<T> head, Node<T> targetNode, T data) {
if (head == null) return null;
if (head == targetNode) {
return insertAtBeginning(head, data);
}
Node<T> temp = head;
while (temp != null && temp.next != targetNode) {
temp = temp.next;
}
if (temp != null) {
Node<T> newNode = new Node<>(data);
newNode.next = temp.next;
temp.next = newNode;
}
return head;
}
// Insert after a specific node
public static <T> void insertAfterNode(Node<T> node, T data) {
if (node == null) return;
Node<T> newNode = new Node<>(data);
newNode.next = node.next;
node.next = newNode;
}
// Delete at the beginning
public static <T> Node<T> deleteAtBeginning(Node<T> head) {
if (head == null) {
System.out.println("List is empty");
return null;
}
return head.next;
}
// Delete at the end
public static <T> Node<T> deleteAtEnd(Node<T> head) {
if (head == null) {
System.out.println("List is empty");
return null;
}
if (head.next == null) {
return null;
}
Node<T> temp = head;
while (temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
return head;
}
// Delete at a specific position
public static <T> Node<T> deleteAtPosition(Node<T> head, int position) {
if (head == null) {
System.out.println("List is empty");
return null;
}
if (position == 0) {
return head.next;
}
Node<T> temp = head;
for (int i = 0; i < position - 1 && temp.next != null; i++) {
temp = temp.next;
}
if (temp.next == null) {
System.out.println("Position out of bounds");
return head;
}
temp.next = temp.next.next;
return head;
}
// check if the list is empty
public static <T> boolean isEmpty(Node<T> head) {
return head == null;
}
// Search for an element
public static <T> boolean search(Node<T> head, T key) {
Node<T> temp = head;
while (temp != null) {
if (temp.data.equals(key)) {
return true;
}
temp = temp.next;
}
return false;
}
// Get the size of the list
public static <T> int size(Node<T> head) {
int count = 0;
Node<T> temp = head;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
// Get element at a specific index
public static <T> T get(Node<T> head, int index) throws Exception {
int count = 0;
Node<T> temp = head;
while (temp != null) {
if (count == index) {
return temp.data;
}
count++;
temp = temp.next;
}
throw new Exception("Index out of range");
}
// Set element at a specific index
public static <T> void set(Node<T> head, int index, T newValue) throws Exception {
int count = 0;
Node<T> temp = head;
while (temp != null) {
if (count == index) {
temp.data = newValue; // Update the value at the index
return;
}
count++;
temp = temp.next;
}
throw new Exception("Index out of range");
}
// Traverse the list
public static <T> void traverse(Node<T> head) {
Node<T> temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("NULL");
}
// reverse the list
public static <T> Node<T> reverse(Node<T> head) {
Node<T> prev = null;
Node<T> current = head;
Node<T> next = null;
while (current != null) {
next = current.next; // Store next node
current.next = prev; // Reverse current node's pointer
prev = current; // Move prev forward
current = next; // Move current forward
}
return prev; // New head of the reversed list
}
// Sort the list (by name first, then by age)
public static <T extends Comparable<T>> Node<T> sort(Node<T> head) {
if (head == null || head.next == null) return head;
Node<T> mid = middle(head);
Node<T> nextToMid = mid.next;
mid.next = null;
Node<T> left = sort(head);
Node<T> right = sort(nextToMid);
return merge(left, right);
}
// Merge two sorted lists
public static <T extends Comparable<T>> Node<T> merge(Node<T> left, Node<T> right) {
if (left == null) return right;
if (right == null) return left;
if (left.data.compareTo(right.data) <= 0) {
left.next = merge(left.next, right);
return left;
} else {
right.next = merge(left, right.next);
return right;
}
}
// Find the middle of the list
public static <T> Node<T> middle(Node<T> head) {
if (head == null) return null;
Node<T> slow = head;
Node<T> fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static <T> Node<T> clear(Node<T> head) {
Node<T> current = head;
while (current != null) { // Traverse the list until we reach the end
Node<T> next = current.next; // Save reference to the next node
current.next = null; // Break the link to the next node
current = next; // Move to the next node
}
return null; // Set the head to null to indicate the list is empty
}
// Person class
static class Person implements Comparable<Person> {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person{name: " + name + ", age: " + age + "}";
}
@Override
public int compareTo(Person other) {
// Compare by name first, then by age
int nameComparison = this.name.compareTo(other.name);
if (nameComparison != 0) {
return nameComparison;
}
return Integer.compare(this.age, other.age);
}
}
public static void main(String[] args) {
// Create Person objects
Person alice = new Person("Alice", 30);
Person john = new Person("John", 19);
Person albert = new Person("Albert", 28);
Person robert = new Person("Robert", 20);
// Initialize the linked list
Node<Person> head = null;
// 1. Insert elements at the beginning
head = insertAtBeginning(head, alice);
head = insertAtBeginning(head, john);
// 2. Insert elements at the end
head = insertAtEnd(head, albert);
head = insertAtEnd(head, robert);
System.out.println("\nList after inserting elements:");
traverse(head);
// 3. Insert at a specific position
Person eve = new Person("Eve", 22);
head = insertAtPosition(head, eve, 2);
System.out.println("\nList after inserting at position 2:");
traverse(head);
// 4. Insert before a node (insert before the second node)
Node<Person> secondNode = head.next; // Find the second node
head = insertBeforeNode(head, secondNode, eve);
System.out.println("\nList after inserting before second node:");
traverse(head);
// 5. Insert after a node (insert after the second node)
insertAfterNode(secondNode, eve); // Insert after the second node
System.out.println("\nList after inserting after second node:");
traverse(head);
// 6. Delete the first node
head = deleteAtBeginning(head);
System.out.println("\nList after deleting first node:");
traverse(head);
// 7. Delete the last node
head = deleteAtEnd(head);
System.out.println("\nList after deleting last node:");
traverse(head);
// 8. Delete at a specific position
head = deleteAtPosition(head, 2);
System.out.println("\nList after deleting node at position 2:");
traverse(head);
// 9. Search for an element
boolean found = search(head, albert);
System.out.println("\nSearch result for 'Albert': " + (found ? "Found" : "Not Found"));
// 10. Get size of the list
System.out.println("\nSize of the list: " + size(head));
// 11. Check if list is empty
if (isEmpty(head)) {
System.out.println("The list is empty.");
} else {
System.out.println("The list is not empty.");
}
// 12. Get an element
try {
Person p = get(head, 2);
System.out.println("\nElement at index 2: " + p.toString());
} catch (Exception e) {
System.out.println(e.getMessage());
}
// 13. Set (modify) an element
try {
Person updatedJohn = new Person("John", 25);
set(head, 1, updatedJohn);
System.out.println("\nList after modifying index 1:");
traverse(head);
} catch (Exception e) {
System.out.println(e.getMessage());
}
// 14. Sort the linked list (by name first, then by age)
head = sort(head);
System.out.println("\nList after sorting:");
traverse(head);
// 15. Reverse the list
head = reverse(head);
System.out.println("\nList after reversing:");
traverse(head);
// 16. Clear the list
head = clear(head);
System.out.println("After clearing the list:");
traverse(head); // This should print "NULL" as the list is now empty
}
}Here is the Generic singly linked list implementation in C#:
using System;
class Node<T>
{
public T Data;
public Node<T> Next;
public Node(T data)
{
Data = data;
Next = null;
}
}
class Program
{
// Insert at beginning
static Node<T> InsertAtBeginning<T>(Node<T> head, T data)
{
Node<T> newNode = new Node<T>(data) { Next = head };
return newNode;
}
// Insert at end
static Node<T> InsertAtEnd<T>(Node<T> head, T data)
{
Node<T> newNode = new Node<T>(data);
if (head == null) return newNode;
Node<T> temp = head;
while (temp.Next != null) temp = temp.Next;
temp.Next = newNode;
return head;
}
// Insert at position
static Node<T> InsertAtPosition<T>(Node<T> head, T data, int position)
{
Node<T> newNode = new Node<T>(data);
if (position == 0) { newNode.Next = head; return newNode; }
Node<T> temp = head;
for (int i = 0; i < position - 1 && temp != null; i++) temp = temp.Next;
if (temp == null) { Console.WriteLine("Position out of bounds"); return head; }
newNode.Next = temp.Next;
temp.Next = newNode;
return head;
}
// Insert before node
static Node<T> InsertBeforeNode<T>(Node<T> head, Node<T> targetNode, T data)
{
if (head == null) return null;
if (head == targetNode) return InsertAtBeginning(head, data);
Node<T> temp = head;
while (temp != null && temp.Next != targetNode) temp = temp.Next;
if (temp != null)
{
Node<T> newNode = new Node<T>(data) { Next = temp.Next };
temp.Next = newNode;
}
return head;
}
// Insert after node
static void InsertAfterNode<T>(Node<T> node, T data)
{
if (node == null) return;
Node<T> newNode = new Node<T>(data) { Next = node.Next };
node.Next = newNode;
}
// Delete at beginning
static Node<T> DeleteAtBeginning<T>(Node<T> head)
{
if (head == null) { Console.WriteLine("List is empty"); return null; }
return head.Next;
}
// Delete at end
static Node<T> DeleteAtEnd<T>(Node<T> head)
{
if (head == null) { Console.WriteLine("List is empty"); return null; }
if (head.Next == null) return null;
Node<T> temp = head;
while (temp.Next.Next != null) temp = temp.Next;
temp.Next = null;
return head;
}
// Delete at a specific position
static Node<T> DeleteAtPosition<T>(Node<T> head, int position)
{
if (head == null)
{
Console.WriteLine("List is empty");
return null;
}
if (position == 0) // Deleting the first node
{
return head.Next;
}
Node<T> temp = head;
for (int i = 0; i < position - 1 && temp != null; i++)
{
temp = temp.Next;
}
if (temp == null || temp.Next == null)
{
Console.WriteLine("Position out of bounds");
return head;
}
temp.Next = temp.Next.Next; // Remove the node at the given position
return head;
}
// Search for an element
static bool Search<T>(Node<T> head, T key)
{
Node<T> temp = head;
while (temp != null)
{
if (temp.Data.Equals(key)) return true;
temp = temp.Next;
}
return false;
}
// Get size of the list
static int Size<T>(Node<T> head)
{
int count = 0;
Node<T> temp = head;
while (temp != null)
{
count++;
temp = temp.Next;
}
return count;
}
// Traverse the list and print elements
static void Traverse<T>(Node<T> head)
{
Node<T> temp = head;
while (temp != null)
{
Console.Write(temp.Data + " -> ");
temp = temp.Next;
}
Console.WriteLine("NULL");
}
// Get an element at specific index
static T Get<T>(Node<T> head, int index)
{
int count = 0;
Node<T> temp = head;
while (temp != null)
{
if (count == index) return temp.Data;
count++;
temp = temp.Next;
}
throw new Exception("Index out of range");
}
// Set (modify) an element at specific index
static void Set<T>(Node<T> head, int index, T newValue)
{
int count = 0;
Node<T> temp = head;
while (temp != null)
{
if (count == index)
{
temp.Data = newValue;
return;
}
count++;
temp = temp.Next;
}
throw new Exception("Index out of range");
}
// Sort the linked list (Merge Sort)
static Node<T> Sort<T>(Node<T> head) where T : IComparable<T>
{
if (head == null || head.Next == null) return head;
// Split the list into two halves
Node<T> mid = Middle(head);
Node<T> nextToMid = mid.Next;
mid.Next = null;
// Recursively sort both halves
Node<T> left = Sort(head);
Node<T> right = Sort(nextToMid);
// Merge the sorted halves
return Merge(left, right);
}
static bool IsEmpty<T>(Node<T> head) {
return head == null;
}
// Reverse the linked list
static Node<T> Reverse<T>(Node<T> head)
{
Node<T> prev = null;
Node<T> current = head;
Node<T> next = null;
while (current != null)
{
next = current.Next; // Store next node
current.Next = prev; // Reverse the current node's pointer
prev = current; // Move prev and current one step forward
current = next;
}
head = prev; // Set the new head to the last node
return head;
}
// Merge two sorted lists
static Node<T> Merge<T>(Node<T> left, Node<T> right) where T : IComparable<T>
{
if (left == null) return right;
if (right == null) return left;
if (left.Data.CompareTo(right.Data) <= 0)
{
left.Next = Merge(left.Next, right);
return left;
}
else
{
right.Next = Merge(left, right.Next);
return right;
}
}
// Find the middle node of the list
static Node<T> Middle<T>(Node<T> head)
{
if (head == null) return null;
Node<T> slow = head, fast = head.Next;
while (fast != null && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow;
}
// Clear the linked list
public static Node<T> Clear<T>(Node<T> head)
{
if (head == null) return null; // If the list is already empty, return null
Node<T> current = head;
while (current != null) // Traverse the list until we reach the end
{
Node<T> next = current.Next; // Save reference to next node
current.Next = null; // Break the link to the next node
current = next; // Move to the next node
}
return null; // Return null to indicate the list is empty
}
static void Main()
{
// Create Person objects
Person alice = new Person("Alice", 30);
Person john = new Person("John", 19);
Person albert = new Person("Albert", 28);
Person robert = new Person("Robert", 20);
// Initialize the linked list
Node<Person> head = null;
// 1. Insert elements at the beginning
head = InsertAtBeginning(head, alice);
head = InsertAtBeginning(head, john);
// 2. Insert elements at the end
head = InsertAtEnd(head, albert);
head = InsertAtEnd(head, robert);
Console.WriteLine("\nList after inserting elements:");
Traverse(head);
// 3. Insert at a specific position
Person eve = new Person("Eve", 22);
head = InsertAtPosition(head, eve, 2);
Console.WriteLine("\nList after inserting at position 2:");
Traverse(head);
// 4. Insert before a node (insert before the second node)
Node<Person> secondNode = head.Next; // Find the second node
Person jack = new Person("Jack", 29);
head = InsertBeforeNode(head, secondNode, jack);
Console.WriteLine("\nList after inserting before second node:");
Traverse(head);
// 5. Insert after a node (insert after the second node)
InsertAfterNode(secondNode, eve); // Insert after the second node
Console.WriteLine("\nList after inserting after second node:");
Traverse(head);
// 6. Delete the first node
head = DeleteAtBeginning(head);
Console.WriteLine("\nList after deleting first node:");
Traverse(head);
// 7. Delete the last node
head = DeleteAtEnd(head);
Console.WriteLine("\nList after deleting last node:");
Traverse(head);
// 8. Delete node at position 2
head = DeleteAtPosition(head, 2);
Console.WriteLine("\nList after deleting at position 2:");
Traverse(head);
// 9. Search for an element
bool found = Search(head, albert);
Console.WriteLine("\nSearch result for 'Albert': " + (found ? "Found" : "Not Found"));
// 10. Get size of the list
Console.WriteLine("\nSize of the list: " + Size(head));
// 11. Check if the list is empty
if (IsEmpty(head))
{
Console.WriteLine("The list is empty.");
}
else
{
Console.WriteLine("The list is not empty.");
}
// 12. Get an element
try
{
Person p = Get(head, 2);
Console.WriteLine("\nElement at index 2: " + p.ToString());
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
// 13. Set (modify) an element
try
{
Person updatedJohn = new Person("John", 25);
Set(head, 1, updatedJohn);
Console.WriteLine("\nList after modifying index 1:");
Traverse(head);
}
catch (Exception e)
{
Console.WriteLine(e.Message);
}
// 14. Sort the linked list (by name first, then by age)
head = Sort(head);
Console.WriteLine("\nList after sorting:");
Traverse(head);
// 15. Reverse the list
head = Reverse(head);
Console.WriteLine("\nList after reversing:");
Traverse(head);
// 16. Clear the list
head = Clear(head);
Console.WriteLine("\nList after clearing:");
Traverse(head);
}
}
class Person : IComparable<Person>
{
public string Name;
public int Age;
public Person(string name, int age) { Name = name; Age = age; }
public int CompareTo(Person other)
{
// Sort by Name, then Age
return Name.CompareTo(other.Name) != 0 ? Name.CompareTo(other.Name) : Age.CompareTo(other.Age);
}
public override string ToString() => $"Person{{name: {Name}, age: {Age}}}";
}
