Doubly Linked List

A doubly linked list is a linear data structure consisting of a sequence of elements, called nodes, where each node points to both its previous and next nodes in the sequence. Unlike arrays, elements in a linked list are not stored in contiguous memory locations. Each node contains three fields:

• Data: The value or information stored in the node.
• Next Pointer: A reference (or pointer) to the next node in the sequence.
• Previous Pointer: A reference (or pointer) to the previous node in the sequence.

The doubly linked list forms a linear collection of elements where each node points to both its successor and its predecessor. The first node, known as the head, has a NULL reference for its previous pointer, indicating the beginning of the list. The last node has a NULL reference for its next pointer, marking the end of the list.

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.

Insertions and deletions of nodes, particularly at the beginning, middle, or end of the list, are more efficient compared to arrays since you do not need to shift elements. However, managing both the previous and next pointers requires extra attention.

The nodes in a doubly linked list do not need to be stored in contiguous memory locations, unlike arrays. Each node is linked to the next and previous nodes 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 doubly linked list requires extra memory for the two pointers (next and previous references), which slightly increases memory usage compared to arrays or singly linked lists.

Here's a visual representation of a doubly linked list:

HEAD -> [NULL | Data | Next] <->  [Prev | Data | Next] <->  [Prev | Data | NULL]

In the above representation:

• The Head points to the first node of the list, providing quick access to the start of the list.
• Each node contains Data, a Next pointer to the next node, and a Previous pointer to the previous node.
• The last node in the list has its Next pointer set to NULL, indicating the end of the list. Its Prev pointer points to the previous node.
• The Prev pointer of the first node is NULL, as there is no node before it.

A simple doubly linked list with three nodes could look like this:

Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

In the above example:

• The head points to the first node containing the data 10. The Prev pointer of this node is NULL, as there is no node before it.
• The second node contains the data 20. Its Prev pointer points to the first node, and its Next pointer points to the third node.
• The third node contains the data 30. Its Prev pointer points to the second node, and its Next pointer is NULL, indicating the end of the list.

Here's a detailed breakdown of common doubly linked list operations:

• insertAtBeginning():
  
  • Description: Inserts a new node at the start (or head) of a doubly linked list.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 5 | Next] <-> [Prev | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

  • Time complexity: The time complexity of inserting a node at the beginning of a doubly linked list is \(O(1)\) (constant time). If the list is empty, the following steps are performed:
    
    • Create a new node.
    • Set the next pointer of the new node to NULL, as there is no node after it.
    • Set the prev pointer of the new node to NULL, as it will become the first node.
    • Update the head pointer to point to the new node.
    
    If the list is not empty, the following steps are performed:
    
    • Create a new node.
    • Set the next pointer of the new node to point to the current head node (the first node in the list).
    • If the list is not empty, set the prev pointer of the current head node to point to the new node.
    • Set the prev pointer of the new node to NULL, as it will become the first node.
    • Update the head pointer to point to the new node.
    
    Since no traversal is required, this operation takes constant time, \(O(1)\).
  • Space complexity: The space complexity of inserting a node at the beginning of a doubly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAtEnd():
  
  • Description: Inserts a new node at the end (or tail) of a doubly linked list.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | Next] <-> [Prev | 40 | NULL]

  • Time complexity: The time complexity of inserting a node at the end of a singly linked list is \(O(n)\) (linear time) in the general case.
    
    • Best Case (Empty List): If the list is empty, inserting a new node at the end is the same as inserting at the beginning. The following steps are performed:
      
      • Create a new node.
      • Set the next pointer of the new node NULL, as it will be the only node in the list.
      • Update the head pointer to point to the new node.
      
      Since no traversal is required, this operation takes constant time, \(O(1)\).
    • Average/Worst Case (Non-Empty List): If the list is not empty, you have to traverse the entire list to reach the last node. The following steps are performed:
      • Start from the head node.
      • Traverse the list by following the next pointers until you reach the last node (the node whose next pointer is NULL).
      • Create a new node.
      • Set the next pointer of the new node to NULL.
      • Update the next pointer of the last node to point to the new node.
      
      The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\).
  • Space complexity: The space complexity of inserting a node at the end of a singly linked list is \(O(1)\) (constant space). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAfterNode():
  
  • Description: Inserts a new node in a singly linked list immediately after a given node. If the target node doesn't exist, you may opt to do nothing and just return control to the caller without modifying the list.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 25 | Next] <-> [Prev | 30 | NULL]

  • Time complexity: The time complexity of inserting a node after a node in a doubly linked list is \(O(1)\) (constant time). The following steps are performed:
    
    • Create a new node.
    • Set the next pointer of the new node to point to the node that follows the given node.
    • Set the prev pointer of the new node to point to the given node.
    • Update its prev pointer of the node following the given node to point to the new node.
    • Update the next pointer of the given node to point to the new node.
    
    Since no traversal is required, this operation takes constant time, \(O(1)\).
  • Space complexity: The space complexity of inserting a node after a node in a doubly linked list is \(O(1)\) (constant time). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertBeforeNode():
  
  • Description: Inserts a new node 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 -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 10 | Next] -> [NULL | 25 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

  • Time complexity: The time complexity for inserting a node before a node in a doubly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • Create a new node.
    • Locate the preceding node (the node whose next pointer points to the target node).
    • Set the prev pointer of the new node to point to the preceding node.
    • Set the next pointer of the new node to point to the target node.
    • Update the prev pointer of the target node to point to the new node.
    • Update the next pointer of the preceding node to point to the new node.
    
    The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\).
  • Space complexity: The space complexity for inserting a node before a node in a doubly linked list is \(O(1)\) (constant time). The space required to allocate the new node is a fixed amount and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• insertAtPosition():
  
  • Description: Inserts a new node at a specified position in a doubly linked list. Positions are usually indexed starting from 0 or 1. If the position is 1 (or 0, based on indexing), this implies insertion at the beginning of the list. If the position is greater than the size of the list or less than 1, the function may return an error or take no action since the insertion would be out of range.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 35 | Next] <-> [Prev | 30 | NULL]

  • Time complexity: The time complexity for inserting a new node at a specified position in a doubly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • Create a new node.
    • Locate the preceding node (the node whose next pointer points to the target node).
    • Set the prev pointer of the new node to point to the preceding node.
    • Set the next pointer of the new node to point to the target node.
    • Update the prev pointer of the target node to point to the new node.
    • Update the next pointer of the preceding node to point to the new node.
    
    The traversal takes \(O(n)\) time, where \(n\) is the number of nodes in the list. Updating the pointer takes \(O(1)\).
  • Space complexity: The space complexity for removing a node at the beginning of a doubly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• deleteAtBeginning():
  
  • Description: Removes a node at the start (or head) of a doubly linked list. If the list is empty, it prints a message "List is empty" and returns, since there is no node to delete.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 20 | Next] <-> [Prev | 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). The following steps are performed:
    
    • Set the head pointer to the next node
    • Set the prev pointer of the new head node (if it exists) to NULL.
    • Deallocate the memory for the old head node.
    
    Since no traversal is required, this operation takes constant time, \(O(1)\).
  • Space complexity: The space complexity for removing a node at the beginning of a doubly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• deleteAtEnd():
  
  • Description: Removes a node at the end (or tail) of a doubly linked list. If the list is empty, it prints a message "List is empty" and returns, since there is no node to delete.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | NULL]

  • Time complexity: The time complexity for removing a node at the end of a doubly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • Start at the head node.
    • Traverse until reaching the second-to-last node.
    • Set the next pointer of the second-to-last node to null.
    • Deallocate the memory for the old last node.
    
    
  • Space complexity: The space complexity for removing a node at the end of a singly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• deleteAtPosition():
  
  • Description: Removes a node at a specified position in a linked list. Positions are usually indexed starting from 0 or 1. If the position to delete is 0, it means the head node should be removed. If the specified position is out of bounds, and a message is printed.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

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

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | NULL]

  • Time complexity: The time complexity for removing a node at a specified position in a doubly linked list is \(O(n)\) (linear time). The following steps are performed:
    
    • Start at the head node.
    • Traverse until reaching the node before the target position.
    • Update the next pointer of the preceding node to point to the node after the target node (if it exists).
    • Update the prev pointer of the node after the target node (if it exists) to point to the preceding node.
    • Deallocate the memory for the removed node.
    
    
  • Space complexity: The space complexity for removing a node at a specified position in a doubly linked list is \(O(1)\) (constant space). Only a fixed amount of space is used to store references to the head node and does not depend on the size of the list. No additional data structures or auxiliary space are used in the process.
• traverse():
  
  • Description: Visits each node in a doubly linked list and perform an action, such as printing the node's value.
  • Time complexity: The time complexity of traverse function in a linked list is \(O(n)\) (linear time). The function iterates through each node in the linked list exactly once, from the head to the end (NULL). Thus, the number of operations performed is directly proportional to the number of nodes.
  • Space complexity: The space complexity of traverse function in a linked list is \(O(1)\) (constant space). The function only uses a constant amount of space to store variables such as the current node reference during the traversal. Regardless of the size of the linked list, the amount of extra space used does not change.
• reverse():
  
  • Description: Reverses the order of nodes in a doubly linked list.
  • Example:
    • Suppose you have the following linked list:
      

      Head -> [NULL | 10 | Next] <-> [Prev | 20 | Next] <-> [Prev | 30 | NULL]

    • After calling reverse(), the list becomes:
      

      Head -> [NULL | 30 | Next] <-> [Prev | 20 | Next] <-> [Prev | 10 | NULL]

  • Time complexity: The time complexity of reverse function in a doubly 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 doubly linked list is \(O(1)\) (constant space). The function only uses a fixed amount of extra space for variables, such as pointers for the current, previous, and next nodes. This amount of space does not depend on the size of the linked list.
