A Singly Linked List is a type of linked list in which each element, called a node, contains two fields:

• Data: The value or information stored in the node.
• Pointer (Next): 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 | Next] -> NULL

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 20 and points to the third node.
• The third node contains the data 30 and points to NULL, indicating the end of the list.

The following are some common operations implemented on the singly linked list:

• 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 -> 20 -> 30 -> NULL

    • You want to insert the value 5 at the beginning of the list. After calling insertAtBeginning(), the list becomes:
      

      Head -> 5 -> 10 -> 20 -> 30 -> NULL

  • Time complexity: The time complexity of inserting a node at the beginning of a singly linked list is \(O(1)\) (constant time). This operation is independent of the size of the linked list. Therefore, regardless of whether the list has \(1\) node, \(100\) nodes, or is empty, the time it takes to insert a new node at the beginning is always constant.
  • Space complexity: The space complexity of inserting a node at the beginning of a singly linked list is \(O(1)\) (constant space). The function only requires a fixed amount of extra memory to store the pointer to the new node. It doesn't depend on the size of the list. The new node's space is part of the memory needed for the linked list and is not considered part of the space complexity of the function itself. If we consider the space of the new node, it requires \(O(1)\) additional memory.
• 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 -> 20 -> 30 -> NULL

    • You want to insert the value 40 at the end of the list. After calling insertAtEnd(), the list becomes:
      

      Head -> 10 -> 20 -> 30 -> 40 -> NULL

  • Time complexity: The time complexity of inserting a node at the end of a singly linked list is \(O(n)\) (linear time). This operation has to traverse the entire list to reach the last node (since each node only points to the next one), which takes \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of inserting a node at the end of a singly linked list is \(O(1)\) (constant space). The function only needs a constant amount of extra memory to store the pointer to the new node. This is independent of the size of the list. Allocating space for the new node takes \(O(1)\) (constant space), as only a single node's memory is allocated.
• 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 -> 20 -> 30 -> NULL

    • You want to insert the value 25 after the node containing 20. After calling insertAfterNode(), the list becomes:
      

      Head -> 10 -> 20 -> 25 -> 30 -> NULL

  • Time complexity: The time complexity of inserting a node after a node in a singly linked list is \(O(n)\) (linear time). This operation has to traverse the list to find the node after which the new node will be inserted. In the worst case, it might have to traverse the entire list to find this node, which takes \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of inserting a node after a node in a singly linked list is \(O(1)\) (constant time). The function only needs a constant amount of extra memory for a few local variables. This is independent of the size of the list. Allocating space for the new node takes \(O(1)\) (constant space), as only a single node's memory is allocated.
• insertBeforeNode():
  
  • Description: Inserts a new node in a singly linked list immediately before 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 -> 20 -> 30 -> NULL

    • You want to insert the value 25 before the node containing 20. After calling insertBeforeNode(), the list becomes:
      

      Head -> 10  -> 25 -> 20 -> 30 -> NULL

  • Time complexity: The time complexity of inserting a node before a node in a singly linked list is \(O(n)\) (linear time). This operation has to traverse the list to find the node before which the new node will be inserted. In the worst case, it might have to traverse the entire list to find this node, which takes \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of inserting a node before a node in a singly linked list is \(O(1)\) (constant time). The function only needs a constant amount of extra memory for a few local variables. Allocating space for the new node takes \(O(1)\) (constant space), as only a single node's memory is allocated.
• 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. In this case, the new node's next pointer is assigned to point to the current head, and the head is updated to be the new node. For positions other than the head, the function must traverse the list until it reaches the node before the desired position. This traversal ensures that we place the new node between the current node and the next node at the target position. 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 -> 20 -> 30 -> NULL

    • You want to insert a new node with value 35 at position 3. After calling insertAtPosition(), the list becomes:
      

      Head -> 10 -> 20 -> 35 -> 30 -> NULL

  • Time complexity: The time complexity of inserting a new node at a specified position in a linked list is \(O(n)\) (linear time). This operation has to traverse the list to locate the position which the new node will be inserted. In the worst case, it might have to traverse the entire list to locate the position, which takes \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of inserting a new node at a specified position in a linked list is \(O(1)\) (constant space). The function only needs a constant amount of extra memory for a few local variables. Allocating space for the new node takes \(O(1)\) (constant space), as only a single node's memory is allocated.
• 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, nothing to delete" and returns, since there is no node to delete.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> 10 -> 20 -> 30 -> NULL

    • You want to delete the value 10 at the beginning of the list. After calling deleteAtBeginning(), the list becomes:
      

      Head -> 20 -> 30 -> NULL

  • Time complexity: The time complexity of removing a node at the beginning of a singly linked list is \(O(1)\) (constant time). This operation is independent of the size of the linked list. Therefore, regardless of whether the list has \(1\) node, \(100\) nodes, or is empty, the time it takes to remove a new node at the beginning is always constant.
  • Space complexity: The space complexity of removing a node at the beginning of a singly linked list is \(O(1)\) (constant space). The function only requires a fixed amount of extra memory to store references to the head node and potentially the node to be deleted. It doesn't depend on the size of the list.
• deleteAtEnd():
  
  • Description: Removes a node at the end (or tail) of a singly linked list. If the list is empty, and there are no nodes to delete. In this case, the function will typically print a message indicating that the list is empty and return without making any changes.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> 10 -> 20 -> 30 -> NULL

    • You want to remove the value 30 at the end of the list. After calling deleteAtEnd(), the list becomes:
      

      Head -> 10 -> 20 -> NULL

  • Time complexity: The time complexity of removing a node at the end of a singly linked list is \(O(n)\) (linear time). This operation has to traverse the entire list to reach the last node (since each node only points to the next one), which takes \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of removing a node at the end of a singly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space regardless of the size of the linked list.
• 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. The function updates the head pointer to point to the next node and frees the memory of the old head node. For positions other than the head, the function must traverse the list until it reaches the node before the desired position. If the specified position is out of bounds, and a message is printed.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> 10 -> 20 -> 30 -> NULL

    • You want to remove a node at position 3. After calling deleteAtPosition(), the list becomes:
      

      Head -> 10 -> 20 -> NULL

  • Time complexity: The time complexity of removing a node at a specified position in a linked list is \(O(n)\) (linear time). This operation has to traverse the list to locate the position which the node will be removed. In the worst case, it might have to traverse the entire list to locate the position, which takes \(O(n)\), where \(n\) is the number of nodes in the list.
  • Space complexity: The space complexity of removing a node at a specified position in a 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.
• 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 uses a constant amount of space for variables regardless of the size of the linked list.
• reverse():
  
  • Description: Reverses the order of nodes in a singly linked list.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> 10 -> 20 -> 30 -> NULL

    • After calling reverse(), the list becomes:
      

      Head -> 30 -> 20 -> 10 -> NULL

  • 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 uses a constant amount of space for variables regardless of 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 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 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.
• size():
  
  • Description: Calculates and returns the number of nodes in a singly linked list.
  • Time complexity: The time complexity of size function in a 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 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 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 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.
