Header Linked List in Data Structure: Types & its Applications

1. Singly or Doubly Header Linked List

Each node in a linked list, which is a linear data structure, has both data and a reference (or link) to the node after it in the sequence. These nodes are kept in memory. Linked lists can be classified into singly linked lists and doubly linked lists, based on how the nodes are linked to each other.

2. Ground Header Linked List

A grounded header linked list is a linked list where the last node points to null. It is a type of header-linked list with a special node at the beginning, called the header node. The header node allows access to all nodes in the list and does not need to represent the same data type as other nodes.

3. Circular Header Linked List

A circular header linked list is a header-linked list that has a header node at the beginning of the list and the last node points to the header node. This header node is a special node the header node gives access to all the nodes in the linked list.

4. Two-way Linked List

A Two-Way Header Linked List is a variation of the doubly linked list where there is a special header node that serves as an anchor for both directions (forward and backward) of traversal.

5. Circular Two-way Linked List

A Circular Two-Way Header Linked List combines features from both circular lists and doubly linked lists. It has a header node, and both the next and previous pointers of the nodes are used. Additionally, the list is circular, meaning the last node's next pointer links back to the header, and the first node's previous pointer links back to the header as well.

Below are the advantages and disadvantages of the header-linked list:

Advantages

1. The header node allows access to all the nodes in the header-linked list.

2. The polynomial is often stored in memory as a header-linked list.

3. The size of the header-linked list can be increased at run time.

4. The header-linked list allocates memory for the actual data nodes with less wasted memory than an array.

5. The header node stores global information about the header-linked list - e.g., total number of nodes, max value, min value, etc.

Disadvantages

1. Header-linked lists use more memory because they maintain  pointer information with the values in the node.

2. If you want to find an element in a Header linked List, it will take a long time to find that requirement since you may have to start from the head to that point, and in a large list, it's not efficient.

3. It can be much harder to traverse a linked list; the time it takes can seem forever, just to get to a node.

4. It is hard to reverse-traverse a linked list.

Here are some common uses for the header linked list:

• Simplifying operations on empty lists as a header node (or dummy node) can make it easier to separate when performing operations (insertion, deletion) on empty lists. 
• The header node allows for a consistent starting point to traverse through the list, making iteration easier even in cases when the list might be empty.
• Used when implementing abstract data types such as queues, stacks, or deques with a linked list as the underlying storage.
• Commonly used in polynomial operations (e.g. addition, multiplication) where each term is a node of the linked list.
• All dynamic memory management relies on header and free-list linked lists for managing free memory blocks, especially in systems that use free-lists.
• In order to maintain track of allocated memory blocks, header nodes are helpful for designing memory management systems (such as garbage collection).

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

// Definition of the node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Definition of the linked list with a header node
typedef struct LinkedList {
    Node* header;
} LinkedList;

// Function to create a new node
Node* create_node(int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

LinkedList* create_list() {
    LinkedList* list = (LinkedList*)malloc(sizeof(LinkedList));
    if (list == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    // Creating a header node without any meaningful data (data = -1)
    list->header = create_node(-1);
    return list;
}

// You add a node to the end of the linked list using this function.
void insert_end(LinkedList* list, int data) {
    Node* new_node = create_node(data);
    Node* temp = list->header;

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

    // Insert the new node at the end
    temp->next = new_node;
}

// Function to display the list
void display_list(LinkedList* list) {
    Node* temp = list->header->next;  // Skip the header node
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Function to delete a node by its value
void delete_node(LinkedList* list, int value) {
    Node* temp = list->header;
    while (temp->next != NULL && temp->next->data != value) {
        temp = temp->next;
    }

    if (temp->next != NULL) {
        Node* to_delete = temp->next;
        temp->next = temp->next->next;
        free(to_delete);
        printf("Node with value %d deleted.\n", value);
    } else {
        printf("Node with value %d not found.\n", value);
    }
}

// Function to free the entire list
void free_list(LinkedList* list) {
    Node* temp = list->header;
    while (temp != NULL) {
        Node* next = temp->next;
         free(temp);
        temp = next;
    }
    free(list);
}

int main() {
    // Create a new list
    LinkedList* list = create_list();

    // Insert elements into the list
    insert_end(list, 10);
    insert_end(list, 30);
    insert_end(list, 40);
    insert_end(list, 50);

    // Display the list
    printf("Linked List: ");
    display_list(list);

    // Delete a node
    delete_node(list, 30);
    printf("Linked List after deletion: ");
    display_list(list);

    // Free the list memory
    free_list(list);

    return 0;
}

Output

The Linked List: 10 -> 30 -> 40 -> 50 -> NULL
Node with value 30 deleted.
The Linked List after deletion: 10 -> 40 -> 50 -> NULL

To summarize, the header linked list is a robust strategy for maintaining a linked list which eases the functions which can eliminate the need for simple cases especially when handling difficult structures. The header linked list in data structure is advantageous when you need to perform frequent insertion and deletion at the head or tail.

1. What is the role of the header node in the linked list?

The header node in the linked list is used to simplify operations such as insertion, deletion, and traversal. It eliminates the need to check for any special cases such as an empty list.

2. Can a header-linked list be useful in a circular or doubly linked list?

Yes, header nodes are useful in circular or doubly linked lists to simplify the traversal and manipulation of the nodes.