• search():
  
  • Description: Finds whether a specific element (or key) exists in a doubly 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 extra space to store variables, such as pointers for the current node. The space required does not depend on the size of the list because the function does not use any additional data structures or dynamic memory allocations for the search process.
• size():
  
  • Description: Calculates and returns the number of nodes in a doubly 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 doubly 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 doubly 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 doubly 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 doubly linked list is \(O(1)\) (constant space). The function only uses a constant amount of space for variables, such as the pointer to the current node and the index being tracked. This space requirement does not depend on the size of the list.
• set():
  
  • Description: Updates the value of a node at a specified index in a doubly 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 doubly 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 doubly linked list is \(O(1)\) (constant space). The function only uses a constant amount of space for variables, such as the pointer to the current node and the index being tracked. This space requirement does not depend on the size of the list.
• isEmpty():
  
  • Description: Checks whether a doubly linked list is empty.
  • Time complexity: The time complexity of isEmpty function in a doubly 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 doubly linked list is \(O(1)\) (constant space). The function uses a fixed amount of space to store the result of the comparison (typically a boolean value), regardless of the size of the linked list.
• merge():
  
  • Description: Combines two sorted linked lists into a single sorted linked list.
  • Time complexity: The time complexity of merge function in a doubly 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 doubly linked list is \(O(n + m)\) (linear space) due to the call stack storing recursive calls. In the worst case, the maximum depth of recursion will be equal to the total number of nodes in both lists combined, leading to \(n + m\) recursive calls.
• sort():
  
  • Description: Arranges the elements of a doubly linked list, in a specific order (typically ascending or descending).
  • Time complexity: The time complexity of sort function in a doubly linked list, when using merge sort is \(O(n \log n)\) (linearithmic time) because the algorithm consistently divides the list into halves and requires a linear amount of time \(O(n)\) to merge those halves back together. The logarithmic factor \(\log n\) comes from the number of times the list can be divided in half (depth of recursion).
  • Space complexity: The space complexity of sort function in a doubly linked list, specifically Merge Sort, is \(O(n)\) (linear space) because it requires additional space for the temporary arrays or linked lists used during the merge process. When merging two halves, the algorithm needs space to hold the merged elements before copying them back to the original array or linked list.
• clear():
  
  • Description: Removes all nodes from the list and free up the memory they occupy, effectively making the list empty.
  • Time complexity: The time complexity of clear function in a doubly linked list is \(O(n)\) (linear time). The function iterates through each node exactly once, freeing its memory. Since it processes all nodes in the list, the time complexity is proportional to the number of nodes.
  • Space complexity: The space complexity of clear function in a doubly linked list is \(O(1)\) (constant space). The function only requires a fixed amount of extra memory for the iteration, typically for a pointer to traverse the list. No additional memory structures are needed, regardless of the size of the linked list.

Non-Generic Singly Linked List Implementation

Here is the Non-Generic singly linked list implementation in C:

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

// defines a structure to represent a node in a doubly linked list
typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** headRef, int data) {
    Node* newNode = createNode(data);
    if (*headRef != NULL) {
        (*headRef)->prev = newNode;
    }
    newNode->next = *headRef;
    *headRef = newNode;
}

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

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

    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
}

// Function to insert a new node before a given next node
void insertBeforeNode(Node** headRef, Node* nextNode, int data) {
    if (*headRef == NULL) {
        printf("The list cannot be empty\n");
        return;
    }
    if (nextNode == NULL) {
        printf("The given next node cannot be NULL\n");
        return;
    }

    Node* newNode = createNode(data);
    if (*headRef == nextNode) {
        newNode->next = *headRef;
        (*headRef)->prev = newNode;
        *headRef = newNode;
        return;
    }

    newNode->next = nextNode;
    newNode->prev = nextNode->prev;
    if (nextNode->prev != NULL) {
        nextNode->prev->next = newNode;
    }
    nextNode->prev = newNode;
}

// Function to insert a node at a specific position (0-based index)
void insertAtPosition(Node** headRef, int data, int position) {
    Node* newNode = createNode(data);
    
    if (position == 0) {
        newNode->next = *headRef;
        if (*headRef != NULL) {
            (*headRef)->prev = newNode;
        }
        *headRef = newNode;
        return;
    }

    Node* temp = *headRef;
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Position out of bounds\n");
        free(newNode);
        return;
    }

    newNode->next = temp->next;
    newNode->prev = temp;
    if (temp->next != NULL) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
}

// Function to delete a node at the beginning of the list
void deleteAtBeginning(Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }
    Node* temp = *headRef;
    *headRef = (*headRef)->next;
    if (*headRef != NULL) {
        (*headRef)->prev = NULL;
    }
    free(temp);
}

// Function to delete a node at the end of the list
void deleteAtEnd(Node** headRef) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }

    Node* temp = *headRef;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    if (temp->prev != NULL) {
        temp->prev->next = NULL;
    } else {
        *headRef = NULL; // List has only one element
    }
    free(temp);
}

// Function to delete a node at a specific position (0-based index)
void deleteAtPosition(Node** headRef, int position) {
    if (*headRef == NULL) {
        printf("List is empty\n");
        return;
    }

    Node* temp = *headRef;

    if (position == 0) {
        *headRef = temp->next;
        if (*headRef != NULL) {
            (*headRef)->prev = NULL;
        }
        free(temp);
        return;
    }

    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("Position out of bounds\n");
        return;
    }

    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    if (nodeToDelete->next != NULL) {
        nodeToDelete->next->prev = temp;
    }
    free(nodeToDelete);
}

// Function to traverse the list and print all elements
void traverse(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

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

// Function to reverse the linked list
void reverse(Node** headRef) {
    Node *temp = NULL;
    Node* current = *headRef;
    
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }

    if (temp != NULL) {
        *headRef = temp->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;

    while (current != NULL) {
        if (count == index) {
            current->data = newValue;
            return;
        }
        count++;
        current = current->next;
    }

    printf("Index out of range\n");
}

// Function to clear the entire linked list and free memory
void clear(Node** headRef) {
    Node* current = *headRef;
    Node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    *headRef = NULL;
}

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

// Function to merge two lists
void merge(Node** headRef, Node* head1, Node* head2) {
    // Log the current state of head1 and head2
    //printf("Merging: head1 data = %d, head2 data = %d\n", 
    //       head1 ? head1->data : -1, head2 ? head2->data : -1);

    // Base case when one of the lists is empty
    if (head1 == NULL) {
        // Log when head1 is NULL and remaining head2 is being added
        if (head2 != NULL) {
            printf("head1 is NULL, adding remaining head2 data: %d\n", head2->data);
            Node* newNode = createNode(head2->data); // Create a new node
            *headRef = newNode;
            merge(&((*headRef)->next), head1, head2->next);
        }
        return;
    }
    if (head2 == NULL) {
        // Log when head2 is NULL and remaining head1 is being added
        if (head1 != NULL) {
            //printf("head2 is NULL, adding remaining head1 data: %d\n", head1->data);
            Node* newNode = createNode(head1->data); // Create a new node
            *headRef = newNode;
            merge(&((*headRef)->next), head1->next, head2);
        }
        return;
    }

    // Compare the data of head1 and head2 and merge accordingly
    if (head1->data <= head2->data) {
        // Log when adding data from head1
        //printf("Adding head1 data: %d\n", head1->data);
        Node* newNode = createNode(head1->data); // Create a new node
        *headRef = newNode;
        merge(&((*headRef)->next), head1->next, head2);
        if ((*headRef)->next != NULL) {
            (*headRef)->next->prev = *headRef;
        }
    } else {
        // Log when adding data from head2
        //printf("Adding head2 data: %d\n", head2->data);
        Node* newNode = createNode(head2->data); // Create a new node
        *headRef = newNode;
        merge(&((*headRef)->next), head1, head2->next);
        if ((*headRef)->next != NULL) {
            (*headRef)->next->prev = *headRef;
        }
    }

    // Log when merge is completed for this recursion
    //printf("Merge step completed. headRef data = %d\n", (*headRef)->data);
}


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

    Node* head = *headRef;
    Node* mid = NULL;
    middle(&mid, head);
    Node* nextToMid = mid->next;
    mid->next = NULL;
	
	// Properly handle the 'prev' pointers for a doubly linked list
    if (nextToMid != nullptr) {
        nextToMid->prev = nullptr;  // Set 'prev' of the second half to null
    }
	
    // Sort the two halves
    sort(&head);
    sort(&nextToMid);

    // Merge the sorted halves
    merge(headRef, head, nextToMid);
}

// Main function to test the doubly linked list operations
int main() {
    Node* list = NULL;

    insertAtBeginning(&list, 5);
    insertAtBeginning(&list, 3);
    insertAtBeginning(&list, 1);

    printf("List after inserting at the beginning: ");
    traverse(list);

    insertAtEnd(&list, 7);
    insertAtEnd(&list, 9);

    printf("List after inserting at the end: ");
    traverse(list);

    insertAtPosition(&list, 4, 2);

    printf("List after inserting 4 at position 2: ");
    traverse(list);

    Node* secondNode = list->next;
    insertAfterNode(secondNode, 6);

    printf("List after inserting 6 after the second node: ");
    traverse(list);

    Node* temp = list;
    while (temp != NULL && temp->data != 7) {
        temp = temp->next;
    }
    insertBeforeNode(&list, temp, 8);

    printf("List after inserting 8 before the node with value 7: ");
    traverse(list);

    deleteAtBeginning(&list);

    printf("List after deleting the first node: ");
    traverse(list);

    deleteAtEnd(&list);

    printf("List after deleting the last node: ");
    traverse(list);

    deleteAtPosition(&list, 2);

    printf("List after deleting the node at position 2: ");
    traverse(list);

    int key = 6;
    if (search(list, key)) {
        printf("Element %d found in the list.\n", key);
    } else {
        printf("Element %d not found in the list.\n", key);
    }

    reverse(&list);

    printf("List after reversing: ");
    traverse(list);

    // Sort the list
    sort(&list);

    printf("List after sorting: ");
    traverse(list);

    printf("Size of the list: %d\n", size(list));

    int index = 2;
    int value = get(list, index);
    if (value != -1) {
        printf("Element at index %d: %d\n", index, value);
    } else {
        printf("Index %d is out of range.\n", index);
    }

    set(list, 2, 10);
    printf("List after setting value 10 at index 2: ");
    traverse(list);

    Node* list1 = NULL;

    insertAtBeginning(&list1, 25);
    insertAtBeginning(&list1, 35);
    insertAtBeginning(&list1, 14);
    
    clear(&list);

    printf("List after clearing: ");
    traverse(list);

    return 0;
}

