C++ program to implement singly linked list

C++ program to perform various operations such as creation, insertion, deletion, search, display,count number of nodes, erase on singly linked list.

C++ program to implement various list operations using arrays

Following program is to show that how list can be represented using arrays

#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
typedef struct link
{
    int data;
    int next;
}link;
class arraylink
{
    link ar[10];
    int start;
public:
    arraylink()
    {
        for(int i=0;i<10;i++)
            ar[i].data=-1;
    }
    void create();
    void insert();
    void delet();
    void search();
    void display();
};
void arraylink::create()
{
    int i;
    for(i=0;i<10;i++)
        ar[i].data=-1;
    cout<<"Enter the index for first element ";
    cin>>start;
    i=start;
    while(i!=-1)
    {
        cout<<"Enter the data and the index of next element ";
        cin>>ar[i].data>>ar[i].next;
        i=ar[i].next;
    }
}
void arraylink::display()
{
    int i=start;
    while(i!=-1)
    {
        cout<<ar[i].data<<" ";
        i=ar[i].next;
    }
    cout<<"Null"<<endl;

}
void arraylink::insert()
{
    char choice;
    int sert,af,y=0,i=start;
    display();
    cout<<"\nEnter the data to be inserted ";
    cin>>sert;
    while(ar[y].data!=-1)
       y++;
    ar[y].data=sert;
    cout<<"\nWant to insert data at first node (Y/N) ";
    choice=getch();
    cout<<endl;
    if(choice=='Y'||choice=='y')
    {
        ar[y].next=start;
        start=y;
    }
    else
    {
        cout<<"Enter the data after which you want to insert ";
        cin>>af;
        while(ar[i].data!=af)
            i=ar[i].next;
        ar[y].next=ar[i].next;
        ar[i].next=y;
    }
    display();
}
void arraylink::delet()
{
    int del,y,i=start;
    display();
    cout<<"Enter the element to be deleted ";
    cin>>del;
    while(ar[i].data!=del)
         i=ar[i].next;
    if(i==start)
         start=ar[i].next;
    else
    {
        y=start;
        while(ar[y].next!=i)
            y=ar[y].next;
        ar[y].next=ar[i].next;
    }
    ar[i].data=-1;
    display();
}
void arraylink::search()
{
    int se,i=start;
    cout<<"\nEnter the element to be searched";
    cin>>se;
    while(ar[i].data!=se)
    {
       if(ar[i].next==-1)
       {
           printf("\nElement is not present in the list");
           return ;
       }
       i=ar[i].next;
    }
    cout<<"\nElement is present at index \n"<<i;
}
int main()
{
int a,flag=1;
arraylink linked;
while(flag)
    {
        cout<<"Main Menu\n\t1.Creation\n\t2.Display\n\t3.Insert\n\t4.Delete\n\t5.Search\n\t6.Exit\nEnter your choice : ";
        cin>>a;
        switch(a)
        {
        case 1:
            linked.create();
            break;
        case 2:
            linked.display();
            break;
        case 3:
            linked.insert();
            break;
        case 4:
            linked.delet();
            break;
        case 5:
            linked.search();
            break;
        case 6:
             flag=0;
        default:
             cout<<"Sorry wrong choice";
       }
    }
    return 0;
}

OUTPUT

C++ program to implement linked list using dynamic memory allocation

In following program we have used dynamic memory allocation to create linked list thus we are not using array.

#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
typedef struct links
{
int data;
struct links *next;
}links;

