Header Linked Lists - CSE205: Data Structures and Algorithms | B.Tech CSE Notes PDF | FineNotes4U

One 0

Header Linked List


⭐Types of Header Linked List


1) Grounded Header Linked List:


CODE:

#include <iostream> 
 struct Node { 
    int data; 
    Node* next; 
}; 

// Function to create a new node 
Node* createNode(int value) { 
    Node* newNode = new Node; 
    newNode->data = value; 
    newNode->next = nullptr; 
    return newNode; 
} 
  
// Function to create the header node 
Node* createHeaderNode() { 
    return createNode(0);
} 
  
// Function to insert at the beginning (right after header) 
void insertAtBeginning(Node* header, int value) { 
    Node* newNode = createNode(value); 
    newNode->next = header->next; 
    header->next = newNode; 
} 
  
// Function to insert at the end 
void insertAtEnd(Node* header, int value) { 
    Node* newNode = createNode(value); 
    Node* current = header; 
    while (current->next != nullptr) { 
        current = current->next; 
    } 
    current->next = newNode; 
} 
  
// Function to insert after a given value 
void insertAfterValue(Node* header, int afterValue, int newValue) { 
    Node* current = header->next; 
    while (current != nullptr && current->data != afterValue) { 
        current = current->next; 
    } 
    if (current != nullptr) { 
        Node* newNode = createNode(newValue); 
        newNode->next = current->next; 
        current->next = newNode; 
    } 
    else { 
        std::cout << "Value " << afterValue << " not found in the list." << std::endl; 
    } 
} 
  
// Function to delete from the beginning 
void deleteFromBeginning(Node* header) { 
    if (header->next != nullptr) { 
        Node* temp = header->next; 
        header->next = temp->next; 
        delete temp; 
    } 
    else { 
        std::cout << "List is empty. Cannot delete." << std::endl; 
    } 
} 
  
// Function to delete from the end 
void deleteFromEnd(Node* header) { 
    if (header->next == nullptr) { 
        std::cout << "List is empty. Cannot delete." << std::endl; 
        return; 
    } 
    Node* current = header; 
    while (current->next->next != nullptr) { 
        current = current->next; 
    } 
    delete current->next; 
    current->next = nullptr; 
} 
  
// Function to delete a specific value 
void deleteValue(Node* header, int value) { 
    Node* current = header; 
    while (current->next != nullptr && current->next->data != value) { 
        current = current->next; 
    } 
    if (current->next != nullptr) { 
        Node* temp = current->next; 
        current->next = temp->next; 
        delete temp; 
    } 
    else { 
        std::cout << "Value " << value << " not found in the list." << std::endl; 
    } 
} 
  
// Function to print the list 
void printList(Node* header) { 
    Node* current = header->next; 
    while (current != nullptr) { 
        std::cout << current->data << " "; 
        current = current->next; 
    } 
    std::cout << std::endl; 
} 
  
// Function to free the memory used by the list 
void freeList(Node* header) { 
    Node* current = header; 
    while (current != nullptr) { 
        Node* temp = current; 
        current = current->next; 
        delete temp; 
    } 
} 
  
int main() { 
    Node* header = createHeaderNode(); 
    
    // Insertions 
    insertAtBeginning(header, 1); 
    insertAtEnd(header, 3); 
    insertAfterValue(header, 1, 2); 
    std::cout << "After insertions: "; 
    printList(header);  // Expected: 1 2 3 
  
    // Deletions 
    deleteFromBeginning(header); 
    std::cout << "After deleting from beginning: "; 
    printList(header);  // Expected: 2 3 
    
    insertAtBeginning(header, 1); 
    deleteFromEnd(header); 
    std::cout << "After deleting from end: "; 
    printList(header);  // Expected: 1 2 
    
    insertAtEnd(header, 3); 
    deleteValue(header, 2); 
    std::cout << "After deleting value 2: "; 
    printList(header);  // Expected: 1 3 
    freeList(header); 
    return 0; 
}

OUTPUT:

After insertions: 1 2 3 
After deleting from beginning: 2 3 
After deleting from end: 1 2 
After deleting value 2: 1 3 

2) Circular Header Linked List:


CODE:

#include <iostream> 
 struct Node { 
    int data; 
    Node* next; 
}; 

// Function to create a new node 
Node* createNode(int value) { 
    Node* newNode = new Node; 
    newNode->data = value; 
    newNode->next = nullptr; 
    return newNode; 
} 
  
// Function to create the header node 
Node* createHeaderNode() { 
    Node* header = createNode(0);
    header->next = header;
    return header; 
} 
  