Here is the Non-Generic singly linked list implementation in C++:

#include <iostream>

using namespace std;

// Node structure for doubly linked list
struct Node {
    int data;
    Node* next;
    Node* prev;

    // Constructor to create a new node
    Node(int data) : data(data), next(nullptr), prev(nullptr) {}
};

// Insert at the beginning
void insertAtBeginning(Node*& head, int data) {
    Node* newNode = new Node(data);
    newNode->next = head;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

// Insert at the end
void insertAtEnd(Node*& head, int data) {
    Node* newNode = new Node(data);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Function to insert a new node after a given previous node
void insertAfterNode(Node* prevNode, int data) {
    // Check if the previous node is NULL
    if (prevNode == nullptr) {
        std::cout << "The given previous node cannot be NULL." << std::endl;
        return;
    }

    Node* newNode = new Node(data);

    // Insert the new node after the previous node
    newNode->next = prevNode->next;
    if (prevNode->next != nullptr) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
    newNode->prev = prevNode;
}

// Function to insert a new node before a given next node
void insertBeforeNode(Node*& headRef, Node* nextNode, int data) {
    if (headRef == nullptr) {
        std::cout << "The list cannot be empty" << std::endl;
        return;
    }

    if (nextNode == nullptr) {
        std::cout << "The given next node cannot be NULL" << std::endl;
        return;
    }

    Node* newNode = new Node(data);

    // If the nextNode is the head node, handle the insertion at the beginning
    if (headRef == nextNode) {
        newNode->next = headRef;
        headRef->prev = newNode;
        headRef = newNode;
        return;
    }

    // Find the node just before the nextNode
    Node* temp = headRef;
    while (temp != nullptr && temp->next != nextNode) {
        temp = temp->next;
    }

    if (temp == nullptr) {
        std::cout << "The given next node is not found in the list" << std::endl;
        delete newNode;
        return;
    }

    newNode->next = temp->next;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Insert at a specific position
void insertAtPosition(Node*& head, int data, int position) {
    Node* newNode = new Node(data);
    if (position == 0) {
        newNode->next = head;
        if (head != nullptr) {
            head->prev = newNode;
        }
        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;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}


// Delete at the beginning
void deleteAtBeginning(Node*& head) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }
    Node* temp = head;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;
    }
    delete temp;
}


// Delete at the end
void deleteAtEnd(Node*& head) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    temp->prev->next = nullptr;
    delete temp;
}


// Delete at a specific position
void deleteAtPosition(Node*& head, int position) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    if (position == 0) {
        Node* temp = head;
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        }
        delete temp;
        return;
    }

    Node* temp = head;
    for (int i = 0; i < position - 1 && temp != nullptr; i++) {
        temp = temp->next;
    }

    if (temp == nullptr || temp->next == nullptr) {
        cout << "Position out of bounds\n";
        return;
    }

    Node* nextNode = temp->next->next;
    delete temp->next;
    if (nextNode != nullptr) {
        nextNode->prev = temp;
    }
    temp->next = nextNode;
}

// Function to reverse a doubly linked list
void reverse(Node*& head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next = nullptr;

    while (current != nullptr) {
        // Swap next and prev for the current node
        next = current->next;
        current->next = prev;
        current->prev = next;

        // Move to the next node in the original list
        prev = current;
        current = next;
    }

    // Update head to the last node (new head after reverse)
    head = prev;
}

// Function to get the size of a doubly linked list
int size(Node* head) {
    int count = 0;
    Node* temp = head;

    while (temp != nullptr) {
        count++;  // Increment count for each node
        temp = temp->next;  // Move to the next node
    }

    return count;
}

// Function to access an element at a specific index (0-based) in a doubly linked list
int get(Node* head, int index) {
    int count = 0;
    Node* temp = head;

    // Traverse the list to find the node at the specified index
    while (temp != nullptr) {
        if (count == index)
            return temp->data;  // Return the data at the index
        count++;
        temp = temp->next;  // Move to the next node
    }

    return -1;  // Index out of range
}

// Function to set an element at a specific index (0-based) in a doubly linked list
void set(Node* head, int index, int newValue) {
    Node* current = head;
    int count = 0;

    // Traverse the list until the specified index
    while (current != nullptr) {
        if (count == index) {
            current->data = newValue;  // Update the node's value
            return;  // Exit the function after the update
        }
        count++;
        current = current->next;  // Move to the next node
    }

    cout << "Index out of range\n";  // Handle case where index exceeds list length
}

// Search for an element in a doubly linked list
bool search(Node* head, int key) {
    Node* temp = head;
    while (temp != nullptr) {
        if (temp->data == key)
            return true;  // Element found
        temp = temp->next;
    }
    return false;  // Element not found
}

// Traverse the list (forward)
void traverse(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " <-> ";
        temp = temp->next;
    }
    cout << "NULL\n";
}

// Find the middle of the list
void middle(Node*& mid, Node* head) {
    if (head == nullptr) {
        mid = nullptr;
        return;
    }

    Node* slow = head;
    Node* fast = head->next;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    mid = slow;
}

// Merge two sorted lists
void merge(Node*& headRef, Node* head1, Node* head2) {
    if (head1 == nullptr) {
        headRef = head2;
        return;
    }
    if (head2 == nullptr) {
        headRef = head1;
        return;
    }

    if (head1->data <= head2->data) {
        headRef = head1;
        merge(headRef->next, head1->next, head2);
        if (headRef->next != nullptr) {
            headRef->next->prev = headRef;
        }
    } else {
        headRef = head2;
        merge(headRef->next, head1, head2->next);
        if (headRef->next != nullptr) {
            headRef->next->prev = headRef;
        }
    }
}

// Sort the list using merge sort
void sort(Node*& head) {
    if (head == nullptr || head->next == nullptr)
        return;

    Node* mid = nullptr;
    middle(mid, head);

    Node* nextToMid = mid->next;
    mid->next = nullptr;
	
	// Properly handle the 'prev' pointers for a doubly linked list
    if (nextToMid != nullptr) {
        nextToMid->prev = nullptr;  // Set 'prev' of the second half to null
    }
	
    Node* left = head;
    Node* right = nextToMid;

    sort(left);
    sort(right);

    merge(head, left, right);
}

// Clear the list
void clear(Node*& head) {
    Node* current = head;
    while (current != nullptr) {
        Node* next = current->next;
        delete current;
        current = next;
    }
    head = nullptr;
}

int main() {
    Node* list = nullptr;  // Initialize an empty doubly linked list

    // Insert elements at the beginning
    insertAtBeginning(list, 5);
    insertAtBeginning(list, 3);
    insertAtBeginning(list, 1);

    cout << "List after inserting at the beginning: ";
    traverse(list);

    // Insert elements at the end
    insertAtEnd(list, 7);
    insertAtEnd(list, 9);

    cout << "List after inserting at the end: ";
    traverse(list);

    // Insert element at position 2
    insertAtPosition(list, 4, 2);

    cout << "List after inserting 4 at position 2: ";
    traverse(list);

    // Insert element after the second node
    Node* secondNode = list->next;
    insertAfterNode(secondNode, 6);

    cout << "List after inserting 6 after the second node: ";
    traverse(list);

    // Insert element before the node with value 7
    Node* temp = list;
    while (temp != nullptr && temp->data != 7) {
        temp = temp->next;
    }
    insertBeforeNode(list, temp, 8);

    cout << "List after inserting 8 before the node with value 7: ";
    traverse(list);

    // Delete the first node
    deleteAtBeginning(list);

    cout << "List after deleting the first node: ";
    traverse(list);

    // Delete the last node
    deleteAtEnd(list);

    cout << "List after deleting the last node: ";
    traverse(list);

    // Delete the node at position 2
    deleteAtPosition(list, 2);

    cout << "List after deleting the node at position 2: ";
    traverse(list);

    // Search for an element
    int key = 6;
    if (search(list, key)) {
        cout << "Element " << key << " found in the list." << endl;
    } else {
        cout << "Element " << key << " not found in the list." << endl;
    }

    // Reverse the list
    reverse(list);

    cout << "List after reversing: ";
    traverse(list);

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

    // Clear the list
    clear(list);

    cout << "List after clearing: ";
    traverse(list);

    return 0;
}

Here is the Non-Generic singly linked list implementation in Java:

public class DoublyLinkedList {

    // Node structure for doubly linked list
    static class Node {
        int data;
        Node next;
        Node prev;

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

    // Insert at the beginning
    public static Node insertAtBeginning(Node head, int data) {
        Node newNode = new Node(data);
        if (head != null) {
            head.prev = newNode;
        }
        newNode.next = head;
        return newNode;
    }

