Header Linked List in Data Structure: Types & its Applications

A Header Linked List is a type of linked list in data structures that includes an extra node at the beginning, often referred to as the header node. This node is not used to store any data but rather serves as a placeholder to simplify operations like insertion, deletion, and traversal. The header node can make certain operations more efficient and consistent by providing a fixed starting point for the list.

There are 5 types of header linked lists, namely:

• Singly or Doubly Header Linked List
• Ground Header Circular Linked List
• Circular Header Linked List
• Two-way Linked List
• Two-way Circular Linked List

1. Singly or Doubly Header Linked List

A linked list is a linear data structure where elements (called nodes) are stored in memory in such a way that each node contains data and a reference (or link) to the next node in the sequence. 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 type of linked list that has a header node at the beginning and the last node points back to the header node. The header node is a special node that allows access to all the nodes in the 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.

Here are the advantages and disadvantages of using header header-linked list:

Advantages

• The header node allows access to all the nodes in the list.
• Polynomials are often stored in memory as header-linked lists.
• The size can be increased during runtime.
• It allocates memory for the actual data nodes, reducing memory waste compared to arrays.
• This stores global information about the list, such as the total number of nodes, maximum value, or minimum value.

Disadvantages

• Header-linked lists require additional memory for storing pointer information alongside the actual data, leading to increased memory usage.
• Searching for an element in a Header Linked List can be time-consuming, as it may involve traversing from the start to the point of interest, which is not efficient for large lists.
• It can be difficult to traverse a linked list, and it can take a long time to get to a node.
• It can be challenging to reverse-traverse a linked list.

Here are the applications of the header linked list are listed below:

• Simplifying operations on empty lists as a header node (a dummy node) can eliminate the need for special cases when performing operations on empty lists (e.g., insertion, deletion).
• The header node provides a consistent starting point for traversing the list, simplifying iteration even in cases where the list might be empty.
• Used in implementing abstract data types like queues, stacks, or deques where linked lists are used as the underlying storage.
• Header-linked lists are commonly used in polynomial operations (e.g., addition, multiplication) where each term is represented as a node.
• Helps in dynamic memory management by managing memory blocks efficiently, particularly in systems that use free lists.
• Header nodes are useful in the implementation of memory management systems like garbage collection to track blocks of memory.

#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 with no meaningful data (e.g., data = -1)
    list->header = create_node(-1);
    return list;
}

// Function to insert a node at the end of the linked list
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

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

In conclusion, the header linked list provides a reliable and efficient way to manage a linked list by simplifying operations and removing the need for special case handling especially in complex data structures. It is useful for frequent insertion and deletion at the beginning or end of the list.

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.