• 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 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 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.
• isEmpty():
  
  • Description: Checks whether a singly linked list is empty.
  • Time complexity: The time complexity of isEmpty function in a linked list is \(O(1)\) (constant time). The isEmpty function checks whether the head pointer of the linked list is NULL. 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 linked list is \(O(1)\) (constant space). It only utilizes a fixed amount of space to store the return value.
• merge():
  
  • Description: Combines two sorted linked lists into a single sorted linked list.
  • Time complexity: The time complexity of merge function in a 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 linked list is \(O(n + m)\) (linear space). 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 merge function in a linked list 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 merge function in a linked list 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 merge function in a 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 merge function in a linked list is \(O(1)\) (constant space). The function uses only a small, fixed amount of extra memory, regardless of the size of the linked list.

Here's an implementation of a simple singly linked list in C:

#include <stdio.h>
#include <stdlib.h>

// Node structure for 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** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// Function to insert a node at the end of the list
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Function to insert a new node after a given previous node
void insertAfterNode(Node** head, Node* prevNode, int data) {
    // Check if the head is NULL (list is empty)
    if (*head == NULL) {
        printf("The list cannot be empty\n");
        return;
    }

    // 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 data
    Node* newNode = createNode(data);

    // Check if prevNode is the head node
    if (*head == prevNode) {
        // Insert the new node after the head
        newNode->next = (*head)->next;
        (*head)->next = newNode;
        return;
    }

    // Traverse the list to find prevNode if it's not the head
    Node* temp = *head;
    while (temp != NULL && temp != prevNode) {
        temp = temp->next;
    }

    // If prevNode is not found in the list, return an error
    if (temp == NULL) {
        printf("The given previous node is not found in the list\n");
        free(newNode);
        return;
    }

    // Insert the new node after prevNode
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Function to insert a node before a given node
void insertBeforeNode(Node** head, Node* nextNode, int data) {
    if (*head == 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 (*head == nextNode) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    Node* temp = *head;
    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** head, int data, int position) {
    Node* newNode = createNode(data);
    
    // 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;
    *head = (*head)->next;
    free(temp);
}

// 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);
        *head = 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** 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 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** 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)
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
Node* merge(Node* head1, Node* head2) {
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;

    Node* mergedHead = NULL;
    if (head1->data <= head2->data) {
        mergedHead = head1;
        mergedHead->next = merge(head1->next, head2);
    } else {
        mergedHead = head2;
        mergedHead->next = merge(head1, head2->next);
    }
    return mergedHead;
}

// Function to get the middle of the linked list
Node* middle(Node* head) {
    if (head == NULL) return head;
    Node* slow = head;
    Node* fast = head->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    return slow;
}

// Function to sort the linked list (using Merge Sort)
Node* sort(Node* head) {
    if (head == NULL || head->next == NULL)
        return head;

    Node* mid = middle(head);
    Node* nextToMid = mid->next;
    mid->next = NULL;

    Node* left = sort(head);
    Node* right = sort(nextToMid);

    return merge(left, right);
}

// 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;
}

// Main function to test the linked list operations
int main() {
    Node* head = NULL;
    
    // Insert at beginning
    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);
    printf("After inserting at the beginning: ");
    traverse(head);  // Output: 30 -> 20 -> 10 -> NULL

    // Insert at end
    insertAtEnd(&head, 40);
    printf("After inserting at the end: ");
    traverse(head);  // Output: 30 -> 20 -> 10 -> 40 -> NULL

    // Insert at position
    insertAtPosition(&head, 25, 2);  // Insert 25 at position 2
    printf("After inserting at position 2: ");
    traverse(head);  // Output: 30 -> 20 -> 25 -> 10 -> 40 -> NULL

    // Delete at position
    deleteAtPosition(&head, 2);  // Delete node at position 2
    printf("After deleting at position 2: ");
    traverse(head);  // Output: 30 -> 20 -> 10 -> 40 -> NULL

    // Reverse the list
    reverse(&head);
    printf("After reversing the list: ");
    traverse(head);  // Output: 40 -> 10 -> 20 -> 30 -> NULL

    // Search for a value
    int found = search(head, 20);
    printf("Is 20 in the list? %s\n", found ? "Yes" : "No");  // Output: Yes

    // Get size of the list
    printf("Size of the list: %d\n", size(head));  // Output: 4

    // Sort the list
    head = sort(head);
    printf("After sorting the list: ");
    traverse(head);  // Output: 10 -> 20 -> 30 -> 40 -> NULL

    // Clear the list
    clear(&head);
    printf("After clearing the list: ");
    traverse(head);  // Output: NULL

    return 0;
}

Here's an implementation of a generic Singly Linked List 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** head, Node* prevNode, 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 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);

    // Check if prevNode is the head node
    if (*head == prevNode) {
        // Insert the new node after the head
        newNode->next = (*head)->next;
        (*head)->next = newNode;
        return;
    }

    // Traverse the list to find prevNode if it's not the head
    Node* temp = *head;
    while (temp != NULL && temp != prevNode) {
        temp = temp->next;
    }

    // If prevNode is not found in the list, return an error
    if (temp == NULL) {
        printf("The given previous node is not found in the list\n");
        free(newNode);
        return;
    }

    // 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
}

// Comparison function
int compare(const void *arg1, const void *arg2) {
    StackElement *elem1 = (StackElement *)arg1;
    StackElement *elem2 = (StackElement *)arg2;
    return strcasecmp(elem1->toString, elem2->toString);
}

StackElement* linkedListToArray(Node* head, int* length) {
    int count = 0;
    Node* temp = head;

    // Count number of nodes in the list
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }

    // Create an array of StackElements
    StackElement* array = (StackElement*)malloc(count * sizeof(StackElement));
    temp = head;
    for (int i = 0; i < count; i++) {
        array[i] = temp->element;
        temp = temp->next;
    }

    *length = count;
    return array;
}

void arrayToLinkedList(StackElement* array, int length, Node** head) {
    *head = NULL;
    for (int i = 0; i < length; i++) {
        Node* newNode = createNode(array[i]); // Create a new node

        if (*head == NULL) {
            // If the list is empty, make the new node the head
            *head = newNode;
        } else {
            // Traverse to the end of the list and append the new node
            Node* temp = *head;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = newNode; // Link the new node
        }
    }
}


// Function to sort the linked list
Node* sortLinkedList(Node* head) {
    if (head == NULL) {
        return NULL;  // If the list is empty, return NULL
    }

    int length = 0;
    StackElement* array = linkedListToArray(head, &length);
    
    // Sort the array using qsort and the comparison function
    qsort(array, length, sizeof(StackElement), compare);
    
    // Convert the sorted array back to a linked list
    Node* sortedHead = NULL;
    arrayToLinkedList(array, length, &sortedHead);
    
    // Free the array as it's no longer needed
    free(array);

    // Return the new sorted head of the list
    return sortedHead;
}

// Function to merge two lists
Node* merge(Node* a, Node* b) {
    // Combine the two linked lists into one list by linking them
    if (a == NULL) return b;
    if (b == NULL) return a;

    Node* merged = NULL;

    // Merge both lists
    while (a != NULL) {
        insertAtEnd(&merged, a->element);
        a = a->next;
    }

    while (b != NULL) {
        insertAtEnd(&merged, b->element);
        b = b->next;
    }

    return sortLinkedList(merged);
}