    // Insert at the end
    public static Node insertAtEnd(Node head, int data) {
        Node newNode = new Node(data);
        if (head == null) {
            return newNode;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return head;
    }

    // Insert at a specific position
    public static Node insertAtPosition(Node head, int data, int position) {
        Node newNode = new Node(data);
        if (position == 0) {
            if (head != null) {
                head.prev = newNode;
            }
            newNode.next = head;
            return newNode;
        }

        Node temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }

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

        newNode.next = temp.next;
        if (temp.next != null) {
            temp.next.prev = newNode;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return head;
    }
	
	// Insert after a given node
    public static void insertAfterNode(Node prevNode, int data) {
        if (prevNode == null) {
            System.out.println("The given previous node cannot be null");
            return;
        }
        Node newNode = new Node(data);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        newNode.prev = prevNode;
        if (newNode.next != null) {
            newNode.next.prev = newNode;
        }
    }

    // Insert before a given node
    public static Node insertBeforeNode(Node head, Node nextNode, int data) {
        if (nextNode == null) {
            System.out.println("The given next node cannot be null");
            return head;
        }
        Node newNode = new Node(data);
        newNode.prev = nextNode.prev;
        newNode.next = nextNode;
        nextNode.prev = newNode;
        if (newNode.prev != null) {
            newNode.prev.next = newNode;
        } else {
            head = newNode;
        }
        return head;
    }
	
    // Delete at the beginning
    public static Node deleteAtBeginning(Node head) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }
        Node newHead = head.next;
        if (newHead != null) {
            newHead.prev = null;
        }
        return newHead;
    }

    // Delete at the end
    public static Node deleteAtEnd(Node head) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }

        if (head.next == null) {
            return null;
        }

        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.prev.next = null;
        return head;
    }

    // Delete at a specific position
    public static Node deleteAtPosition(Node head, int position) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }

        if (position == 0) {
            return deleteAtBeginning(head);
        }

        Node temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }

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

        Node toDelete = temp.next;
        temp.next = toDelete.next;
        if (toDelete.next != null) {
            toDelete.next.prev = temp;
        }
        return head;
    }

    // Get element at a specific index
    public static int get(Node head, int index) {
        int count = 0;
        Node temp = head;

        while (temp != null) {
            if (count == index) {
                return temp.data;
            }
            count++;
            temp = temp.next;
        }

        System.out.println("Index out of range");
        return -1; // Return -1 if the index is out of range
    }

    // Set element at a specific index
    public static void set(Node head, int index, int newValue) {
        int count = 0;
        Node temp = head;

        while (temp != null) {
            if (count == index) {
                temp.data = newValue; // Update the value at the index
                return;
            }
            count++;
            temp = temp.next;
        }

        System.out.println("Index out of range");
    }

    // Traverse the list
    public static void traverse(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " <-> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }

    // Search for an element
    public static boolean search(Node head, int key) {
        Node temp = head;
        while (temp != null) {
            if (temp.data == key) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    // Reverse the list
    public static Node reverse(Node head) {
        Node temp = null;
        Node current = head;

        // Swap next and prev pointers for each node
        while (current != null) {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        }

        // After the loop, temp will be the last node, so update head
        if (temp != null) {
            head = temp.prev;
        }

        return head;
    }

    // Merge two sorted lists
    public static Node merge(Node head1, Node head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        if (head1.data <= head2.data) {
            head1.next = merge(head1.next, head2);
            if (head1.next != null) {
                head1.next.prev = head1;
            }
            return head1;
        } else {
            head2.next = merge(head1, head2.next);
            if (head2.next != null) {
                head2.next.prev = head2;
            }
            return head2;
        }
    }

    // Find the middle of the list
    public static Node middle(Node head) {
        if (head == null) return null;

        Node slow = head;
        Node fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // Sort the list using merge sort
    public static Node sort(Node head) {
        if (head == null || head.next == null) return head;

        // Find the middle node
        Node mid = middle(head);
        Node nextToMid = mid.next;
        mid.next = null;
		
		// Properly break the list into two halves
		if (nextToMid != null) {
			nextToMid.prev = null;  // Set the 'prev' pointer of the second half to null
		}
	
        // Recursively split and sort both halves
        Node left = sort(head);
        Node right = sort(nextToMid);

        // Merge the sorted halves
        return merge(left, right);
    }

    // Get the size of the list
    public static int size(Node head) {
        int count = 0;
        Node temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    // Clear the list
    public static Node clear(Node head) {
        return null;
    }

    // Main method to test
    public static void main(String[] args) {
        Node head = null;

        // Insert elements at the beginning
        head = insertAtBeginning(head, 5);
        head = insertAtBeginning(head, 10);
        head = insertAtBeginning(head, 3);

        System.out.println("List after inserting at the beginning: ");
        traverse(head);

        // Insert element at the end
        head = insertAtEnd(head, 7);
        head = insertAtEnd(head, 2);

        System.out.println("List after inserting at the end: ");
        traverse(head);

        // Insert at a specific position
        head = insertAtPosition(head, 4, 2);
        System.out.println("List after inserting at position 2: ");
        traverse(head);
		    
		    Node second = new Node(20);
		    insertAfterNode(second, 25);
        System.out.println("List after inserting 25 after 20:");
        traverse(head);
        
        head = insertBeforeNode(head, second, 15);
        System.out.println("List after inserting 15 before 20:");
        traverse(head);
		
        // Delete at the beginning
        head = deleteAtBeginning(head);
        System.out.println("List after deleting at the beginning: ");
        traverse(head);

        // Delete at the end
        head = deleteAtEnd(head);
        System.out.println("List after deleting at the end: ");
        traverse(head);

        // Delete at a specific position
        head = deleteAtPosition(head, 2);
        System.out.println("List after deleting at position 2: ");
        traverse(head);

        // Search for an element
        int key = 7;
        if (search(head, key)) {
            System.out.println("Element " + key + " found in the list");
        } else {
            System.out.println("Element " + key + " not found in the list");
        }

        // Reverse the list
        head = reverse(head);
        System.out.println("List after reversing: ");
        traverse(head);

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

        // Sort the list
        head = sort(head);

        System.out.println("Sorted list:");
        traverse(head);

        // Clear the list
        head = clear(head);
        System.out.println("List after clearing: ");
        traverse(head);
    }
}

Here is the Non-Generic singly linked list implementation in C#:

using System;

public class DoublyLinkedList
{
    // Node structure for doubly linked list
    public class Node
    {
        public int data;
        public Node next;
        public Node prev;

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

    // Insert at the beginning
    public static Node InsertAtBeginning(Node head, int data)
    {
        Node newNode = new Node(data);
        newNode.next = head;
        if (head != null)
        {
            head.prev = newNode;
        }
        return newNode;
    }

    // Insert at the end
    public static Node InsertAtEnd(Node head, int data)
    {
        Node newNode = new Node(data);
        if (head == null)
        {
            return newNode;
        }
        Node temp = head;
        while (temp.next != null)
        {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return head;
    }

    // Insert at a specific position
    public static Node InsertAtPosition(Node head, int data, int position)
    {
        Node newNode = new Node(data);
        if (position == 0)
        {
            newNode.next = head;
            if (head != null)
            {
                head.prev = newNode;
            }
            return newNode;
        }

        Node temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++)
        {
            temp = temp.next;
        }

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

        newNode.next = temp.next;
        if (temp.next != null)
        {
            temp.next.prev = newNode;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return head;
    }
	
	// Insert a new node after a given node
	public static Node InsertAfterNode(Node head, int target, int data)
	{
		Node temp = head;
		while (temp != null && temp.data != target)
		{
			temp = temp.next;
		}

		if (temp == null)
		{
			Console.WriteLine($"Node with value {target} not found.");
			return head;
		}

		Node newNode = new Node(data);
		newNode.next = temp.next;
		newNode.prev = temp;
		
		if (temp.next != null)
		{
			temp.next.prev = newNode;
		}
		temp.next = newNode;
		
		return head;
	}

	// Insert a new node before a given node
	public static Node InsertBeforeNode(Node head, int target, int data)
	{
		if (head == null)
		{
			Console.WriteLine("List is empty.");
			return null;
		}

		if (head.data == target)
		{
			return InsertAtBeginning(head, data);
		}

		Node temp = head;
		while (temp != null && temp.data != target)
		{
			temp = temp.next;
		}

		if (temp == null)
		{
			Console.WriteLine($"Node with value {target} not found.");
			return head;
		}

		Node newNode = new Node(data);
		newNode.next = temp;
		newNode.prev = temp.prev;

		if (temp.prev != null)
		{
			temp.prev.next = newNode;
		}
		temp.prev = newNode;

		return head;
	}

    // Delete at the beginning
    public static Node DeleteAtBeginning(Node head)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return null;
        }
        if (head.next != null)
        {
            head.next.prev = null;
        }
        return head.next;
    }

    // Delete at the end
    public static Node DeleteAtEnd(Node head)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return null;
        }

        if (head.next == null)
        {
            return null;
        }

        Node temp = head;
        while (temp.next != null)
        {
            temp = temp.next;
        }
        if (temp.prev != null)
        {
            temp.prev.next = null;
        }
        return head;
    }

    // Delete at a specific position
    public static Node DeleteAtPosition(Node head, int position)
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return null;
        }

        if (position == 0)
        {
            return DeleteAtBeginning(head);
        }

        Node temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++)
        {
            temp = temp.next;
        }

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

        if (temp.next.next != null)
        {
            temp.next.next.prev = temp;
        }
        temp.next = temp.next.next;
        return head;
    }

    // Get element at a specific index
    public static int Get(Node head, int index)
    {
        int count = 0;
        Node temp = head;

        while (temp != null)
        {
            if (count == index)
            {
                return temp.data;
            }
            count++;
            temp = temp.next;
        }

        Console.WriteLine("Index out of range");
        return -1;
    }

    // Set element at a specific index
    public static void Set(Node head, int index, int newValue)
    {
        int count = 0;
        Node temp = head;

        while (temp != null)
        {
            if (count == index)
            {
                temp.data = newValue;
                return;
            }
            count++;
            temp = temp.next;
        }

        Console.WriteLine("Index out of range");
    }

    // Traverse the list
    public static void Traverse(Node head)
    {
        Node temp = head;
        while (temp != null)
        {
            Console.Write(temp.data + " <-> ");
            temp = temp.next;
        }
        Console.WriteLine("NULL");
    }

    // Search for an element
    public static bool Search(Node head, int key)
    {
        Node temp = head;
        while (temp != null)
        {
            if (temp.data == key)
            {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    // Reverse the list
    public static Node Reverse(Node head)
    {
        Node temp = null;
        Node current = head;

        while (current != null)
        {
            temp = current.prev;
            current.prev = current.next;
            current.next = temp;
            current = current.prev;
        }

        if (temp != null)
        {
            head = temp.prev;
        }
        return head;
    }

    // Find the middle of the list
	public static Node Middle(Node head)
	{
		if (head == null) return null;

		Node slow = head, fast = head;
		
		while (fast.next != null && fast.next.next != null)
		{
			slow = slow.next;
			fast = fast.next.next;
		}

		return slow;
	}

	// Sort the list using merge sort
	public static Node Sort(Node head)
	{
		if (head == null || head.next == null) return head;

		Node mid = Middle(head);
		Node nextToMid = mid.next;

		// Properly break the list into two halves
		mid.next = null;
		if (nextToMid != null) 
		{
			nextToMid.prev = null;
		}

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

		return Merge(left, right);
	}

	// Merge two sorted lists
	public static Node Merge(Node head1, Node head2)
	{
		if (head1 == null) return head2;
		if (head2 == null) return head1;

		if (head1.data <= head2.data)
		{
			head1.next = Merge(head1.next, head2);
			if (head1.next != null)
			{
				head1.next.prev = head1;
			}
			return head1;
		}
		else
		{
			head2.next = Merge(head1, head2.next);
			if (head2.next != null)
			{
				head2.next.prev = head2;
			}
			return head2;
		}
	}

    // Get the size of the list
    public static int Size(Node head)
    {
        int count = 0;
        Node temp = head;
        while (temp != null)
        {
            count++;
            temp = temp.next;
        }
        return count;
    }

    // Clear the list
    public static Node Clear(Node head)
    {
        return null;
    }

    // Main method to test
    public static void Main(string[] args)
    {
        Node head = null;

        // Insert elements at the beginning
        head = InsertAtBeginning(head, 5);
        head = InsertAtBeginning(head, 10);
        head = InsertAtBeginning(head, 3);

        Console.WriteLine("List after inserting at the beginning: ");
        Traverse(head);

        // Insert element at the end
        head = InsertAtEnd(head, 7);
        head = InsertAtEnd(head, 2);

        Console.WriteLine("List after inserting at the end: ");
        Traverse(head);

        // Insert at a specific position
        head = InsertAtPosition(head, 4, 2);
        Console.WriteLine("List after inserting at position 2: ");
        Traverse(head);
		
  		head = InsertAfterNode(head, 4, 8);
  		Console.WriteLine("List after inserting 8 after 4:");
  		Traverse(head);
  
  		head = InsertBeforeNode(head, 4, 6);
  		Console.WriteLine("List after inserting 6 before 4:");
  		Traverse(head);

        // Delete at the beginning
        head = DeleteAtBeginning(head);
        Console.WriteLine("List after deleting at the beginning: ");
        Traverse(head);

        // Delete at the end
        head = DeleteAtEnd(head);
        Console.WriteLine("List after deleting at the end: ");
        Traverse(head);

        // Delete at a specific position
        head = DeleteAtPosition(head, 2);
        Console.WriteLine("List after deleting at position 2: ");
        Traverse(head);

        // Search for an element
        int key = 7;
        if (Search(head, key))
        {
            Console.WriteLine("Element " + key + " found in the list");
        }
        else
        {
            Console.WriteLine("Element " + key + " not found in the list");
        }

        // Reverse the list
        head = Reverse(head);
        Console.WriteLine("List after reversing: ");
        Traverse(head);

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

        // Sort the list
        head = Sort(head);

        Console.WriteLine("Sorted list:");
        Traverse(head);

        // Clear the list
        head = Clear(head);
        Console.WriteLine("List after clearing: ");
        Traverse(head);
    }
}

Generic Singly Linked List Implementation

Here is the Generic singly linked list implementation in C:

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

// StackElement structure to hold data and a toString function pointer
typedef struct {
    void* data;           // Pointer to hold the actual data
    char* toString;       // This will be modified to hold the string representation
} StackElement;

// Node structure for doubly linked list
typedef struct Node {
    StackElement element;     // Stack element data
    struct Node* next;        // Pointer to the next node
    struct Node* prev;        // Pointer to the previous node
} Node;

// Function to create a new node
Node* createNode(StackElement element) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->element = element;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Function to insert a node at the beginning of the list
void insertAtBeginning(Node** head, StackElement element) {
    Node* newNode = createNode(element);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    newNode->next = *head;
    (*head)->prev = newNode;
    *head = newNode;
}

// Function to insert a node at the end of the list
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;
    newNode->prev = temp;
}

// Function to insert a node after a given previous node
void insertAfterNode(Node** head, Node* prevNode, StackElement element) {
    if (*head == NULL || prevNode == NULL) {
        printf("The list cannot be empty or the previous node cannot be NULL\n");
        return;
    }

    Node* newNode = createNode(element);
    newNode->next = prevNode->next;
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
    newNode->prev = prevNode;
}

// Function to insert a node before a given next node
void insertBeforeNode(Node** head, Node* nextNode, StackElement element) {
    if (*head == NULL || nextNode == NULL) {
        printf("The list cannot be empty or the next node cannot be NULL\n");
        return;
    }

    Node* newNode = createNode(element);
    newNode->prev = nextNode->prev;
    if (nextNode->prev != NULL) {
        nextNode->prev->next = newNode;
    }
    nextNode->prev = newNode;
    newNode->next = nextNode;

    // If nextNode is the head node
    if (newNode->prev == NULL) {
        *head = newNode;
    }
}

// Function to insert a node at a specific position
void insertAtPosition(Node** head, StackElement element, int position) {
    if (position == 0) {
        insertAtBeginning(head, element);
        return;
    }

    Node* newNode = createNode(element);
    Node* temp = *head;
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Position out of bounds\n");
        free(newNode);
        return;
    }

    newNode->next = temp->next;
    if (temp->next != NULL) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// 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;
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    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;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    if (temp->prev != NULL) {
        temp->prev->next = NULL;
    } else {
        *head = NULL; // Only one element in the list
    }
    free(temp);
}