// Function to insert at the beginning (right after header) 
void insertAtBeginning(Node* header, int value) { 
    Node* newNode = createNode(value); 
    newNode->next = header->next; 
    header->next = newNode; 
} 
  
// Function to insert at the end 
void insertAtEnd(Node* header, int value) { 
    Node* newNode = createNode(value); 
    Node* current = header; 
    while (current->next != header) { 
        current = current->next; 
    } 
    newNode->next = header; 
    current->next = newNode; 
} 
  
// Function to insert after a given value 
void insertAfterValue(Node* header, int afterValue, int newValue) { 
    Node* current = header->next; 
    while (current != header && current->data != afterValue) { 
        current = current->next; 
    } 
    if (current != header) { 
        Node* newNode = createNode(newValue); 
        newNode->next = current->next; 
        current->next = newNode; 
    } 
    else { 
        std::cout << "Value " << afterValue << " not found in the list." << std::endl; 
    } 
} 
  
// Function to delete from the beginning 
void deleteFromBeginning(Node* header) { 
    if (header->next != header) { 
        Node* temp = header->next; 
        header->next = temp->next; 
        delete temp; 
    } 
    else { 
        std::cout << "List is empty. Cannot delete." << std::endl; 
    } 
} 
  
// Function to delete from the end 
void deleteFromEnd(Node* header) { 
    if (header->next == header) { 
        std::cout << "List is empty. Cannot delete." << std::endl; 
        return; 
    } 
    Node* current = header; 
    while (current->next->next != header) { 
        current = current->next; 
    } 
    Node* temp = current->next; 
    current->next = header; 
    delete temp; 
} 
  
// Function to delete a specific value 
void deleteValue(Node* header, int value) { 
    if (header->next == header) { 
        std::cout << "List is empty. Cannot delete." << std::endl; 
        return; 
    } 
    Node* current = header; 
    while (current->next != header && current->next->data != value) { 
        current = current->next; 
    } 
    if (current->next != header) { 
        Node* temp = current->next; 
        current->next = temp->next; 
        delete temp; 
    } 
    else { 
        std::cout << "Value " << value << " not found in the list." << std::endl; 
    } 
} 
  
// Function to print the list 
void printList(Node* header) { 
    if (header->next == header) { 
        std::cout << "List is empty." << std::endl; 
        return; 
    } 
    Node* current = header->next; 
    while (current != header) { 
        std::cout << current->data << " "; 
        current = current->next; 
    } 
    std::cout << std::endl; 
}

// Function to free the memory used by the list 
void freeList(Node* header) { 
    if (header->next == header) { 
        delete header; 
        return; 
    } 
    Node* current = header->next; 
    while (current != header) { 
        Node* temp = current; 
        current = current->next; 
        delete temp; 
    } 
    delete header; 
} 
  
int main() { 
    Node* header = createHeaderNode(); 
    
    // Insertions 
    insertAtBeginning(header, 3); 
    insertAtBeginning(header, 2); 
    insertAtBeginning(header, 1); 
    std::cout << "After insertions at beginning: "; 
    printList(header);  // Expected: 1 2 3 
  
    insertAtEnd(header, 4); 
    insertAtEnd(header, 5); 
    std::cout << "After insertions at end: "; 
    printList(header);  // Expected: 1 2 3 4 5 
  
    insertAfterValue(header, 3, 6); 
    std::cout << "After inserting 6 after 3: "; 
    printList(header);  // Expected: 1 2 3 6 4 5 
  
    // Deletions 
    deleteFromBeginning(header); 
    std::cout << "After deleting from beginning: "; 
    printList(header);  // Expected: 2 3 6 4 5 
  
    deleteFromEnd(header); 
    std::cout << "After deleting from end: "; 
    printList(header);  // Expected: 2 3 6 4 
  
    deleteValue(header, 6); 
    std::cout << "After deleting value 6: "; 
    printList(header);  // Expected: 2 3 4 
    freeList(header); 
    return 0; 
}

OUTPUT:

After insertions at beginning: 1 2 3 
After insertions at end: 1 2 3 4 5 
After inserting 6 after 3: 1 2 3 6 4 5 
After deleting from beginning: 2 3 6 4 5 
After deleting from end: 2 3 6 4 
After deleting value 6: 2 3 4 

🚨Thanks for visiting finenotes4u✨

Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.

💗 Bookmark our site to stay connected and never miss an update!

💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍

Tags

Post a Comment

Post a Comment

Previous Post Next Post