Mastering Linked List Operations: A Comprehensive Guide with C++ Code

Introduction:

This C++ code demonstrates various operations on a singly linked list. A linked list is a data structure composed of nodes, each containing data and a reference to the next node in the sequence. The code covers operations like inserting nodes at the end, start, and middle of the linked list, searching for a value, and deleting nodes.

 

#include 

using namespace std;
struct node
{
    int data;
    struct node *next;
};

int main()
{
    node *head;
    node *temp;
    node *last;

    last=0;
    int choice;

   do
    {
        temp=new node();
        cout<<"Enter values in a node:"<<endl; cin>>temp->data;
        if(last==0)
        {
            head=last=temp;

        }
        else
        {
            last->next=temp;
            last=temp;
        }
        cout<<"Enter your choice:"<<endl; cin>>choice;
    }while(choice==1);

        last->next=0;
        temp=head;

        while(temp!=0)
        {
            cout<data<<" "; temp=temp->next;
        }
        /************insertion at the start of the node***************************/
        do{
        temp=new node();
        cout<<"Enter value at the start of the node: "<<endl; cin>>temp->data;

        temp->next=head;
        head=temp;

        cout<<"Enter your choice: "<<endl; cin>>choice;
        }while(choice==1);

        temp=head;
        while(temp!=0)
        {
            cout<data<<" "; temp=temp->next;

        }

        /************** iNSERTION AT MIDDLE OF THE LINKLIST***********/
        node *temp2;
        int location=0;

        cout<<"\n Enter your location"<<endl; cin>>location;

        temp=new node();
        cout<<"\n Enter data in node: "<<endl; cin>>temp->data;

        temp2=head;

        while(location-1>0)
        {
            location--;
            temp2=temp2->next;
        }
        temp->next=temp2->next;
        temp2->next=temp;

        temp=head;
        while(temp!=0)
        {
            cout<data<<" "; temp=temp->next;
        }

    /**************************Search traverse*************/
    int value;
    int count=1;
    int flag=0;
    cout<<"\n Enter value you want to search in LinkList: "<<endl; cin>>value;
    temp=head;
    while(temp!=0)
    {
        if(temp->data==value)
        {
            cout<<"Data found successfully at index "<<count<<endl; flag=1; break; } else { temp=temp->next;
            count++;
        }
    }

    if(flag==0)
    {
        cout<<"Data not found"<<endl;
    }
    /**************************deleting node******************/
    int b=0;
    int item;
    node *temp3;
    cout<<"which data do you want to delete?"<<endl; cin>>item;
    temp=head;
    while(temp->next->next!=0)
    {
        if(temp->next->data==item)
        {
            cout<<"Data found successfully"<<endl; b=1; break; } else { temp=temp->next;
            temp3=temp->next;
        }
    }

    if(b==0)
    {
        cout<<"Data not found"<<endl; } else { temp->next=temp->next->next;
        delete temp3;
    }

    temp=head;
        while(temp!=0)
        {
            cout<data<<" "; temp=temp->next;
        }


    return 0;
}

 

Steps:

1. Node Structure Definition: A node structure is defined to hold an integer data and a pointer next to the next node.
2. Main Function:
   • head, temp, and last are declared as pointers to nodes. last is initialized to 0 (null).
   • choice is declared to control the execution of the main loop.
3. Main Loop for Inserting at the End:
   • A loop (do-while) allows the user to input values for nodes.
   • A new node temp is created, and its data is input.
   • If last is null, the new node becomes the head and last.
   • Otherwise, the new node is attached to the last node’s next pointer, and last is updated.
   • The user is prompted to continue or exit.
4. Display Linked List:
   • The loop is exited when the user chooses to stop.
   • last->next is set to null to terminate the linked list.
   • A new pointer temp is set to head.
   • A loop traverses the linked list and prints the data of each node.
5. Insertion at the Start:
   • Another loop (do-while) allows the user to insert nodes at the start.
   • Similar to end insertion, a new node temp is created and its data is input.
   • The new node next points to the current, and head is updated to the new node.
   • The user is prompted to continue or exit.
6. Display Linked List after Start Insertion:
   • The loop is exited when the user chooses to stop.
   • The updated linked list is displayed using the same traversal mechanism.
7. Insertion in the Middle:
   • The user inputs the location where they want to insert the node.
   • A new node temp is created with the given data.
   • A pointer temp2 is set to head.
   • A loop advances temp2 to the node before the desired location.
   • The new node’s next is set to temp2‘s original next, and temp2‘s next points to the new node.
8. Display Linked List after Middle Insertion:
   • The updated linked list is displayed again.
9. Search Operation:
   • The user inputs a value to search for in the linked list.
   • A loop traverses the linked list, counting the nodes.
   • If the desired value is found, its index is displayed and flag is set.
   • If not found, an appropriate message is displayed.
10. Deletion Operation:
    • User inputs an item to be deleted from the linked list.
    • A loop searches for the item.
    • If found, the preceding node’s next pointer is adjusted to skip the node to be deleted.
    • The memory of the deleted node is released using delete.
11. Display Linked List after Deletion:
    • The updated linked list is displayed again.

Conclusion:

This C++ code illustrates the implementation of basic singly linked list operations, including insertion at the end, start, and middle, searching for a value, and deleting nodes. It provides an example of managing dynamic data structures using pointers and dynamic memory allocation.

FAQs:

1. What is a linked list? A linked list is a data structure consisting of a sequence of elements called nodes, where each node contains data and a reference (or pointer) to the next node.
2. Why is dynamic memory used in linked lists? Linked lists allow for efficient dynamic memory allocation, enabling the creation and deletion of nodes as needed, which is especially useful when the size of the list changes frequently.
3. What’s the purpose of the last pointer? The last pointer keeps track of the last node in the linked list. This facilitates efficient insertion at the end without traversing the entire list each time.
4. Why is the first loop structured as a do-while loop? The do-while loop ensures that the insertion process runs at least once, allowing the creation of the initial node. Subsequent insertions are controlled by the user’s choice.
5. Why is deletion handled differently from insertion? Deletion requires locating the node to be deleted and adjusting pointers in the previous node. It involves memory deallocation, which is not required during insertion.