// 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 (position == 0) {
        *head = temp->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        free(temp);
        return;
    }

    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    if (temp == NULL || temp->next == NULL) {
        printf("Position out of bounds\n");
        return;
    }

    Node* nextNode = temp->next->next;
    if (nextNode != NULL) {
        nextNode->prev = temp;
    }
    free(temp->next);
    temp->next = nextNode;
}

// Function to traverse the list and print all elements
void traverse(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%s <-> ", temp->element.toString);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to reverse the linked list
void reverse(Node** head) {
    Node* temp = NULL;
    Node* current = *head;
    
    while (current != NULL) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }
    
    if (temp != NULL) {
        *head = temp->prev;
    }
}


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

// 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 get the size of the linked list
int size(Node* head) {
    int size = 0;
    Node* temp = head;
    while (temp != NULL) {
        size++;
        temp = temp->next;
    }
    return size;
}

// Function to check if the list is empty
int isEmpty(Node* head) {
    return head == NULL;
}

// Function to access an element at a specific index (0-based)
StackElement get(Node* head, int index) {
    int count = 0;
    Node* temp = head;
    while (temp != NULL) {
        if (count == index)
            return temp->element;
        count++;
        temp = temp->next;
    }
    StackElement emptyElement = {NULL, ""};
    return emptyElement; // Index out of range
}

// Function to set an element at a specific index (0-based)
void set(Node* head, int index, StackElement element) {
    Node* current = head;
    int count = 0;

    // Traverse the list until the specified index
    while (current != NULL) {
        if (count == index) {
            current->element = element;  // Update the node's value
            return;                    // Exit the function after the update
        }
        count++;
        current = current->next;      // Move to the next node
    }
    
    printf("Index out of range\n"); // Handle case where index exceeds list length
}

// Function to merge two lists
void merge(Node** headRef, Node* head1, Node* head2) {
    if (head1 == NULL) {
        while (head2 != NULL) {
            Node* newNode = createNode(head2->element); // Create a new node
            *headRef = newNode;
            headRef = &((*headRef)->next);
            head2 = head2->next;
        }
        return;
    }
    if (head2 == NULL) {
        while (head1 != NULL) {
            Node* newNode = createNode(head1->element); // Create a new node
            *headRef = newNode;
            headRef = &((*headRef)->next);
            head1 = head1->next;
        }
        return;
    }

    if (strcmp(head1->element.toString, head2->element.toString) < 0) {
        Node* newNode = createNode(head1->element); // Create a new node
        *headRef = newNode;
        merge(&((*headRef)->next), head1->next, head2);
        if ((*headRef)->next != NULL) {
            (*headRef)->next->prev = *headRef;
        }
    } else {
        Node* newNode = createNode(head2->element); // Create a new node
        *headRef = newNode;
        merge(&((*headRef)->next), head1, head2->next);
        if ((*headRef)->next != NULL) {
            (*headRef)->next->prev = *headRef;
        }
    }
}

// Function to get the middle of the linked list
void middle(Node* head, Node** middle) {
    if (head == NULL) {
        *middle = NULL; // Set middle node to NULL if list is empty
        return;
    }

    Node* slow = head;
    Node* fast = head->next;

    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    *middle = slow; // Update the middle node
}

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

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

    // Properly handle the 'prev' pointers for a doubly linked list
    if (nextToMid != NULL) {
        nextToMid->prev = NULL;  // Set 'prev' of the second half to null
    }

    // Sort the two halves
    sort(&head);
    sort(&nextToMid);

    // Merge the sorted halves
    merge(headRef, head, nextToMid);
}


