Linked Lists Data Structure in C++

Linked Lists
A Linked list is a linear data structure, where the linear order is given by means of pointers. Each element of the linked list is known as nodes.
Each node is divided into two parts:

  1. The first part contains the data of the element.
  2. The second part contains the address of the next node in the list (next).

    Traversing a Linked List in C++

    Traversing is the process of displaying all the elements of the linked list. Here, we have traversed the elements of the linked list using functions.

    #include <iostream>
    using namespace std;
    struct node{
        int data;
        struct node*next;
    };
    void traversal(struct node*ptr);
    int main()
    {
    struct node*head,*second,*third;   
    head=new node();
    second=new node();
    third=new node();
    
    head->data=7;
    head->next=second;
    
    second->data=14;
    second->next=third;
    
    third->data=21;
    third->next=NULL;
    
    node *newnode;
    newnode=new node();
    traversal(head);
    cout<<"\n Insert element:";
    cin>>newnode->data;
    newnode->next=head;
    head=newnode; 
    traversal(head);
    return 0;
    }
    void traversal(struct node*ptr)
    {   while(ptr!=NULL)
        {
            cout<<ptr->data<<" ";
            ptr=ptr->next;
    }
    }

    Algorithm for traversing a Linked List

    The variable ptr points to the node currently being processed. The variable head contains the address of the head node of the LIST.
    void traversal(struct node*ptr)
    1.ptr=head (Initialize pointers)
    2. Repeat steps 3 and 4 while PTR!= NULL
    3. Apply the PROCESS to data[PTR].
    4. Set ptr=next[PTR]
    5. Exit


    Insertion in a Linked List in C++

    Insertion is the process of inserting an element in a linked list. In this program, we are inserting elements into the linked list from the end.
    Output:
    Enter data:56
    Do you want to insert another number? (y/n)y
    Enter data:23
    Do you want to insert another number? (y/n)y
    Enter data:96
    Do you want to insert another number? (y/n)n
    Elements in Linked list: 56 23 96

    Insertion into a Linked List in C++

    #include<iostream>
    using namespace std;
    struct node{
    int data;
    node*next;
    };
    int main()
    {
    char ch;
    node *head,*newnode,*temp;
    head = NULL;
    do
    {
    newnode=new node();
    cout<<"\n Enter data:";
    cin>>newnode->data;
    newnode->next=NULL;
    if(head==NULL)
    head=temp=newnode;
    else
    {
    temp->next=newnode;
    temp=newnode;
    }
    cout<<"\n Do you want to insert another number? (y/n)";
    cin>>ch;
    }while(ch=='y');
    temp=head;
    cout<<"\n Elements in Linked list: ";
    while(temp!=NULL)
    {
    cout<<temp->data<<" ";
    temp=temp->next;
    }
    return 0;
    }

    Deletion from a Linked List

    Deletion is the process of deleting an element from the linked list.

    Output:
    Elements of linked list: 7 14 21

    After Deletion
    Elements of linked list:14 21
    #include <iostream>
    using namespace std;
    struct node{
        int data;
        struct node*next;
    };
    void traversal(struct node*ptr);
    int main()
    {
    struct node*head,*second,*third;
    head=new node();
    second=new node();
    third=new node();
    
    head->data=7;
    head->next=second;
    
    second->data=14;
    second->next=third;
    
    third->data=21;
    third->next=NULL;
    
    cout<<”\n Elements of linked list:”;
    traversal(head);
    
    cout<<"\n After Deletion\n";
    cout<<”\n Elements of linked list:”;
    struct node*temp;
        temp=head;
        head=head->next;
        free(temp);
    
    traversal(head);
    return 0;
    }
    void traversal(struct node*ptr)
    {   while(ptr!=NULL)
        {
    
            cout<<ptr->data<<" ";
            ptr=ptr->next;
    }
    }
    Siddharth Jha
    • Hackerrank 5* • Full Stack Developer • Masters in SEO

    Related Posts

    Post a Comment