Linked Lists with applications in C++

0
521
Fractional Calculator in C++
Classes with applications in C++

In computer science, linked lists are data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.Understand linked lists from below image:

untitled

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation. The principal benefit of linked lists over a conventional arrays is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the linked lists, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.On the other hand, simple linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the linked lists structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most or all of the linked lists elements.

For more details about the linked lists look at  the below example explained with comments simultaneously:

    //Linked Lists in C++, Simplest data structure.
    #include<iostream>
    using namespace std;
    // declare the Node structure.
    struct Node {
        int data;
        Node *link;
    };
    /*Function adds a new node at the front end of linked lists */
    void AddAtFront(Node *&head, Node*&tail) {
     
        Node *var = new Node;
        cout << " Enter the Value of Element: ";     cin >> var->data;
     
        if (head == NULL && tail == NULL) // first element, linked lists is empty
                {
            head = var; // our head and tail will be pointing to the same Node.
            tail = var; // head=tail=var;
        } else {
            var->link = head; // first chain the existing head to the current newly created node
     
            head = var; // update the head information
        }
    }
    /*Function adds a new node at the back end of linked lists */
    void AddAtBack(Node *&head, Node*&tail) {
        Node *var = new Node;
        cout << " Enter the Value of Element: ";     cin >> var->data;
     
        if (head == NULL && tail == NULL) // first element, linked lists is empty
                {
            head = var; // our head and tail will be pointing to the same Node.
            tail = var; // head=tail=var;
        } else {
            tail->link = var; // first, chain the new node to the tail of existing list
     
            tail = var; // update the tail information,
        }
    }
     
    void PrintList(Node *&head, Node*&tail)
    /*Print the link list starting from the head to tail*/{
        if (head == NULL && tail == NULL) // linked lists is empty
                {
            cout << "n List is empty, so displaying nothing";
            return;
        }
        Node *currNode = head; // start from the head node.
        int count = 0;
        do { // loop from head to tail
             // first, displ
            cout << "n Node Number = " << ++count << " Has data ="
                    << currNode->data;
            currNode = currNode->link; //update the currNode such that it points to next node now.
        } while (currNode != 0); // stop if currNode == 0 because we have reached at the end of list..
    }
     
    void DeleteFromFront(Node *&head, Node*&tail)
    /*Function delete an existing node from the front
     * We Perform reverse procedure of AddatFront*/{
     
        if (head == NULL && tail == NULL) // first element, linked lists is empty
                {
            cout << "n Sorry, List is empty cannot delete from front";
     
        } else if (head == tail) {
            // there is only single element in the list
            Node *var = head;
            head = NULL;
            tail = NULL;
            cout << " n Deleted Node has following data --->" << var->data;
            delete var; // delete the data pointed by var
        } else {
            Node *var = head;
            head = head->link; // move the head one node forward
            cout << " n Deleted Node has following data --->" << var->data;
            delete var; // delete the previous head node...
        }
    }
     
    void DeleteFromBack(Node *&head, Node*&tail)
    /*Function delete an existing node from back
     * We Perform reverse procedure of AddatBack*/{
     
        if (head == NULL && tail == NULL) // first element, linked lists is empty
                {
            cout << "n Sorry, List is empty cannot delete from back";
     
        } else if (head == tail) {
            // there is only single element in the list
            Node *var = head;
            head = NULL;
            tail = NULL;
            cout << " n Deleted Node has following data --->" << var->data;
            delete var; // delete the data pointed by var
        } else {
            Node *currNode = head; // start from the head node from the head
            while (currNode->link != tail) // move current node until it link to the end node..
                currNode = currNode->link;
            Node *var = tail;
            currNode->link = NULL; // first put null to next link.
            tail = currNode; // update the tail..
            cout << " n Deleted Node has following data --->" << var->data;
            delete var; // delete the old tail node..
        }
    }
     
    //
    int main(void) {
        Node *head, *tail;
        head = NULL;
        tail = NULL; // both head and tail initially points to NULL
        int choice = 0;
        while (1) {
            cout << "n --------------MENU ------------ " << endl
                    << " Press 1. To Enter at the Front " << endl
                    << " Press 2. To Enter at the Back" << endl
                    << " Press 3. To Delete from the Front " << endl
                    << " Press 4. To Delete from the Back" << endl
                    << " Press 5. To Print the Complete List from head to tail"
                    << endl << " Press 6: To Exit" << endl
                    << "n ------------------------------- " << endl
                    << "Your Choice :";         cin >> choice;
            switch (choice) {
            case 1:
                AddAtFront(head, tail);
                break;
            case 2:
                AddAtBack(head, tail);
                break;
            case 3:
                DeleteFromFront(head, tail);
                break;
            case 4:
                DeleteFromBack(head, tail);
                break;
            case 5:
                PrintList(head, tail);
                break;
            case 6:
                cout << " n Exiting .... " << endl;
                return 0;
            default:
                cout << "n Invalid Option, Please use any of the listed options"
                        << endl;
            }
     
        }
    }

As mentioned in the comments above, we can move forward through a node and reach to the required node in linked lists and do whatever we want with the required node. The link lists have the simplest logic for doing any kind of operation with it, that is why linked lists are considered the most simple data structure by programmers. You can see the function for every operation in the above linked lists.

Fractional Calculator in C++
Classes with applications in C++

Leave a Reply