// 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 Car {
    char model[20];
    int year;
};

struct Person {
    char name[20];
    int age;
};
// Main function to test the linked list operations
int main() {
    // Create Cars
    struct Car tesla = {"Tesla", 2020};
    struct Car toyota = {"Toyota", 2019};
    struct Car honda = {"Honda", 2020};
    
    // Create StackElement for cars
    StackElement carElement1, carElement2, carElement3;
    carElement1.data = &tesla;
    carElement1.toString = "Car{model:\"Tesla\", year:2020}";
    
    carElement2.data = &toyota;
    carElement2.toString = "Car{model:\"Toyota\", year:2019}";
    
    carElement3.data = &honda;
    carElement3.toString = "Car{model:\"Honda\", year:2020}";
    
    // 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, personElement2, personElement3, personElement4;
    personElement1.data = &alice;
    personElement1.toString = "Person{name:\"Alice\", age:30}";
    
    personElement2.data = &john;
    personElement2.toString = "Person{name:\"John\", age:19}";
    
    personElement3.data = &albert;
    personElement3.toString = "Person{name:\"Albert\", age:28}";
    
    personElement4.data = &robert;
    personElement4.toString = "Person{name:\"Robert\", age:20}";

    // Initialize linked lists for cars and people
    Node* carList = NULL;
    Node* personList = NULL;

    // Insert cars into the car linked list
    insertAtEnd(&carList, carElement1);
    insertAtEnd(&carList, carElement2);
    insertAtEnd(&carList, carElement3);

    // Insert people into the person linked list
    insertAtEnd(&personList, personElement1);
    insertAtEnd(&personList, personElement2);
    insertAtEnd(&personList, personElement3);
    insertAtEnd(&personList, personElement4);

    // Print the original car list
    printf("Original Car List:\n");
    traverse(carList);

    // Print the original person list
    printf("\nOriginal Person List:\n");
    traverse(personList);

    // Merge the two lists and sort the combined list
    Node* mergedList = merge(personList, carList);

    // Print the merged and sorted list
    printf("\nMerged and Sorted List:\n");
    traverse(mergedList);

    // Clean up and free the memory
    clear(&carList);
    clear(&personList);
    clear(&mergedList);

    return 0;
}

Here is an implementation of a simple singly linked list 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) {
        this->data = data;
        this->next = nullptr;
    }
};

// Class to manage linked list operations
class LinkedList {
private:
    Node* head;

public:
    // Constructor to initialize the linked list
    LinkedList() : head(nullptr) {}