struct Car {
    char model[20];
    int year;
};

struct Person {
    char name[20];
    int age;
};

// Main function to test the doubly linked list operations
int main() {
    // Create People
    struct Person alice = {"Alice", 30};
    struct Person john = {"John", 19};
    struct Person albert = {"Albert", 28};
    struct Person robert = {"Robert", 20};

    // Create StackElement for people
    StackElement personElement1 = {&alice, "Person{name:\"Alice\", age:30}"};
    StackElement personElement2 = {&john, "Person{name:\"John\", age:19}"};
    StackElement personElement3 = {&albert, "Person{name:\"Albert\", age:28}"};
    StackElement personElement4 = {&robert, "Person{name:\"Robert\", age:20}"};

    // Initialize Linked List
    Node* personList = NULL;

    // 1. **Insert elements into the list**
    insertAtBeginning(&personList, personElement1);
    insertAtEnd(&personList, personElement2);
    insertAtEnd(&personList, personElement3);
    insertAtEnd(&personList, personElement4);
    printf("\nList after inserting elements:\n");
    traverse(personList);

    // 2. **Insert at a specific position**
    StackElement newElement = {&alice, "Person{name:\"Eve\", age:22}"};
    insertAtPosition(&personList, newElement, 2);
    printf("\nList after inserting at position 2:\n");
    traverse(personList);

    // 3. **Insert before a node**
    insertBeforeNode(&personList, personList->next, newElement);
    printf("\nList after inserting before second node:\n");
    traverse(personList);

    // 4. **Insert after a node**
    insertAfterNode(&personList, personList->next, newElement);
    printf("\nList after inserting after second node:\n");
    traverse(personList);

    // 5. **Delete the first node**
    deleteAtBeginning(&personList);
    printf("\nList after deleting first node:\n");
    traverse(personList);

    // 6. **Delete the last node**
    deleteAtEnd(&personList);
    printf("\nList after deleting last node:\n");
    traverse(personList);

    // 7. **Delete at a specific position**
    deleteAtPosition(&personList, 1);
    printf("\nList after deleting node at position 1:\n");
    traverse(personList);

    // 8. **Search for an element**
    int found = search(personList, personElement3);
    printf("\nSearch result for 'Albert': %s\n", found ? "Found" : "Not Found");

    // 9. **Get size of list**
    printf("\nSize of the list: %d\n", size(personList));

    // 10. **Check if list is empty**
    printf("\nIs the list empty? %s\n", isEmpty(personList) ? "Yes" : "No");

    // 11. **Access an element by index**
    StackElement retrievedElement = get(personList, 1);
    printf("\nElement at index 1: %s\n", retrievedElement.toString);

    // 12. **Modify an element at an index**
    StackElement modifiedElement = {&john, "Person{name:\"Updated John\", age:25}"};
    set(personList, 1, modifiedElement);
    printf("\nList after updating element at index 1:\n");
    traverse(personList);

    // 13. **Sort the linked list**
    printf("\nList before sorting:\n");
    traverse(personList);
    sort(&personList);
    printf("\nList after sorting:\n");
    traverse(personList);

    // 14. **Reverse the linked list**
    reverse(&personList);
    printf("\nList after reversing:\n");
    traverse(personList);

    // 15. **Clear the list**
    clear(&personList);
    printf("\nList after clearing:\n");
    traverse(personList);

    return 0;
}

Here is the Generic singly linked list implementation in C++:

#include <iostream>
#include <string>

using namespace std;

// Node structure for doubly linked list
template <typename T>
struct Node {
    T data;
    Node* next;
    Node* prev; // Add prev pointer

    // Constructor to create a new node
    Node(T data) : data(data), next(nullptr), prev(nullptr) {}
};

// Insert at the beginning
template <typename T>
void insertAtBeginning(Node<T>*& head, T data) {
    Node<T>* newNode = new Node<T>(data);
    newNode->next = head;
    if (head != nullptr) {
        head->prev = newNode;
    }
    head = newNode;
}

