A two-way header list, also known as a doubly linked list with header nodes, is a variation of a doubly linked list that includes additional header nodes at both ends of the list. These header nodes simplify the implementation by providing a placeholder for the start and end of the list, which can help in handling edge cases.
Here’s an implementation of a doubly linked list with header nodes in C, including traversal and searching:
 // Node structure
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf(“Memory allocation failed\n”);
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node at the beginning of the list
void insertAtBeginning(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = (*head)->next;
if ((*head)->next != NULL) {
(*head)->next->prev = newNode;
}
(*head)->next = newNode;
newNode->prev = *head;
}
// Function to insert a new node at the end of the list
void insertAtEnd(Node** head, int data) {
Node* newNode = createNode(data);
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
// Function to display the linked list
void displayList(Node* head) {
Node* current = head->next;
printf(“Linked List: “);
while (current != NULL) {
printf(“%d -> “, current->data);
current = current->next;
}
printf(“NULL\n”);
}
// Function to search for a value in the linked list
Node* search(Node* head, int key) {
Node* current = head->next;
while (current != NULL && current->data != key) {
current = current->next;
}
return current;
}
int main() {
// Creating header nodes
Node* head = createNode(-1); // Head node
Node* tail = createNode(-1); // Tail node
head->next = tail;
tail->prev = head;
// Inserting nodes
insertAtBeginning(&head, 10);
insertAtBeginning(&head, 20);
insertAtEnd(&head, 30);
// Displaying the linked list
displayList(head);
// Searching for a value
int key = 20;
Node* result = search(head, key);
if (result != NULL) {
printf(“%d found in the list\n”, key);
} else {
printf(“%d not found in the list\n”, key);
}
// Freeing memory
Node* current = head;
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
return 0;
}
In this implementation:
- Each node has a data part and two pointers:
prevto the previous node andnextto the next node. - The
insertAtBeginningfunction inserts a new node at the beginning of the list, and theinsertAtEndfunction inserts a new node at the end of the list. - The
displayListfunction traverses the list from the head to the tail, printing each node’s data. - The
searchfunction searches for a value in the list and returns a pointer to the node containing the value if found, orNULLotherwise.
This implementation demonstrates how to create, traverse, and search a doubly linked list with header nodes.