Linked list

 

Linked list:

A list of items, called nodes, in which the order of the nodes is determined by the address, called the link, stored in each node.

Following are the important terms to understand the concept of Linked List.

·         Link − Each link of a linked list can store a data called an element.

·         Next − Each link of a linked list contains a link to the next link called Next.

Types of Linked List:

Following are the various types of linked list.

·        Simple Linked List − Item navigation is forward only.

·        Doubly Linked List − Items can be navigated forward and backward.

·       Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations of Link List:

·            Insertion Operation- A node is added at start or end of the linklist

·            Deletion Operation- A node is delete at start or end or middle of linklist

·            Reverse Operation-The linklist is reversed

 

Code:

#include <iostream>

using namespace std;

struct Node {

    int data;

    struct Node* next;

};

struct Node* head = NULL;

void insert(int new_data) {

    struct Node* new_node = new Node;

    new_node->data = new_data;

    new_node->next = head;

    head = new_node;

}

void display() {

    struct Node* ptr;

    ptr = head;

    while (ptr != NULL) {

        cout << ptr->data << " ";

        ptr = ptr->next;

    }

}

void insertAfter(int key, int value) {

    Node* newNode = new Node;

    newNode->data = value;

    newNode->next = NULL;

    if (head == NULL) {

        cout << "List is empty. Cannot insert after." << endl;

        return;

    }

    Node* current = head;

    while (current != NULL && current->data != key) {

        current = current->next;

    }

    if (current == NULL) {

        cout << "Key not found in the list." << endl;

    } else {

        newNode->next = current->next;

        current->next = newNode;

    }

}

void deleteNode(int key) {

    Node* current = head;

    Node* prev = NULL;

    if (current != NULL && current->data == key) {

        head = current->next;

        delete current;

        return;

    }

    while (current != NULL && current->data != key) {

        prev = current;

        current = current->next;

    }

    if (current == NULL) {

        cout << "Key not found in the list. Cannot delete." << endl;

        return;

    }

    prev->next = current->next;

    delete current;

}

void reverseList() {

    Node* prev = NULL;

    Node* current = head;

    Node* next = NULL;

    while (current != NULL) {

        next = current->next;

        current->next = prev;

        prev = current;

        current = next;

    }

    head = prev;

}

int main() {

    insert(3);

    insert(1);

    insert(7);

    insert(2);

    insert(9);

    cout << "The linked list is: ";

    display();

    cout << endl;

    int option;

    do {

        int value, target;

        cout << "1. Insert After." << endl;

        cout << "2. Delete." << endl;

        cout << "3. Reverse." << endl;

        cout << "4. Exit." << endl;

        cout << "Enter the option from above: ";

        cin >> option;

        cout << endl;

        switch (option) {

            case 1:

                cout << "Enter the value to be inserted: ";

                cin >> value;

                cout << "Enter the target value: ";

                cin >> target;

                insertAfter(target, value);

                cout << "Updated linked list is: ";

                display();

                cout << endl;

                break;

            case 2:

                cout << "Enter the value to be deleted: ";

                cin >> value;

                deleteNode(value);

                cout << "Updated linked list after deletion: ";

                display();

                cout << endl;

                break;

            case 3:

                reverseList();

                cout << "Reversed linked list: ";

                display();

                cout << endl;

                break;

            case 4:

                cout << "Exiting the program." << endl;

                break;

            default:

                cout << "Invalid option. Please try again." << endl;

        }

    } while (option != 4);

    return 0;

}