// Insert at the end
template <typename T>
void insertAtEnd(Node<T>*& head, T data) {
    Node<T>* newNode = new Node<T>(data);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    Node<T>* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Function to insert a node after a given previous node
template <typename T>
void insertAfterNode(Node<T>* prevNode, T element) {
    if (prevNode == nullptr) {
        cout << "The given previous node cannot be NULL\n";
        return;
    }

    Node<T>* newNode = new Node<T>(element);
    newNode->next = prevNode->next;
    newNode->prev = prevNode;

    if (prevNode->next != nullptr) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
}

// Function to insert a node before a given next node
template <typename T>
void insertBeforeNode(Node<T>*& head, Node<T>* nextNode, T element) {
    if (head == nullptr) {
        cout << "The list cannot be empty\n";
        return;
    }

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

    Node<T>* newNode = new Node<T>(element);
    
    if (head == nextNode) {
        newNode->next = head;
        head->prev = newNode;
        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;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Insert at a specific position
template <typename T>
void insertAtPosition(Node<T>*& head, T data, int position) {
    Node<T>* newNode = new Node<T>(data);
    if (position == 0) {
        newNode->next = head;
        if (head != nullptr) {
            head->prev = newNode;
        }
        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;
    if (temp->next != nullptr) {
        temp->next->prev = newNode;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// Delete at the beginning
template <typename T>
void deleteAtBeginning(Node<T>*& head) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }
    Node<T>* temp = head;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;
    }
    delete temp;
}

// Delete at the end
template <typename T>
void deleteAtEnd(Node<T>*& head) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    if (head->next == nullptr) {
        delete head;
        head = nullptr;
        return;
    }

    Node<T>* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    temp->prev->next = nullptr;
    delete temp;
}

// Delete at a specific position
template <typename T>
void deleteAtPosition(Node<T>*& head, int position) {
    if (head == nullptr) {
        cout << "List is empty\n";
        return;
    }

    if (position == 0) {
        Node<T>* temp = head;
        head = head->next;
        if (head != nullptr) {
            head->prev = nullptr;
        }
        delete temp;
        return;
    }

    Node<T>* temp = head;
    for (int i = 0; i < position - 1 && temp != nullptr; i++) {
        temp = temp->next;
    }

    if (temp == nullptr || temp->next == nullptr) {
        cout << "Position out of bounds\n";
        return;
    }

    Node<T>* nextNode = temp->next->next;
    if (nextNode != nullptr) {
        nextNode->prev = temp;
    }
    delete temp->next;
    temp->next = nextNode;
}

// Traverse the list
template <typename T>
void traverse(Node<T>* head) {
    Node<T>* temp = head;
    while (temp != nullptr) {
        cout << (temp->data).toString() << " <-> ";
        temp = temp->next;
    }
    cout << "NULL\n";
}

// Reverse the list
template <typename T>
void reverse(Node<T>*& head) {
    Node<T>* current = head;
    Node<T>* temp = nullptr;

    // Reverse the next and prev pointers of all nodes
    while (current != nullptr) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }

    // Reset the head to the last node
    if (temp != nullptr) {
        head = temp->prev;
    }
}

// Get the size of the list
template <typename T>
int size(Node<T>* head) {
    int count = 0;
    Node<T>* temp = head;
    while (temp != nullptr) {
        count++;
        temp = temp->next;
    }
    return count;
}

// Function to access an element at a specific index (0-based)
template <typename T>
T get(Node<T>* head, int index) {
    int count = 0;
    Node<T>* temp = head;

    while (temp != nullptr) {
        if (count == index)
            return temp->data; // Return the data at the index
        count++;
        temp = temp->next;
    }

    throw out_of_range("Index out of range"); // Throw exception if index is invalid
}

// Function to set an element at a specific index (0-based)
template <typename T>
void set(Node<T>* head, int index, T element) {
    Node<T>* current = head;
    int count = 0;

    // Traverse the list until the specified index
    while (current != nullptr) {
        if (count == index) {
            current->data = element; // Update the node's value
            return;                  // Exit the function after the update
        }
        count++;
        current = current->next;     // Move to the next node
    }

    throw out_of_range("Index out of range"); // Throw exception if index is invalid
}

template <typename T>
bool search(Node<T>* head, T key) {
    Node<T>* temp = head;
    
    // Traverse the list in the forward direction
    while (temp != nullptr) {
        if (temp->data == key)
            return true;  // Element found
        temp = temp->next;
    }

    // If not found, return false
    return false;
}

// Function to merge two lists
template <typename T>
void merge(Node<T>*& headRef, Node<T>* head1, Node<T>* head2) {
    // Handle base cases for empty lists
    if (head1 == nullptr) {
        headRef = head2;
        return;
    }
    if (head2 == nullptr) {
        headRef = head1;
        return;
    }

    // Merge the two lists based on data comparison (using < operator)
    if (head1->data < head2->data) {
        headRef = head1;
        merge(headRef->next, head1->next, head2);
        // Update the prev pointer of the next node in the merged list
        if (headRef->next != nullptr) {
            headRef->next->prev = headRef;
        }
    } else {
        headRef = head2;
        merge(headRef->next, head1, head2->next);
        // Update the prev pointer of the next node in the merged list
        if (headRef->next != nullptr) {
            headRef->next->prev = headRef;
        }
    }
}

// Function to find the middle node of the linked list
template <typename T>
void middle(Node<T>* head, Node<T>*& mid) {
    if (head == nullptr) {
        mid = nullptr; // Set middle node to nullptr if the list is empty
        return;
    }

    Node<T>* slow = head;
    Node<T>* fast = head->next;

    while (fast != nullptr) {
        fast = fast->next;
        if (fast != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    mid = slow; // Update the middle node
}

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

    Node<T>* mid = nullptr;
    middle(headRef, mid);
    Node<T>* nextToMid = mid->next;
    mid->next = nullptr;
    
    // Properly handle the 'prev' pointers for the second half of the list
    if (nextToMid != nullptr) {
        nextToMid->prev = nullptr;  // Set 'prev' of the second half to null
    }
    
    // Sort the two halves
    sort(headRef);
    sort(nextToMid);

    // Merge the sorted halves
    Node<T>* mergedHead = nullptr;
    merge(mergedHead, headRef, nextToMid);
    headRef = mergedHead; // Update the original head reference
}

// Clear the list
template <typename T>
void clear(Node<T>*& head) {
    Node<T>* current = head;
    while (current != nullptr) {
        Node<T>* next = current->next;
        delete current;
        current = next;
    }
    head = nullptr;
}

// Person class to demonstrate
class Person {
public:
    string name;
    int age;

    Person(string name, int age) : name(name), age(age) {}

    // Define < operator for sorting purposes (sort by name, then by age)
    bool operator<(const Person& other) const {
        if (name == other.name) {
            return age < other.age;  // If names are the same, sort by age
        }
        return name < other.name;  // Otherwise, sort by name
    }
    
    // Overload the equality operator to compare Person objects
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
    
    string toString() const {
        return "Person{name: " + name + ", age: " + to_string(age) + "}";
    }
};

int main() {
    // Create Person objects
    Person alice("Alice", 30);
    Person john("John", 19);
    Person albert("Albert", 28);
    Person robert("Robert", 20);

    // Initialize the linked list
    Node<Person>* head = nullptr;

    // Insert elements into the list
    insertAtBeginning(head, alice);
    insertAtBeginning(head, john);
    insertAtEnd(head, albert);
    insertAtEnd(head, robert);

    cout << "\nList after inserting elements:\n";
    traverse(head);

    // Insert at a specific position
    Person eve("Eve", 22);
    insertAtPosition(head, eve, 2);
    cout << "\nList after inserting at position 2:\n";
    traverse(head);

    // Insert before a node (insert before the second node)
    Node<Person>* secondNode = head->next; // Find the second node
    insertBeforeNode(head, secondNode, eve);
    cout << "\nList after inserting before second node:\n";
    traverse(head);

    // Insert after a node (insert after the second node)
    insertAfterNode(secondNode, eve);  // Insert after the second node
    cout << "\nList after inserting after second node:\n";
    traverse(head);

    // Delete the first node
    deleteAtBeginning(head);
    cout << "\nList after deleting first node:\n";
    traverse(head);

    // Delete the last node
    deleteAtEnd(head);
    cout << "\nList after deleting last node:\n";
    traverse(head);

    // Search for an element
    bool found = search(head, albert);
    cout << "\nSearch result for 'Albert': " << (found ? "Found" : "Not Found") << endl;

    // Get size of the list
    cout << "\nSize of the list: " << size(head) << endl;

    // Get an element
    try {
        Person p = get(head, 2);
        cout << "\nElement at index 2: " << p.toString() << endl;
    } catch (const exception& e) {
        cout << e.what() << endl;
    }

    // Set (modify) an element
    try {
        Person updatedJohn("John", 25);
        set(head, 1, updatedJohn);
        cout << "\nList after modifying index 1:\n";
        traverse(head);
    } catch (const exception& e) {
        cout << e.what() << endl;
    }

    // Sort the linked list (by name first, then by age)
    cout << "\nList before sorting:\n";
    traverse(head);
    sort(head);
    cout << "\nList after sorting:\n";
    traverse(head);
    
    // Clear the list
    clear(head);

    cout << "\nList after clearing:" << endl;
    traverse(head);  // Should print NULL, as the list is cleared
    
    return 0;
}

Here is the Generic singly linked list implementation in Java:

class LinkedList<T> {

    // Node structure for doubly linked list
    static class Node<T> {
        T data;
        Node<T> next;
        Node<T> prev;

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

    // Insert at the beginning
    public static <T> Node<T> insertAtBeginning(Node<T> head, T data) {
        Node<T> newNode = new Node<>(data);
        if (head != null) {
            head.prev = newNode;
        }
        newNode.next = head;
        return newNode;
    }

    // Insert at the end
    public static <T> Node<T> insertAtEnd(Node<T> head, T data) {
        Node<T> newNode = new Node<>(data);
        if (head == null) {
            return newNode;
        }
        Node<T> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return head;
    }

    // Insert at a specific position
    public static <T> Node<T> insertAtPosition(Node<T> head, T data, int position) {
        Node<T> newNode = new Node<>(data);
        if (position == 0) {
            newNode.next = head;
            if (head != null) {
                head.prev = newNode;
            }
            return newNode;
        }

        Node<T> temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }

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

        newNode.next = temp.next;
        if (temp.next != null) {
            temp.next.prev = newNode;
        }
        temp.next = newNode;
        newNode.prev = temp;
        return head;
    }

    // Insert before a specific node
    public static <T> Node<T> insertBeforeNode(Node<T> head, Node<T> targetNode, T data) {
        if (head == null) return null;

        if (head == targetNode) {
            return insertAtBeginning(head, data);
        }

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

        if (temp != null) {
            Node<T> newNode = new Node<>(data);
            newNode.next = temp.next;
            if (temp.next != null) {
                temp.next.prev = newNode;
            }
            temp.next = newNode;
            newNode.prev = temp;
        }
        return head;
    }

    // Insert after a specific node
    public static <T> void insertAfterNode(Node<T> node, T data) {
        if (node == null) return;

        Node<T> newNode = new Node<>(data);
        newNode.next = node.next;
        if (node.next != null) {
            node.next.prev = newNode;
        }
        node.next = newNode;
        newNode.prev = node;
    }

    // Delete at the beginning
    public static <T> Node<T> deleteAtBeginning(Node<T> head) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }
        if (head.next != null) {
            head.next.prev = null;
        }
        return head.next;
    }

    // Delete at the end
    public static <T> Node<T> deleteAtEnd(Node<T> head) {
        if (head == null) {
            System.out.println("List is empty");
            return null;
        }

        if (head.next == null) {
            return null;
        }

        Node<T> temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.prev.next = null;
        return head;
    }

    // Search for an element
    public static <T> boolean search(Node<T> head, T key) {
        Node<T> temp = head;
        while (temp != null) {
            if (temp.data.equals(key)) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    // Get the size of the list
    public static <T> int size(Node<T> head) {
        int count = 0;
        Node<T> temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }

    // Get element at a specific index
    public static <T> T get(Node<T> head, int index) throws Exception {
        int count = 0;
        Node<T> temp = head;

        while (temp != null) {
            if (count == index) {
                return temp.data;
            }
            count++;
            temp = temp.next;
        }

        throw new Exception("Index out of range");
    }

    // Set element at a specific index
    public static <T> void set(Node<T> head, int index, T newValue) throws Exception {
        int count = 0;
        Node<T> temp = head;

        while (temp != null) {
            if (count == index) {
                temp.data = newValue; // Update the value at the index
                return;
            }
            count++;
            temp = temp.next;
        }

        throw new Exception("Index out of range");
    }

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

    // Sort the list
    public static <T extends Comparable<T>> Node<T> sort(Node<T> head) {
        if (head == null || head.next == null) return head;

        Node<T> mid = middle(head);
        Node<T> nextToMid = mid.next;
        mid.next = null;
        
        // Properly handle the 'prev' pointers for a doubly linked list
        if (nextToMid != null) {
            nextToMid.prev = null;  // Set 'prev' of the second half to null
        }
    
        Node<T> left = sort(head);
        Node<T> right = sort(nextToMid);

        return merge(left, right);
    }

    // Merge two sorted lists
    public static <T extends Comparable<T>> Node<T> merge(Node<T> left, Node<T> right) {
        if (left == null) return right;
        if (right == null) return left;

        if (left.data.compareTo(right.data) <= 0) {
            left.next = merge(left.next, right);
            if (left.next != null) {
                left.next.prev = left;
            }
            return left;
        } else {
            right.next = merge(left, right.next);
            if (right.next != null) {
                right.next.prev = right;
            }
            return right;
        }
    }

    // Find the middle of the list
    public static <T> Node<T> middle(Node<T> head) {
        if (head == null) return null;

        Node<T> slow = head;
        Node<T> fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // Clear the list by removing all nodes
    public static <T> void clear(Node<T> head) {
        Node<T> current = head;
        while (current != null) {
            Node<T> next = current.next;
            current.next = null;  // Disconnect the current node
            current.prev = null;  // Disconnect the previous node
            current = next;       // Move to the next node
        }
    }
    
    // Person class
    static class Person implements Comparable<Person> {
        String name;
        int age;

        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }

        @Override
        public String toString() {
            return "Person{name: " + name + ", age: " + age + "}";
        }

        @Override
        public int compareTo(Person other) {
            int nameComparison = this.name.compareTo(other.name);
            if (nameComparison != 0) {
                return nameComparison;
            }
            return Integer.compare(this.age, other.age);
        }
    }

    public static void main(String[] args) {
        // Create Person objects
        Person alice = new Person("Alice", 30);
        Person john = new Person("John", 19);
        Person albert = new Person("Albert", 28);
        Person robert = new Person("Robert", 20);

        // Initialize the linked list
        Node<Person> head = null;

        // Insert elements into the list
        head = insertAtBeginning(head, alice);
        head = insertAtBeginning(head, john);
        head = insertAtEnd(head, albert);
        head = insertAtEnd(head, robert);

        System.out.println("\nList after inserting elements:");
        traverse(head);

        // Insert at a specific position
        Person eve = new Person("Eve", 22);
        head = insertAtPosition(head, eve, 2);
        System.out.println("\nList after inserting at position 2:");
        traverse(head);

        // Insert before a node (insert before the second node)
        Node<Person> secondNode = head.next; // Find the second node
        head = insertBeforeNode(head, secondNode, eve);
        System.out.println("\nList after inserting before second node:");
        traverse(head);

        // Insert after a node (insert after the second node)
        insertAfterNode(secondNode, eve);  // Insert after the second node
        System.out.println("\nList after inserting after second node:");
        traverse(head);

        // Delete the first node
        head = deleteAtBeginning(head);
        System.out.println("\nList after deleting first node:");
        traverse(head);

        // Delete the last node
        head = deleteAtEnd(head);
        System.out.println("\nList after deleting last node:");
        traverse(head);

        // Search for an element
        boolean found = search(head, albert);
        System.out.println("\nSearch result for 'Albert': " + (found ? "Found" : "Not Found"));

        // Get size of the list
        System.out.println("\nSize of the list: " + size(head));

        // Get an element
        try {
            Person p = get(head, 2);
            System.out.println("\nElement at index 2: " + p.toString());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        // Set (modify) an element
        try {
            Person updatedJohn = new Person("John", 25);
            set(head, 1, updatedJohn);
            System.out.println("\nList after modifying index 1:");
            traverse(head);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

        // Sort the linked list (by name first, then by age)
        System.out.println("\nList before sorting:");
        traverse(head);
        head = sort(head);
        System.out.println("\nList after sorting:");
        traverse(head);
        
        // Clear the list
        clear(head);
        System.out.println("After clearing the list:");
        traverse(head);  // This should print "NULL" as the list is now empty
    }
}

Here is the Generic singly linked list implementation in C#:

using System;

class Node<T>
{
    public T Data;
    public Node<T> Next;
    public Node<T> Prev;

    public Node(T data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

class Program
{
    static Node<T> InsertAtBeginning<T>(Node<T> head, T data)
    {
        Node<T> newNode = new Node<T>(data) { Next = head };
        if (head != null) head.Prev = newNode;
        return newNode;
    }

    static Node<T> InsertAtEnd<T>(Node<T> head, T data)
    {
        Node<T> newNode = new Node<T>(data);
        if (head == null) return newNode;
        Node<T> temp = head;
        while (temp.Next != null) temp = temp.Next;
        temp.Next = newNode;
        newNode.Prev = temp;
        return head;
    }

    static Node<T> InsertAtPosition<T>(Node<T> head, T data, int position)
    {
        Node<T> newNode = new Node<T>(data);
        if (position == 0) { newNode.Next = head; if (head != null) head.Prev = newNode; return newNode; }
        Node<T> temp = head;
        for (int i = 0; i < position - 1 && temp != null; i++) temp = temp.Next;
        if (temp == null) { Console.WriteLine("Position out of bounds"); return head; }
        newNode.Next = temp.Next;
        newNode.Prev = temp;
        if (temp.Next != null) temp.Next.Prev = newNode;
        temp.Next = newNode;
        return head;
    }

    static Node<T> InsertBeforeNode<T>(Node<T> head, Node<T> targetNode, T data)
    {
        if (head == null) return null;
        if (head == targetNode) return InsertAtBeginning(head, data);
        Node<T> temp = head;
        while (temp != null && temp.Next != targetNode) temp = temp.Next;
        if (temp != null)
        {
            Node<T> newNode = new Node<T>(data) { Next = temp.Next, Prev = temp };
            if (temp.Next != null) temp.Next.Prev = newNode;
            temp.Next = newNode;
        }
        return head;
    }

    static void InsertAfterNode<T>(Node<T> node, T data)
    {
        if (node == null) return;
        Node<T> newNode = new Node<T>(data) { Next = node.Next, Prev = node };
        if (node.Next != null) node.Next.Prev = newNode;
        node.Next = newNode;
    }

    static Node<T> DeleteAtBeginning<T>(Node<T> head)
    {
        if (head == null) { Console.WriteLine("List is empty"); return null; }
        head = head.Next;
        if (head != null) head.Prev = null;
        return head;
    }

    static Node<T> DeleteAtEnd<T>(Node<T> head)
    {
        if (head == null || head.Next == null) return null;
        Node<T> temp = head;
        while (temp.Next != null) temp = temp.Next;
        temp.Prev.Next = null;
        return head;
    }

    // Search for an element
    static bool Search<T>(Node<T> head, T key)
    {
        Node<T> temp = head;
        while (temp != null)
        {
            if (temp.Data.Equals(key)) return true;
            temp = temp.Next;
        }
        return false;
    }

    // Get size of the list
    static int Size<T>(Node<T> head)
    {
        int count = 0;
        Node<T> temp = head;
        while (temp != null)
        {
            count++;
            temp = temp.Next;
        }
        return count;
    }

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

    // Get an element at specific index
    static T Get<T>(Node<T> head, int index)
    {
        int count = 0;
        Node<T> temp = head;
        while (temp != null)
        {
            if (count == index) return temp.Data;
            count++;
            temp = temp.Next;
        }
        throw new Exception("Index out of range");
    }

    // Set (modify) an element at specific index
    static void Set<T>(Node<T> head, int index, T newValue)
    {
        int count = 0;
        Node<T> temp = head;
        while (temp != null)
        {
            if (count == index)
            {
                temp.Data = newValue;
                return;
            }
            count++;
            temp = temp.Next;
        }
        throw new Exception("Index out of range");
    }
    
    // Sort the linked list (Merge Sort)
    static Node<T> Sort<T>(Node<T> head) where T : IComparable<T>
    {
        if (head == null || head.Next == null) return head;

        // Split the list into two halves
        Node<T> mid = Middle(head);
        Node<T> nextToMid = mid.Next;
        mid.Next = null;
        if (nextToMid != null) nextToMid.Prev = null;

        // Recursively sort both halves
        Node<T> left = Sort(head);
        Node<T> right = Sort(nextToMid);

        // Merge the sorted halves
        return Merge(left, right);
    }

    // Merge two sorted lists
    static Node<T> Merge<T>(Node<T> left, Node<T> right) where T : IComparable<T>
    {
        if (left == null) return right;
        if (right == null) return left;

        if (left.Data.CompareTo(right.Data) <= 0)
        {
            left.Next = Merge(left.Next, right);
            if (left.Next != null) left.Next.Prev = left;
            return left;
        }
        else
        {
            right.Next = Merge(left, right.Next);
            if (right.Next != null) right.Next.Prev = right;
            return right;
        }
    }

    // Find the middle node of the list
    static Node<T> Middle<T>(Node<T> head)
    {
        if (head == null) return null;
        Node<T> slow = head, fast = head.Next;

        while (fast != null && fast.Next != null)
        {
            slow = slow.Next;
            fast = fast.Next.Next;
        }

        return slow;
    }
    
    // Clear the linked list
    static Node<T> Clear<T>(Node<T> head)
    {
        head = null;
        return head;
    }
    
    static void Main()
    {
        // Create Person objects
        Person alice = new Person("Alice", 30);
        Person john = new Person("John", 19);
        Person albert = new Person("Albert", 28);
        Person robert = new Person("Robert", 20);

        // Initialize the linked list
        Node<Person> head = null;

        // Insert elements into the list
        head = InsertAtBeginning(head, alice);
        head = InsertAtBeginning(head, john);
        head = InsertAtEnd(head, albert);
        head = InsertAtEnd(head, robert);

        Console.WriteLine("\nList after inserting elements:");
        Traverse(head);

        // Insert at a specific position
        Person eve = new Person("Eve", 22);
        head = InsertAtPosition(head, eve, 2);
        Console.WriteLine("\nList after inserting at position 2:");
        Traverse(head);

        // Insert before a node (insert before the second node)
        Node<Person> secondNode = head.Next; // Find the second node
        head = InsertBeforeNode(head, secondNode, eve);
        Console.WriteLine("\nList after inserting before second node:");
        Traverse(head);

        // Insert after a node (insert after the second node)
        InsertAfterNode(secondNode, eve);  // Insert after the second node
        Console.WriteLine("\nList after inserting after second node:");
        Traverse(head);

        // Delete the first node
        head = DeleteAtBeginning(head);
        Console.WriteLine("\nList after deleting first node:");
        Traverse(head);

        // Delete the last node
        head = DeleteAtEnd(head);
        Console.WriteLine("\nList after deleting last node:");
        Traverse(head);

        // Search for an element
        bool found = Search(head, albert);
        Console.WriteLine("\nSearch result for 'Albert': " + (found ? "Found" : "Not Found"));

        // Get size of the list
        Console.WriteLine("\nSize of the list: " + Size(head));

        // Get an element
        try
        {
            Person p = Get(head, 2);
            Console.WriteLine("\nElement at index 2: " + p.ToString());
        }
        catch (Exception e)
        {
            Console.WriteLine(e.Message);
        }

        // Set (modify) an element
        try
        {
            Person updatedJohn = new Person("John", 25);
            Set(head, 1, updatedJohn);
            Console.WriteLine("\nList after modifying index 1:");
            Traverse(head);
        }
        catch (Exception e)
        {
            Console.WriteLine(e.Message);
        }

        // Sort the linked list (by name first, then by age)
        Console.WriteLine("\nList before sorting:");
        Traverse(head);
        head = Sort(head);
        Console.WriteLine("\nList after sorting:");
        Traverse(head);
        
        // Clear the list
        head = Clear(head);
        Console.WriteLine("\nList after clearing:");
        Traverse(head);
    }
}

class Person : IComparable<Person>
{
    public string Name;
    public int Age;
    public Person(string name, int age) { Name = name; Age = age; }
    public int CompareTo(Person other)
    {
        // Sort by Name, then Age
        return Name.CompareTo(other.Name) != 0 ? Name.CompareTo(other.Name) : Age.CompareTo(other.Age);
    }
    public override string ToString() => $"Person{{name: {Name}, age: {Age}}}";

}