Wednesday, 5 September 2012

Insertion at a specified position in a doubly linked list


/*Insertion At a specified position in Doubly Linked List */
#include<stdio.h>
#include<conio.h>
struct linklist
{
    int data;
    struct linklist *next;
    struct linklist *prev;
};
typedef struct linklist node;

node *create_node(int val,node *nxt,node *prv)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=val;
    p->next=nxt;
    p->prev=prv;
    return p;


int get_length(node *head)/*Returns the number of elements in the list*/
{
    int count=0;
    if(head!=NULL)
    {
        while(head!=NULL)
        {
            head=head->next;
            count++;
        }
    }
    return count;
}

node *get_ith_node(node *head,int i)
{
    if(i<=get_length(head))
    {
        while(i>1)
        {
            head=head->next;
            i--;
        }
        return head;
    }
    else
        return NULL;
}

node *inposition(node *head,int val,int pos)/*At specified location*/
{
    int no_of_elements;
    node *p,*nxt;
    if(head==NULL)
    {
        if(pos==1)
            head=create_node(val,NULL,NULL);
        else
            printf("No linked list exists\n");
    }
    else
    {
        no_of_elements=get_length(head);
        if(pos<=no_of_elements+1)
        {
            p=get_ith_node(head,pos-1);
            if(pos==1)
            {
                head=create_node(val,head,NULL);
                head->next->prev=head;
            }
            else
            {
                nxt=p->next;
                p->next=create_node(val,p->next,p);
                if(nxt!=NULL)/*If the insertion is performed at the end of the doubly list, nxt will be NULL*/
                nxt->prev=p->next;
            }
        }
        else
            printf("Desired number of nodes do not exists\n");
    }
    return head;
}

node *del_from_pos(node *head,int pos)/*Deletion From specified Position*/
{
    node *p,*start=head;
    int no_of_elements;
    if(head!=NULL)
    {
        if(pos==1)
        {
            head=head->next;
            if(head!=NULL)/*If only 1 node exists*/
            head->prev=NULL;
            free(start);
        }
        else
        {
            no_of_elements=get_length(head);
            if(pos<=no_of_elements)
            {
                p=get_ith_node(head,pos-1);
                start=p->next;
                p->next=start->next;
                if(start->next!=NULL)/*If the deletion is performed at the end of the doubly list, start->next will be NULL*/
                start->next->prev=p;
                free(start);
            }
            else
                printf("Desired number of nodes do not exists\n");
        }
    }
    return head;
}

void print_r(node *head)/*Prints the reversed contents of the linked list*/
{
    node *t_head=head;
    printf("\nReversed_Contents\n");
    if(head!=NULL)
    {
        while(t_head!=NULL)
        {
            printf("%d \t",t_head->data);
            t_head=t_head->prev;
        }
        printf("\n");
    }
    else
        printf("The list is Empty \n");
}

void print(node *head)/*Prints the contents of the linked list*/
{
    node *t_head=head;
    printf("\nContents\n");
    if(head!=NULL)
    {
        while(t_head!=NULL)
        {
            printf("%d \t",t_head->data);
            head=t_head;
            t_head=t_head->next;
        }
        printf("\n");
    }
    else
        printf("The list is Empty \n");
    print_r(head);
}

int main()
{
    node *head=NULL;
    head=inposition(head,10,1);
    head=inposition(head,8,2);
    head=inposition(head,9,2);
    head=inposition(head,7,4);
    print(head);
    head=del_from_pos(head,4);
    print(head);
    head=del_from_pos(head,2);
    print(head);
    head=del_from_pos(head,1);
    print(head);
    head=del_from_pos(head,1);
    print(head);
    getche();
}

0 comments:

Post a Comment

Twitter Delicious Facebook Digg Stumbleupon Favorites More

 
@Gnosioware Solutions