class linkedlist
{
    links *start;
public:
    linkedlist()
    {
        start=NULL;
    }
    void create();
    void insert();
    void display();
    void delet();
    void search();
    void count();
    void erase(links *);
    links *getstart()
    {
        return start;
    }
    void setstart()
    {
        start=NULL;
    }
};
void linkedlist::create()
{
    int take;
    links *temp;
    char ch;
    cout<<"Enter the element ";
    cin>>take;
    start=new links;
    start->data=take;
    start->next=NULL;
    temp=start;
    cout<<"Want to enter more elements (Y/N)\n";
    ch=getch();
    while(ch!='n'&&ch!='N')
    {
        cout<<"Enter the element ";
        cin>>take;
        temp->next=new links;
        temp=temp->next;
        temp->data=take;
        temp->next=NULL;
        cout<<"Want to enter more elements (Y/N)\n";
        ch=getch();
    }
}
void linkedlist::insert()
{
    int a,da;
    links *ne,*temp=start;
    cout<<"Enter the element to be inserted ";
    cin>>da;
    ne=new links;
    ne->data=da;
    if(start!=NULL)
    {
        cout<<"Enter your choice\n 1.Insert as a first node\n 2.Insert as a last node\n 3.Insert between node ";
        cin>>a;
        switch(a)
        {
        case 1:
           ne->next=start;
           start=ne;
           break;
        case 2:
           ne->next=NULL;
           while(temp->next!=NULL)
                temp=temp->next;
           temp->next=ne;
           break;
        case 3:
           cout<<"Enter the element after which element to be inserted ";
           cin>>da;
           while(temp->data!=da)
               temp=temp->next;
           ne->next=temp->next;
           temp->next=ne;
           break;
        default:
           cout<<"Sorry wrong choice\n";
           break;
        }
    }
    else
    {
        start=ne;
        start->next=NULL;
    }
}
void linkedlist::delet()
{
    int a;
    links *de,*pre,*temp=start;
    display();
    cout<<"Enter the element to be deleted ";
    cin>>a;
    while(temp->data!=a)
    {
         if(temp->next==NULL)
         {
            cout<<"Entered element is not present";
            return ;
         }
         pre=temp;
         temp=temp->next;
    }
    if(temp==start)
    {
        if(start->next==NULL)
        {
            delete temp;
            setstart();
        }
        else
        {
            start=temp->next;
            delete temp;
        }
    }
    else if(temp->next==NULL)
    {
        pre->next=NULL;
        delete temp;
    }
    else
    {
        pre->next=temp->next;
        delete temp;
    }
    display();
}
void linkedlist::display()
{
    links *temp=start;
    while(temp!=NULL)
    {
        cout<<temp->data<<"-> ";
        temp=temp->next;
    }
    cout<<"NULL\n";
}
void linkedlist::search()
{
    int a;
    links *temp=start;
    cout<<"Enter the element to be searched ";
    cin>>a;
    while(temp->data!=a)
    {
        if(temp->next==NULL)
        {
            cout<<"Element is not present"<<endl;
            return;
        }
        temp=temp->next;
    }
    cout<<"Element is present"<<endl;
}
void linkedlist::count()
{
    int c=0;
    links *temp=start;
    if(temp==NULL)
        cout<<"Linked List is Empty"<<endl;
    else
    {
        while(temp->next!=NULL)
        {
            temp=temp->next;
            c++;
        }
        cout<<"Total no. of nodes in linked list "<<c+1<<endl;
    }
}
void linkedlist::erase(links *temp)
{
    if(temp==NULL)
    {
        delete temp;
        return ;
    }
    else
    {
        temp=temp->next;
        erase(temp);
        delete temp;
    }
}
int main()
{
    int a,flag=1;
    linkedlist linklist;
    while(flag)
    {
        cout<<"Main Menu\n\t1.) Creation\n\t2.) Display\n\t3.) Insert\n\t4.) Delete\n\t5.) Search\n\t6.) Count Nodes\n\t7.) Erase Linked List\n\t8.) Exit";
        cout<<"\nEnter your choice ";
        cin>>a;
        switch(a)
        {
        case 1:
            linklist.create();
            break;
        case 2:
            linklist.display();
            break;
        case 3:
            linklist.insert();
            break;
        case 4:
            linklist.delet();
            break;
        case 5:
            linklist.search();
            break;
        case 6:
            linklist.count();
            break;
        case 7:
            linklist.erase(linklist.getstart());
            linklist.setstart();
            break;
        case 8:
            flag=0;
        default:
            cout<<"Sorry Wrong choice";
        }
    }
}