Program for Single Linked List Data Structure in C++ and Algorithm

Linked list is linear data structure which contains a group of nodes and are sequentially arranged . Nodes are composed of data and address of the next node or reference of the next node . These nodes are sequentially or Linearly array that is why the Linked list is a Linear data structure . In Linked List we start with a node and create nodes and link to starting node in order and sequentially . Also the address Pointer field of the Last node must be assigned to NULL . There are single Linked List , Double Linked list , circular Linked list and so on . In this Post I will be discussing about Single Linked List .
Inserting an element and deleting an element into linkedlist takes O(1) order of 1 unit of time . Elements can be inserted any where in the linkedlist and any node can be deleted . Similar to Stacks and Queue's Insertion and deletion are the operations performed to insert an element and to delete an element from the linked list .

Also check : Program for Stack Data Structurein C++

Inserting a node or element into Linkedlist :

Inserting an element into linked list contains 3 types .
1. Insertion at beginning of the Linked list
2. Insertion at the middle of the linked list
3. Insertion at the end of the linked list 

1. Insertion at beginning of the Linked list :

An element can be inserted at the beginning of the Linked list by creating a new node at the beginning of the linked list and inserting an element into the node and assigning the address of the address of the next node or assigning the reference of the next node .

2. Insertion at the middle of the linked list :

An element can be inserted at the middle of the linked list . We need to know the data or element of the neighbouring element to insert an element at middle .

3. Insertion at the End of the linked list :

An element can be inserted at the end by simply traversing the node to the end and creating a new node at the end . Also the address pointer of the new node must be assigned to NULL .

Deleting a node from the Linked list .

Deleting an element is similar to pop operation in Stack and Queue . A node can be deleted in 3 ways similar to Insertion .
1. Deleting a Node from the beginning of the Linked List
2. Deleting a node from the middle of the Linked list.
3. Deleting a node from the end of the Linked List .

Program for Linked list in C++

#include<iostream>
using namespace std;
class node
{
public :
    int d; //data
    node *p; // contains the address of the next node
};
class linked
{

public :
    node *start;
public :
    linked()
    {
        start=NULL;
    }
    void insert_at_beg();
    void insert_at_mid();
    void insert_at_end();
    int remove();
    void display();
};
void linked :: insert_at_end()
{
    node *temp;
    if(start==NULL)
    {
        start=new node [1];
        start->p=NULL;
        cout<<"\n Enter Data to insert \n";
        cin>>start->d;
    }
    else
    {
        temp=start;
        while(temp->p!=NULL)
            temp=temp->p;
        temp->p= new node [1];
        temp=temp->p;
        cout<<"\n Enter Data to insert \n";
        cin>>temp->d;
        temp->p=NULL;
    }
}
void linked :: insert_at_mid()
{
    node *temp,*next;
    int x;
    temp=start;
    cout<<"\n Enter the Neighbour element \n";
    cin>>x;
    while(temp->d!=x)
        temp=temp->p;
    next=temp->p;
    temp->p=new node [1];
    temp=temp->p;
    temp->p=next;
    cout<<"\n Enter data to insert \n";
    cin>>temp->d;
}
void linked :: insert_at_beg()
{
    node *temp;
    temp=new node [1];
    temp->p=start;
    start=temp;
    cout<<"\n Enter element to insert \n";
    cin>>temp->d;
}
int linked :: remove()
{
    node *temp,*prev;
    int x;
    if(start==NULL)
    {
        cout<<"\n Underflow -- No element to Delete \n";
        return 0;
    }
    cout<<"\n Enter element to delete \n";
    cin>>x;
    if(start->d==x && start->p==NULL)
    {
        delete start;
        start=NULL;
        cout<<"\n Deletion successfull \n";
        return 0;
    }
    if(start->d==x)
    {
        temp=start->p;
        delete start;
        start=temp;
        cout<<"\n Deletion Successfull \n";
        return 0;
    }
    temp=start;
    while(temp->d!=x)
    {
        prev=temp;
        temp=temp->p;
    }
    prev->p=temp->p;
    cout<<"\n Deletion Successfull \n";
    return x;
}
void linked :: display()
{
    node *temp;
    temp=start;
    cout<<"\n Linked List elements are \n";
    while(temp->p!=NULL)
    {
        cout<<""<<temp->d<<" ";
        temp=temp->p;
    }
    cout<<temp->d<<endl;
}
int main()
{
    int n=0,a;
    linked l;
    do
    {
        cout<<"\n ************** M E N U **************\n";
        cout<<"\n1.Insert at beginning\n2.Insert at middle\n3.Insert at end\n4.Delete\n5.Display elements";
        cout<<"\n6.Exit\n";
        cout<<"Enter option \n";
        cin>>a;
        switch(a)
        {
        case 1:
            l.insert_at_beg();
            break;
        case 2:
            l.insert_at_mid();
            break;
        case 3:
            l.insert_at_end();
            break;
        case 4:
            l.remove();
            break;
        case 5:
            l.display();
            break;
        case 6:
            n=1;
            break;
        default :
            cout<<"\n Invalid Entry \n";
            break;
        }
    }while(n!=1);
    return 0;
} 

The Output of the above Program :

 
Also check : Program for Queue Data Structure in C++

Advantages of Linked Lists over Stacks and Queues :

1. In stacks and Queues we have Underflow and Overflow where as in Linked list we have only Underflow condition .
2. In stacks and Queues the size of the Stack or Queue need to be specified . In Linked list the size of the Linked list is user choice and it can be decided at run time .
3. Inserting an element in Stack and Queue can be performed only at the ends where as in Linked list an element can be inserted any where in the linked list .


If I had missed anything please get it to me through comments . Also share your logic and your idea to approach the program in the best way through comments .