Implementation of Linked List

List

A list is a data structure in which the first elements is stored on its own, but is provided with a pointer to the location of second object which may be stored ia a different area of memory.

Program to perform various operation in a singly link list

#include<stdio.h>

#include<malloc.h>

struct node

{

    int info;

    struct node *link;

};

struct node *first;

void create()

{

    struct node *ptr, *cptr;

    char ch;

    ptr=(struct node*)malloc(sizeof(struct node));

    printf("Enter first node information: ");

    scanf("%d",&ptr->info);

    first=ptr;

    do

    {

        cptr=(struct node*)malloc(sizeof(struct node));

        printf("Enter next node: ");

        scanf("%d",&cptr->info);

        ptr->link=cptr;

        ptr=cptr;

        printf("press 'y' for another entry: \n");

        ch=getch();

    }while(ch=='y');

    ptr->link=NULL;

}

void traverse()

{

    struct node *ptr;

    printf("traversing a linked list\n");

    ptr=first;

    while(ptr!=NULL)

    {

        printf("%d==>",ptr->info);

        ptr=ptr->link;

    }

}

void insert_beg()

{

    struct node *ptr;

    ptr=(struct node *)malloc(sizeof(struct node));

    printf("\nenter data to be inserted at the beginning: ");

    scanf("%d",&ptr->info);

    ptr->link=NULL;

    ptr->link=first;

    first=ptr;

}

void insert_end()

{

    struct node *ptr, *temp;

    ptr=(struct node *)malloc(sizeof(struct node));

    printf("\nenter data to be inserted at the end: ");

    scanf("%d",&ptr->info);

    ptr->link=NULL;

    if(first==NULL)

        first=ptr;

    temp=first;

    while(temp->link!=NULL)

    {

        temp=temp->link;

    }

    temp->link=ptr;

}

void insert_spos()

{

    int i, pos;

    struct node *ptr, *temp;

    ptr=(struct node *)malloc(sizeof(struct node));

    printf("\nenter position of node to insert new node: ");

    scanf("%d",&pos);

    printf("enter data to be inserted at position %d: ",pos);

    scanf("%d",&ptr->info);

    ptr->link=NULL;

    temp=first;

    if(first==NULL)

    {

        printf("insertion not possible.");

        exit(0);

    }

    for(i=1;i<pos-1;i++)

    {

        temp=temp->link;

    }

    ptr->link=temp->link;

    temp->link=ptr;

}

void main()

{

    create();

    traverse();

    insert_beg();

    traverse();

    insert_end();

    traverse();

    insert_spos();

    traverse();

}

Sample output

Program to perform various operations in a doubly link list

#include<iostream>

#include<conio.h>

using namespace std;

class doublelinklist

{

    struct node

    {

        int data;

        struct node *Rpoint;

        struct node *Lpoint;

    };

    struct node *start,*end,*temp,*tmp;

    public:

    doublelinklist()

    {

        start=NULL;

        end=NULL;

    }

    void addatbegin(int q)

    {

        struct node *tmp;

        tmp=(struct node*)new(struct node);

        tmp->data=q;

        tmp->Lpoint=NULL;

        cout<<tmp->data<<" added at the beginning of the list.\n";

        if(start==NULL)

        {

            tmp->Rpoint=NULL;

        }

        else

        {

            start->Lpoint=tmp;

            tmp->Rpoint=start;

        }

        start=tmp;

    }

    void addatend(int q)

    {

            struct node *tmp;

            tmp=(struct node*)new(struct node);

            tmp->data=q;

            if(start==NULL)

            {

                start->Lpoint=NULL;

                start->Rpoint=NULL;

            }

            else

            {

                end=start;

                while(end->Rpoint!=NULL)

                {

                    end=end->Rpoint;

                }

                end->Rpoint=tmp;

                tmp->Lpoint=end;

                tmp->Rpoint=NULL;

            }

            end=tmp;

            cout<<tmp->data<<" added at the end.\n";

    }

    void addafterdata(int q, int pos)

    {

        temp=start;

        int i=1;

        while((i<pos)&&(tmp!=NULL))

        {

            temp=temp->Rpoint;

            i++;

        }

        if(tmp!=NULL && i==pos)

        {

            struct node *tmp;

            tmp=(struct node*)new(struct node);

            tmp->data=q;

            tmp->Rpoint=temp->Rpoint;

            tmp->Lpoint=temp;

            (temp->Rpoint)->Lpoint=tmp;

            temp->Rpoint=tmp;

            cout<<tmp->data<<" added successfully to the "<<pos<<".\n";

        }

        else

        {

            cout<<"Position "<<pos<<" doenot exists.\n";

        }

    }

    void deletenode(int q)

    {

        //struct node *tmp;

        struct node *tmp1;

        //tmp=(struct node*)new(struct node);

        tmp1=(struct node*)new(struct node);

        temp=start;

        while(temp->data!=q && temp!=NULL)

        {

            temp=temp->Rpoint;

        }

        if(temp->data==q)

            {

                tmp=temp->Rpoint;

                tmp->Lpoint=temp->Lpoint;

                tmp1=temp->Lpoint;

                tmp1->Rpoint=temp->Rpoint;

                temp=NULL;

                cout<<q<<" deleted.\n";

            }

            else

            {

                cout<<"Data not found.\n";

            }

    }

    void display()

    {

            struct node *tmp;

            cout<<endl;

            if(start == NULL)

                {

                    cout<<"\n\nList is empty";

                    return;

                }

            tmp=start;

            cout<<"\n\nList is : \n";

            while(tmp!=NULL)

                {

                    cout<<tmp->Lpoint<<"\t\t"<<tmp->data<<"\t\t"<<&tmp->data<<"\t\t"<<tmp->Rpoint<<endl;

                    tmp=tmp->Rpoint;

                }

            cout<<"\n";

    }

};

int main()

{

    doublelinklist d;

    d.addatbegin(1);

    d.addatbegin(2);

    d.addatend(3);

    d.addatend(4);

    d.addafterdata(6,2);

    d.display();

    //d.deletenode(2);

    //d.display();

    return 0;

}