    // Function to insert a node at the beginning of the list
    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }

    // Function to insert a node at the end of the list
    void insertAtEnd(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) {
        if (head == nullptr) {
            cout << "The list cannot be empty\n";
            return;
        }

        if (prevNode == nullptr) {
            cout << "The given previous node cannot be NULL\n";
            return;
        }

        Node* newNode = new Node(data);
        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }

    // Function to insert a node before a given node
    void insertBeforeNode(Node* nextNode, int data) {
        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* newNode = new Node(data);
        if (head == nextNode) {
            newNode->next = head;
            head = newNode;
            return;
        }

        Node* 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;
    }

    // Function to insert a node at a specific position (0-based index)
    void insertAtPosition(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;
    }

    // Function to delete a node at the beginning of the list
    void deleteAtBeginning() {
        if (head == nullptr) {
            cout << "List is empty\n";
            return;
        }
        Node* temp = head;
        head = head->next;
        delete temp;
    }

    // Function to delete a node at the end of the list
    void deleteAtEnd() {
        if (head == nullptr) {
            cout << "List is empty\n";
            return;
        }

        Node* temp = head;

        // If there's only one node in the list
        if (temp->next == nullptr) {
            delete temp;
            head = nullptr;
            return;
        }

        // Traverse to the second last node
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }

        // Free the last node
        delete temp->next;
        temp->next = nullptr;
    }

    // Function to delete a node at a specific position (0-based index)
    void deleteAtPosition(int position) {
        if (head == nullptr) {
            cout << "List is empty\n";
            return;
        }

        Node* temp = head;

        // If head needs to be removed
        if (position == 0) {
            head = temp->next; // Change head
            delete temp; // Free old head
            return;
        }

        // Find previous node of the node to be deleted
        for (int i = 0; temp != nullptr && i < position - 1; i++) {
            temp = temp->next;
        }

        // If position is more than the number of nodes
        if (temp == nullptr || temp->next == nullptr) {
            cout << "Position out of bounds\n";
            return;
        }

        // Node temp->next is the node to be deleted
        Node* nextNode = temp->next->next;
        delete 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* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL\n";
    }

    // Function to search for an element in the list
    bool search(int key) {
        Node* temp = head;
        while (temp != nullptr) {
            if (temp->data == key)
                return true; // Key found
            temp = temp->next;
        }
        return false; // Key not found
    }

    // Function to reverse the linked list
    void reverse() {
        Node *prev = nullptr, *current = head, *next = nullptr;
        while (current != nullptr) {
            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() {
        int size = 0;
        Node* temp = head;
        while (temp != nullptr) {
            size++;
            temp = temp->next;
        }
        return size;
    }

    // Function to check if the list is empty
    bool isEmpty() {
        return head == nullptr;
    }

    // Function to access an element at a specific index (0-based)
    int get(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(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 merge two lists
    Node* merge(Node* head1, Node* head2) {
        if (head1 == nullptr) return head2;
        if (head2 == nullptr) return head1;

        Node* mergedHead = nullptr;
        if (head1->data <= head2->data) {
            mergedHead = head1;
            mergedHead->next = merge(head1->next, head2);
        } else {
            mergedHead = head2;
            mergedHead->next = merge(head1, head2->next);
        }
        return mergedHead;
    }

    // Function to get the middle of the linked list
    Node* middle(Node* head) {
        if (head == nullptr) return head;
        Node* slow = head;
        Node* fast = head->next;
        while (fast != nullptr) {
            fast = fast->next;
            if (fast != nullptr) {
                slow = slow->next;
                fast = fast->next;
            }
        }
        return slow;
    }

    // Function to sort the linked list (using Merge Sort)
    Node* sort(Node* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        Node* mid = middle(head);
        Node* nextToMid = mid->next;
        mid->next = nullptr;

        Node* left = sort(head);
        Node* right = sort(nextToMid);

        return merge(left, right);
    }

    // Function to clear the entire linked list and free memory
    void clear() {
        Node* current = head;
        Node* next;

        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }

        head = nullptr;
    }

    // Destructor to free the memory when the linked list is destroyed
    ~LinkedList() {
        clear();
    }
};

// Main function to test the linked list operations
int main() {
    LinkedList list;

    // Insert at beginning
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(30);
    cout << "After inserting at the beginning: ";
    list.traverse();  // Output: 30 -> 20 -> 10 -> NULL

    // Insert at end
    list.insertAtEnd(40);
    cout << "After inserting at the end: ";
    list.traverse();  // Output: 30 -> 20 -> 10 -> 40 -> NULL

    // Insert at position
    list.insertAtPosition(25, 2);  // Insert 25 at position 2
    cout << "After inserting at position 2: ";
    list.traverse();  // Output: 30 -> 20 -> 25 -> 10 -> 40 -> NULL

    // Delete at position
    list.deleteAtPosition(2);  // Delete node at position 2
    cout << "After deleting at position 2: ";
    list.traverse();  // Output: 30 -> 20 -> 10 -> 40 -> NULL

    // Reverse the list
    list.reverse();
    cout << "After reversing the list: ";
    list.traverse();  // Output: 40 -> 10 -> 20 -> 30 -> NULL

    // Search for a value
    bool found = list.search(20);
    cout << "Is 20 in the list? " << (found ? "Yes" : "No") << endl;  // Output: Yes

    // Get size of the list
    cout << "Size of the list: " << list.size() << endl;  // Output: 4

    // Sort the list
    Node* sortedHead = list.sort(list.head);
    list.clear(); // Clear the current list before assigning sorted list
    list.head = sortedHead; // Set the head to the sorted list
    cout << "After sorting the list: ";
    list.traverse();  // Output: 10 -> 20 -> 30 -> 40 -> NULL

    // Clear the list
    list.clear();
    cout << "After clearing the list: ";
    list.traverse();  // Output: NULL

    return 0;
}

Here is an implementation of a generic singly linked list in C++:

#include <iostream>

using namespace std;

// Node structure for singly linked list
template <typename T>
struct Node {
    T data;
    Node* next;

    // Constructor to create a new node
    Node(T data) {
        this->data = data;
        this->next = nullptr;
    }
};

// Class to manage linked list operations
template <typename T>
class LinkedList {
private:
    Node<T>* head;

public:
    // Constructor to initialize the linked list
    LinkedList() : head(nullptr) {}

    // Function to insert a node at the beginning of the list
    void insertAtBeginning(T data) {
        Node<T>* newNode = new Node<T>(data);
        newNode->next = head;
        head = newNode;
    }

    // Function to insert a node at the end of the list
    void insertAtEnd(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 new node after a given previous node
    void insertAfterNode(Node<T>* prevNode, T data) {
        if (head == nullptr) {
            cout << "The list cannot be empty\n";
            return;
        }

        if (prevNode == nullptr) {
            cout << "The given previous node cannot be NULL\n";
            return;
        }

        Node<T>* newNode = new Node<T>(data);
        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }

    // Function to insert a node before a given node
    void insertBeforeNode(Node<T>* nextNode, T data) {
        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>(data);
        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;
    }

    // Function to insert a node at a specific position (0-based index)
    void insertAtPosition(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;
    }

    // Function to delete a node at the beginning of the list
    void deleteAtBeginning() {
        if (head == nullptr) {
            cout << "List is empty\n";
            return;
        }
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    // Function to delete a node at the end of the list
    void deleteAtEnd() {
        if (head == nullptr) {
            cout << "List is empty\n";
            return;
        }

        Node<T>* temp = head;

        // If there's only one node in the list
        if (temp->next == nullptr) {
            delete temp;
            head = nullptr;
            return;
        }

        // Traverse to the second last node
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }

        // Free the last node
        delete temp->next;
        temp->next = nullptr;
    }

    // Function to delete a node at a specific position (0-based index)
    void deleteAtPosition(int position) {
        if (head == nullptr) {
            cout << "List is empty\n";
            return;
        }

        Node<T>* temp = head;

        // If head needs to be removed
        if (position == 0) {
            head = temp->next; // Change head
            delete temp; // Free old head
            return;
        }

        // Find previous node of the node to be deleted
        for (int i = 0; temp != nullptr && i < position - 1; i++) {
            temp = temp->next;
        }

        // If position is more than the number of nodes
        if (temp == nullptr || temp->next == nullptr) {
            cout << "Position out of bounds\n";
            return;
        }

        // Node temp->next is the node to be deleted
        Node<T>* nextNode = temp->next->next;
        delete 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<T>* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL\n";
    }

    // Function to search for an element in the list
    bool search(T key) {
        Node<T>* temp = head;
        while (temp != nullptr) {
            if (temp->data == key)
                return true; // Key found
            temp = temp->next;
        }
        return false; // Key not found
    }

    // Function to reverse the linked list
    void reverse() {
        Node<T>* prev = nullptr;
        Node<T>* current = head;
        Node<T>* next = nullptr;
        while (current != nullptr) {
            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() {
        int size = 0;
        Node<T>* temp = head;
        while (temp != nullptr) {
            size++;
            temp = temp->next;
        }
        return size;
    }

    // Function to check if the list is empty
    bool isEmpty() {
        return head == nullptr;
    }

    // Function to access an element at a specific index (0-based)
    T get(int index) {
        int count = 0;
        Node<T>* temp = head;
        while (temp != nullptr) {
            if (count == index)
                return temp->data;
            count++;
            temp = temp->next;
        }
        throw out_of_range("Index out of range"); // Using exception handling
    }

    // Function to set an element at a specific index (0-based)
    void set(int index, T newValue) {
        Node<T>* 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 merge two lists
    Node<T>* merge(Node<T>* head1, Node<T>* head2) {
        if (head1 == nullptr) return head2;
        if (head2 == nullptr) return head1;

        Node<T>* mergedHead = nullptr;
        if (head1->data <= head2->data) {
            mergedHead = head1;
            mergedHead->next = merge(head1->next, head2);
        } else {
            mergedHead = head2;
            mergedHead->next = merge(head1, head2->next);
        }
        return mergedHead;
    }

    // Function to get the middle of the linked list
    Node<T>* middle(Node<T>* head) {
        if (head == nullptr) return head;
        Node<T>* slow = head;
        Node<T>* fast = head->next;
        while (fast != nullptr) {
            fast = fast->next;
            if (fast != nullptr) {
                slow = slow->next;
                fast = fast->next;
            }
        }
        return slow;
    }

    // Function to sort the linked list (using Merge Sort)
    Node<T>* sort(Node<T>* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        Node<T>* mid = middle(head);
        Node<T>* nextToMid = mid->next;
        mid->next = nullptr;

        Node<T>* left = sort(head);
        Node<T>* right = sort(nextToMid);

        return merge(left, right);
    }

    // Function to clear the entire linked list and free memory
    void clear() {
        Node<T>* current = head;
        Node<T>* next;

        while (current != nullptr) {
            next = current->next;
            delete current;
            current = next;
        }

        head = nullptr;
    }

    // Destructor to free the memory when the linked list is destroyed
    ~LinkedList() {
        clear();
    }
};

// Main function to test the linked list operations
int main() {
    LinkedList<int> list;

    // Insert at beginning
    list.insertAtBeginning(10);
    list.insertAtBeginning(20);
    list.insertAtBeginning(30);
    cout << "After inserting at the beginning: ";
    list.traverse();  // Output: 30 -> 20 -> 10 -> NULL

    // Insert at end
    list.insertAtEnd(40);
    cout << "After inserting at the end: ";
    list.traverse();  // Output: 30 -> 20 -> 10 -> 40 -> NULL

    // Insert at position
    list.insertAtPosition(25, 2);  // Insert 25 at position 2
    cout << "After inserting at position 2: ";
    list.traverse();  // Output: 30 -> 20 -> 25 -> 10 -> 40 -> NULL

    // Delete at position
    list.deleteAtPosition(2);  // Delete node at position 2
    cout << "After deleting at position 2: ";
    list.traverse();  // Output: 30 -> 20 -> 10 -> 40 -> NULL

    // Reverse the list
    list.reverse();
    cout << "After reversing the list: ";
    list.traverse();  // Output: 40 -> 10 -> 20 -> 30 -> NULL

    // Search for a value
    bool found = list.search(20);
    cout << "Is 20 in the list? " << (found ? "Yes" : "No") << endl;  // Output: Yes

    // Get size of the list
    cout << "Size of the list: " << list.size() << endl;  // Output: 4

    // Sort the list
    Node<int>* sortedHead = list.sort(list.head);
    list.clear(); // Clear the current list before assigning sorted list
    list.head = sortedHead; // Set the head to the sorted list
    cout << "After sorting the list: ";
    list.traverse();  // Output: 10 -> 20 -> 30 -> 40 -> NULL

    // Clear the list
    list.clear();
    cout << "After clearing the list: ";
    list.traverse();  // Output: NULL
	
	LinkedList<string> list;

    // Insert at beginning
    list.insertAtBeginning("World");
    list.insertAtBeginning("Hello");
    cout << "After inserting at the beginning: ";
    list.traverse();  // Output: Hello -> World -> NULL

    // Insert at end
    list.insertAtEnd("!");
    cout << "After inserting at the end: ";
    list.traverse();  // Output: Hello -> World -> ! -> NULL

    // Delete at beginning
    list.deleteAtBeginning();
    cout << "After deleting at the beginning: ";
    list.traverse();  // Output: World -> ! -> NULL

    // Clear the list
    list.clear();
    cout << "After clearing the list: ";
    list.traverse();  // Output: NULL
	
    return 0;
}

Here is an implementation of a simple singly linked list in Java:

class Node {
    int data;
    Node next;

    // Constructor to create a new node
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// Class to manage linked list operations
class LinkedList {
    private Node head;

    // Constructor to initialize the linked list
    public LinkedList() {
        head = null;
    }

    // Function to insert a node at the beginning of the list
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Function to insert a node at the end of the list
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Function to insert a new node after a given previous node
    public void insertAfterNode(Node prevNode, int data) {
        if (head == null) {
            System.out.println("The list cannot be empty");
            return;
        }

        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;
    }

    // Function to insert a node before a given node
    public void insertBeforeNode(Node nextNode, int data) {
        if (head == null) {
            System.out.println("The list cannot be empty");
            return;
        }

        if (nextNode == null) {
            System.out.println("The given next node cannot be null");
            return;
        }

        Node newNode = new Node(data);
        if (head == nextNode) {
            newNode.next = head;
            head = newNode;
            return;
        }

        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;
        }

        newNode.next = temp.next;
        temp.next = newNode;
    }

    // Function to insert a node at a specific position (0-based index)
    public void insertAtPosition(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 != null; i++) {
            temp = temp.next;
        }

        if (temp == null) {
            System.out.println("Position out of bounds");
            return;
        }

        newNode.next = temp.next;
        temp.next = newNode;
    }

    // Function to delete a node at the beginning of the list
    public void deleteAtBeginning() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        head = head.next;
        temp = null; // Helps with garbage collection
    }

    // Function to delete a node at the end of the list
    public void deleteAtEnd() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;

        // If there's only one node in the list
        if (temp.next == null) {
            head = null;
            return;
        }

        // Traverse to the second last node
        while (temp.next.next != null) {
            temp = temp.next;
        }

        // Free the last node
        temp.next = null;
    }

    // Function to delete a node at a specific position (0-based index)
    public void deleteAtPosition(int position) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node temp = head;

        // If head needs to be removed
        if (position == 0) {
            head = temp.next; // Change head
            temp = null; // Helps with garbage collection
            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 the number of nodes
        if (temp == null || temp.next == null) {
            System.out.println("Position out of bounds");
            return;
        }

        // Node temp.next is the node to be deleted
        Node nextNode = temp.next.next;
        temp.next = nextNode; // Unlink the deleted node from the list
    }

    // Function to traverse the list and print all elements
    public void traverse() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }

    // Function to search for an element in the list
    public boolean search(int key) {
        Node temp = head;
        while (temp != null) {
            if (temp.data == key)
                return true; // Key found
            temp = temp.next;
        }
        return false; // Key not found
    }

    // Function to reverse the linked list
    public void reverse() {
        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
    public int size() {
        int size = 0;
        Node temp = head;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    // Function to check if the list is empty
    public boolean isEmpty() {
        return head == null;
    }

    // Function to access an element at a specific index (0-based)
    public int get(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)
    public void set(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
        }

        System.out.println("Index out of range"); // Handle case where index exceeds list length
    }

    // Function to merge two lists
    private Node merge(Node head1, Node head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        Node mergedHead;
        if (head1.data <= head2.data) {
            mergedHead = head1;
            mergedHead.next = merge(head1.next, head2);
        } else {
            mergedHead = head2;
            mergedHead.next = merge(head1, head2.next);
        }
        return mergedHead;
    }

    // Function to get the middle of the linked list
    private Node middle(Node head) {
        if (head == null) return head;
        Node slow = head;
        Node fast = head.next;
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return slow;
    }

    // Function to sort the linked list (using Merge Sort)
    public Node sort(Node head) {
        if (head == null || head.next == null)
            return head;

        Node mid = middle(head);
        Node nextToMid = mid.next;
        mid.next = null;

        Node left = sort(head);
        Node right = sort(nextToMid);

        return merge(left, right);
    }

    // Function to clear the entire linked list and free memory
    public void clear() {
        head = null; // Helps with garbage collection
    }

    // Main method to test the linked list operations
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Insert elements
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        System.out.print("After inserting at the end: ");
        list.traverse();  // Output: 10 -> 20 -> 30 -> NULL

        // Insert at the beginning
        list.insertAtBeginning(5);
        System.out.print("After inserting at the beginning: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> NULL

        // Insert at the end
        list.insertAtEnd(40);
        System.out.print("After inserting at the end: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Insert at position
        list.insertAtPosition(25, 3);  // Insert 25 at position 3
        System.out.print("After inserting at position 3: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> NULL

        // Delete at position
        list.deleteAtPosition(3);  // Delete node at position 3
        System.out.print("After deleting at position 3: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Reverse the list
        list.reverse();
        System.out.print("After reversing the list: ");
        list.traverse();  // Output: 40 -> 30 -> 20 -> 10 -> 5 -> NULL

        // Search for a value
        boolean found = list.search(20);
        System.out.println("Is 20 in the list? " + (found ? "Yes" : "No"));  // Output: Yes

        // Get size of the list
        System.out.println("Size of the list: " + list.size());  // Output: 5

        // Sort the list
        Node sortedHead = list.sort(list.head);
        list.clear(); // Clear the current list before assigning sorted list
        list.head = sortedHead; // Set the head to the sorted list
        System.out.print("After sorting the list: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Clear the list
        list.clear();
        System.out.print("After clearing the list: ");
        list.traverse();  // Output: NULL
    }
}

Here is an implementation of a generic singly linked list in Java:

class Node<T> {
    T data;
    Node<T> next;

    // Constructor to create a new node
    Node(T data) {
        this.data = data;
        this.next = null;
    }
}

// Class to manage linked list operations
class LinkedList<T> {
    private Node<T> head;

    // Constructor to initialize the linked list
    public LinkedList() {
        head = null;
    }

    // Function to insert a node at the beginning of the list
    public void insertAtBeginning(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
    }

    // Function to insert a node at the end of the list
    public void insertAtEnd(T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node<T> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Function to insert a new node after a given previous node
    public void insertAfterNode(Node<T> prevNode, T data) {
        if (head == null) {
            System.out.println("The list cannot be empty");
            return;
        }

        if (prevNode == null) {
            System.out.println("The given previous node cannot be null");
            return;
        }

        Node<T> newNode = new Node<>(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
    }

    // Function to insert a node before a given node
    public void insertBeforeNode(Node<T> nextNode, T data) {
        if (head == null) {
            System.out.println("The list cannot be empty");
            return;
        }

        if (nextNode == null) {
            System.out.println("The given next node cannot be null");
            return;
        }

        Node<T> newNode = new Node<>(data);
        if (head == nextNode) {
            newNode.next = head;
            head = newNode;
            return;
        }

        Node<T> 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;
        }

        newNode.next = temp.next;
        temp.next = newNode;
    }

    // Function to insert a node at a specific position (0-based index)
    public void insertAtPosition(T data, int position) {
        Node<T> newNode = new Node<>(data);

        if (position == 0) {
            newNode.next = head;
            head = newNode;
            return;
        }

        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;
        }

        newNode.next = temp.next;
        temp.next = newNode;
    }

    // Function to delete a node at the beginning of the list
    public void deleteAtBeginning() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node<T> temp = head;
        head = head.next;
        temp = null; // Helps with garbage collection
    }

    // Function to delete a node at the end of the list
    public void deleteAtEnd() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node<T> temp = head;

        // If there's only one node in the list
        if (temp.next == null) {
            head = null;
            return;
        }

        // Traverse to the second last node
        while (temp.next.next != null) {
            temp = temp.next;
        }

        // Free the last node
        temp.next = null;
    }

    // Function to delete a node at a specific position (0-based index)
    public void deleteAtPosition(int position) {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }

        Node<T> temp = head;

        // If head needs to be removed
        if (position == 0) {
            head = temp.next; // Change head
            temp = null; // Helps with garbage collection
            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 the number of nodes
        if (temp == null || temp.next == null) {
            System.out.println("Position out of bounds");
            return;
        }

        // Node temp.next is the node to be deleted
        Node<T> nextNode = temp.next.next;
        temp.next = nextNode; // Unlink the deleted node from the list
    }

    // Function to traverse the list and print all elements
    public void traverse() {
        Node<T> temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }

    // Function to search for an element in the list
    public boolean search(T key) {
        Node<T> temp = head;
        while (temp != null) {
            if (temp.data.equals(key)) // Use equals for object comparison
                return true; // Key found
            temp = temp.next;
        }
        return false; // Key not found
    }

    // Function to reverse the linked list
    public void reverse() {
        Node<T> 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
    public int size() {
        int size = 0;
        Node<T> temp = head;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    // Function to check if the list is empty
    public boolean isEmpty() {
        return head == null;
    }

    // Function to access an element at a specific index (0-based)
    public T get(int index) {
        int count = 0;
        Node<T> temp = head;
        while (temp != null) {
            if (count == index)
                return temp.data;
            count++;
            temp = temp.next;
        }
        return null; // Index out of range
    }

    // Function to set an element at a specific index (0-based)
    public void set(int index, T newValue) {
        Node<T> 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
        }

        System.out.println("Index out of range"); // Handle case where index exceeds list length
    }

    // Function to merge two lists
    private Node<T> merge(Node<T> head1, Node<T> head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        Node<T> mergedHead;
        if (((Comparable<T>) head1.data).compareTo(head2.data) <= 0) {
            mergedHead = head1;
            mergedHead.next = merge(head1.next, head2);
        } else {
            mergedHead = head2;
            mergedHead.next = merge(head1, head2.next);
        }
        return mergedHead;
    }

    // Function to get the middle of the linked list
    private Node<T> middle(Node<T> head) {
        if (head == null) return head;
        Node<T> slow = head;
        Node<T> fast = head.next;
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return slow;
    }

    // Function to sort the linked list (using Merge Sort)
    public 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);
    }

    // Function to clear the entire linked list and free memory
    public void clear() {
        head = null; // Helps with garbage collection
    }

    // Main method to test the linked list operations
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // Insert elements
        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        System.out.print("After inserting at the end: ");
        list.traverse();  // Output: 10 -> 20 -> 30 -> NULL

        // Insert at the beginning
        list.insertAtBeginning(5);
        System.out.print("After inserting at the beginning: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> NULL

        // Insert at the end
        list.insertAtEnd(40);
        System.out.print("After inserting at the end: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Insert at position
        list.insertAtPosition(25, 3);  // Insert 25 at position 3
        System.out.print("After inserting at position 3: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> NULL

        // Delete at position
        list.deleteAtPosition(3);  // Delete node at position 3
        System.out.print("After deleting at position 3: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Reverse the list
        list.reverse();
        System.out.print("After reversing the list: ");
        list.traverse();  // Output: 40 -> 30 -> 20 -> 10 -> 5 -> NULL

        // Search for a value
        boolean found = list.search(20);
        System.out.println("Is 20 in the list? " + (found ? "Yes" : "No"));  // Output: Yes

        // Get size of the list
        System.out.println("Size of the list: " + list.size());  // Output: 5

        // Sort the list
        Node<Integer> sortedHead = list.sort(list.head);
        list.clear(); // Clear the current list before assigning sorted list
        list.head = sortedHead; // Set the head to the sorted list
        System.out.print("After sorting the list: ");
        list.traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Clear the list
        list.clear();
        System.out.print("After clearing the list: ");
        list.traverse();  // Output: NULL
    }
}

Here is an implementation of a simple singly linked list in C#:

using System;

class Node
{
    public int Data;
    public Node Next;

    // Constructor to create a new node
    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

// Class to manage linked list operations
class LinkedList
{
    private Node head;

    // Constructor to initialize the linked list
    public LinkedList()
    {
        head = null;
    }

    // Function to insert a node at the beginning of the list
    public void InsertAtBeginning(int data)
    {
        Node newNode = new Node(data)
        {
            Next = head
        };
        head = newNode;
    }

    // Function to insert a node at the end of the list
    public void InsertAtEnd(int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.Next != null)
        {
            temp = temp.Next;
        }
        temp.Next = newNode;
    }

    // Function to insert a new node after a given previous node
    public void InsertAfterNode(Node prevNode, int data)
    {
        if (head == null)
        {
            Console.WriteLine("The list cannot be empty");
            return;
        }

        if (prevNode == null)
        {
            Console.WriteLine("The given previous node cannot be null");
            return;
        }

        Node newNode = new Node(data)
        {
            Next = prevNode.Next
        };
        prevNode.Next = newNode;
    }

    // Function to insert a node before a given node
    public void InsertBeforeNode(Node nextNode, int data)
    {
        if (head == null)
        {
            Console.WriteLine("The list cannot be empty");
            return;
        }

        if (nextNode == null)
        {
            Console.WriteLine("The given next node cannot be null");
            return;
        }

        Node newNode = new Node(data);
        if (head == nextNode)
        {
            newNode.Next = head;
            head = newNode;
            return;
        }

        Node temp = head;
        while (temp != null && temp.Next != nextNode)
        {
            temp = temp.Next;
        }

        if (temp == null)
        {
            Console.WriteLine("The given next node is not found in the list");
            return;
        }

        newNode.Next = temp.Next;
        temp.Next = newNode;
    }

    // Function to insert a node at a specific position (0-based index)
    public void InsertAtPosition(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 != null; i++)
        {
            temp = temp.Next;
        }

        if (temp == null)
        {
            Console.WriteLine("Position out of bounds");
            return;
        }

        newNode.Next = temp.Next;
        temp.Next = newNode;
    }

    // Function to delete a node at the beginning of the list
    public void DeleteAtBeginning()
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }
        Node temp = head;
        head = head.Next;
        temp = null; // Helps with garbage collection
    }

    // Function to delete a node at the end of the list
    public void DeleteAtEnd()
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }

        Node temp = head;

        // If there's only one node in the list
        if (temp.Next == null)
        {
            head = null;
            return;
        }

        // Traverse to the second last node
        while (temp.Next.Next != null)
        {
            temp = temp.Next;
        }

        // Free the last node
        temp.Next = null;
    }

    // Function to delete a node at a specific position (0-based index)
    public void DeleteAtPosition(int position)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }

        Node temp = head;

        // If head needs to be removed
        if (position == 0)
        {
            head = temp.Next; // Change head
            temp = null; // Helps with garbage collection
            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 the number of nodes
        if (temp == null || temp.Next == null)
        {
            Console.WriteLine("Position out of bounds");
            return;
        }

        // Node temp.Next is the node to be deleted
        Node nextNode = temp.Next.Next;
        temp.Next = nextNode; // Unlink the deleted node from the list
    }

    // Function to traverse the list and print all elements
    public void Traverse()
    {
        Node temp = head;
        while (temp != null)
        {
            Console.Write(temp.Data + " -> ");
            temp = temp.Next;
        }
        Console.WriteLine("NULL");
    }

    // Function to search for an element in the list
    public bool Search(int key)
    {
        Node temp = head;
        while (temp != null)
        {
            if (temp.Data == key)
                return true; // Key found
            temp = temp.Next;
        }
        return false; // Key not found
    }

    // Function to reverse the linked list
    public void Reverse()
    {
        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
    public int Size()
    {
        int size = 0;
        Node temp = head;
        while (temp != null)
        {
            size++;
            temp = temp.Next;
        }
        return size;
    }

    // Function to check if the list is empty
    public bool IsEmpty()
    {
        return head == null;
    }

    // Function to access an element at a specific index (0-based)
    public int Get(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)
    public void Set(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
    }

    // Function to merge two lists
    private Node Merge(Node head1, Node head2)
    {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        Node mergedHead;
        if (head1.Data <= head2.Data)
        {
            mergedHead = head1;
            mergedHead.Next = Merge(head1.Next, head2);
        }
        else
        {
            mergedHead = head2;
            mergedHead.Next = Merge(head1, head2.Next);
        }
        return mergedHead;
    }

    // Function to get the middle of the linked list
    private Node Middle(Node head)
    {
        if (head == null) return head;
        Node slow = head;
        Node fast = head.Next;
        while (fast != null)
        {
            fast = fast.Next;
            if (fast != null)
            {
                slow = slow.Next;
                fast = fast.Next;
            }
        }
        return slow;
    }

    // Function to sort the linked list (using Merge Sort)
    public Node Sort(Node head)
    {
        if (head == null || head.Next == null)
            return head;

        Node mid = Middle(head);
        Node nextToMid = mid.Next;
        mid.Next = null;

        Node left = Sort(head);
        Node right = Sort(nextToMid);

        return Merge(left, right);
    }

    // Function to clear the entire linked list and free memory
    public void Clear()
    {
        head = null; // Helps with garbage collection
    }

    // Main method to test the linked list operations
    public static void Main(string[] args)
    {
        LinkedList list = new LinkedList();

        // Insert elements
        list.InsertAtEnd(10);
        list.InsertAtEnd(20);
        list.InsertAtEnd(30);
        Console.Write("After inserting at the end: ");
        list.Traverse();  // Output: 10 -> 20 -> 30 -> NULL

        // Insert at the beginning
        list.InsertAtBeginning(5);
        Console.Write("After inserting at the beginning: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> NULL

        // Insert at the end
        list.InsertAtEnd(40);
        Console.Write("After inserting at the end: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Insert at position
        list.InsertAtPosition(25, 3);  // Insert 25 at position 3
        Console.Write("After inserting at position 3: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> NULL

        // Delete at position
        list.DeleteAtPosition(3);  // Delete node at position 3
        Console.Write("After deleting at position 3: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Reverse the list
        list.Reverse();
        Console.Write("After reversing the list: ");
        list.Traverse();  // Output: 40 -> 30 -> 20 -> 10 -> 5 -> NULL

        // Search for a value
        bool found = list.Search(20);
        Console.WriteLine("Is 20 in the list? " + (found ? "Yes" : "No"));  // Output: Yes

        // Get size of the list
        Console.WriteLine("Size of the list: " + list.Size());  // Output: 5

        // Sort the list
        Node sortedHead = list.Sort(list.head);
        list.Clear(); // Clear the current list before assigning sorted list
        list.head = sortedHead; // Set the head to the sorted list
        Console.Write("After sorting the list: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Clear the list
        list.Clear();
        Console.Write("After clearing the list: ");
        list.Traverse();  // Output: NULL
    }
}

Here is an implementation of a generic singly linked list in C#:

using System;

// Generic Node class
class Node<T>
{
    public T Data;
    public Node<T> Next;

    // Constructor to create a new node
    public Node(T data)
    {
        Data = data;
        Next = null;
    }
}

// Generic LinkedList class
class LinkedList<T>
{
    private Node<T> head;

    // Constructor to initialize the linked list
    public LinkedList()
    {
        head = null;
    }

    // Function to insert a node at the beginning of the list
    public void InsertAtBeginning(T data)
    {
        Node<T> newNode = new Node<T>(data)
        {
            Next = head
        };
        head = newNode;
    }

    // Function to insert a node at the end of the list
    public void InsertAtEnd(T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null)
        {
            head = newNode;
            return;
        }
        Node<T> temp = head;
        while (temp.Next != null)
        {
            temp = temp.Next;
        }
        temp.Next = newNode;
    }

    // Function to insert a new node after a given previous node
    public void InsertAfterNode(Node<T> prevNode, T data)
    {
        if (head == null)
        {
            Console.WriteLine("The list cannot be empty");
            return;
        }

        if (prevNode == null)
        {
            Console.WriteLine("The given previous node cannot be null");
            return;
        }

        Node<T> newNode = new Node<T>(data)
        {
            Next = prevNode.Next
        };
        prevNode.Next = newNode;
    }

    // Function to insert a node before a given node
    public void InsertBeforeNode(Node<T> nextNode, T data)
    {
        if (head == null)
        {
            Console.WriteLine("The list cannot be empty");
            return;
        }

        if (nextNode == null)
        {
            Console.WriteLine("The given next node cannot be null");
            return;
        }

        Node<T> newNode = new Node<T>(data);
        if (head == nextNode)
        {
            newNode.Next = head;
            head = newNode;
            return;
        }

        Node<T> temp = head;
        while (temp != null && temp.Next != nextNode)
        {
            temp = temp.Next;
        }

        if (temp == null)
        {
            Console.WriteLine("The given next node is not found in the list");
            return;
        }

        newNode.Next = temp.Next;
        temp.Next = newNode;
    }

    // Function to insert a node at a specific position (0-based index)
    public void InsertAtPosition(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 != null; i++)
        {
            temp = temp.Next;
        }

        if (temp == null)
        {
            Console.WriteLine("Position out of bounds");
            return;
        }

        newNode.Next = temp.Next;
        temp.Next = newNode;
    }

    // Function to delete a node at the beginning of the list
    public void DeleteAtBeginning()
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }
        Node<T> temp = head;
        head = head.Next;
        temp = null; // Helps with garbage collection
    }

    // Function to delete a node at the end of the list
    public void DeleteAtEnd()
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }

        Node<T> temp = head;

        // If there's only one node in the list
        if (temp.Next == null)
        {
            head = null;
            return;
        }

        // Traverse to the second last node
        while (temp.Next.Next != null)
        {
            temp = temp.Next;
        }

        // Free the last node
        temp.Next = null;
    }

    // Function to delete a node at a specific position (0-based index)
    public void DeleteAtPosition(int position)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }

        Node<T> temp = head;

        // If head needs to be removed
        if (position == 0)
        {
            head = temp.Next; // Change head
            temp = null; // Helps with garbage collection
            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 the number of nodes
        if (temp == null || temp.Next == null)
        {
            Console.WriteLine("Position out of bounds");
            return;
        }

        // Node temp.Next is the node to be deleted
        Node<T> nextNode = temp.Next.Next;
        temp.Next = nextNode; // Unlink the deleted node from the list
    }

    // Function to traverse the list and print all elements
    public void Traverse()
    {
        Node<T> temp = head;
        while (temp != null)
        {
            Console.Write(temp.Data + " -> ");
            temp = temp.Next;
        }
        Console.WriteLine("NULL");
    }

    // Function to search for an element in the list
    public bool Search(T key)
    {
        Node<T> temp = head;
        while (temp != null)
        {
            if (temp.Data.Equals(key))
                return true; // Key found
            temp = temp.Next;
        }
        return false; // Key not found
    }

    // Function to reverse the linked list
    public void Reverse()
    {
        Node<T> 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
    public int Size()
    {
        int size = 0;
        Node<T> temp = head;
        while (temp != null)
        {
            size++;
            temp = temp.Next;
        }
        return size;
    }

    // Function to check if the list is empty
    public bool IsEmpty()
    {
        return head == null;
    }

    // Function to access an element at a specific index (0-based)
    public T Get(int index)
    {
        int count = 0;
        Node<T> temp = head;
        while (temp != null)
        {
            if (count == index)
                return temp.Data;
            count++;
            temp = temp.Next;
        }
        throw new IndexOutOfRangeException("Index out of range");
    }

    // Function to set an element at a specific index (0-based)
    public void Set(int index, T newValue)
    {
        Node<T> 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
    }

    // Function to merge two lists
    private Node<T> Merge(Node<T> head1, Node<T> head2)
    {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        Node<T> mergedHead;
        if (Comparer<T>.Default.Compare(head1.Data, head2.Data) <= 0)
        {
            mergedHead = head1;
            mergedHead.Next = Merge(head1.Next, head2);
        }
        else
        {
            mergedHead = head2;
            mergedHead.Next = Merge(head1, head2.Next);
        }
        return mergedHead;
    }

    // Function to get the middle of the linked list
    private Node<T> Middle(Node<T> head)
    {
        if (head == null) return head;
        Node<T> slow = head;
        Node<T> fast = head.Next;
        while (fast != null)
        {
            fast = fast.Next;
            if (fast != null)
            {
                slow = slow.Next;
                fast = fast.Next;
            }
        }
        return slow;
    }

    // Function to sort the linked list (using Merge Sort)
    public 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);
    }

    // Function to clear the entire linked list and free memory
    public void Clear()
    {
        head = null; // Helps with garbage collection
    }

    // Main method to test the linked list operations
    public static void Main(string[] args)
    {
        LinkedList<int> list = new LinkedList<int>();

        // Insert elements
        list.InsertAtEnd(10);
        list.InsertAtEnd(20);
        list.InsertAtEnd(30);
        Console.Write("After inserting at the end: ");
        list.Traverse();  // Output: 10 -> 20 -> 30 -> NULL

        // Insert at the beginning
        list.InsertAtBeginning(5);
        Console.Write("After inserting at the beginning: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> NULL

        // Insert at the end
        list.InsertAtEnd(40);
        Console.Write("After inserting at the end: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Insert at position
        list.InsertAtPosition(25, 3);  // Insert 25 at position 3
        Console.Write("After inserting at position 3: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> NULL

        // Delete at position
        list.DeleteAtPosition(3);  // Delete node at position 3
        Console.Write("After deleting at position 3: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Reverse the list
        list.Reverse();
        Console.Write("After reversing the list: ");
        list.Traverse();  // Output: 40 -> 30 -> 20 -> 10 -> 5 -> NULL

        // Search for a value
        bool found = list.Search(20);
        Console.WriteLine("Is 20 in the list? " + (found ? "Yes" : "No"));  // Output: Yes

        // Get size of the list
        Console.WriteLine("Size of the list: " + list.Size());  // Output: 5

        // Sort the list
        Node<int> sortedHead = list.Sort(list.head);
        list.Clear(); // Clear the current list before assigning sorted list
        list.head = sortedHead; // Set the head to the sorted list
        Console.Write("After sorting the list: ");
        list.Traverse();  // Output: 5 -> 10 -> 20 -> 30 -> 40 -> NULL

        // Clear the list
        list.Clear();
        Console.Write("After clearing the list: ");
        list.Traverse();  // Output: NULL
    }
}