Linked List Operations

Leetcode Linked List Revise:

http://www.programcreek.com/2013/12/in-place-reorder-a-singly-linked-list-in-java/
http://www.programcreek.com/2015/03/leetcode-odd-even-linked-list-java/

FakeHead/ConnectNode Technique:
http://www.programcreek.com/2013/02/leetcode-partition-list-java/
http://www.programcreek.com/2015/03/leetcode-odd-even-linked-list-java/
http://www.programcreek.com/2014/04/leetcode-swap-nodes-in-pairs-java/
http://www.programcreek.com/2014/04/leetcode-remove-linked-list-elements-java/

Two Pointer Technique:
http://www.programcreek.com/2013/02/leetcode-partition-list-java/




Write functions for Following Linked List(Single,Circular,Double) Operations using Self Referential Structure

1.Create
2.Insertion
3. Deletion

Intro:
http://quiz.geeksforgeeks.org/linked-list-set-1-introduction/
http://www.geeksforgeeks.org/linked-list-vs-array/
http://quiz.geeksforgeeks.org/programmers-approach-looking-array-vs-linked-list/

Operations:
http://quiz.geeksforgeeks.org/linked-list-set-2-inserting-a-node/
http://quiz.geeksforgeeks.org/linked-list-set-3-deleting-node/
http://quiz.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/
http://quiz.geeksforgeeks.org/find-length-of-a-linked-list-iterative-and-recursive/
http://www.geeksforgeeks.org/how-to-write-functions-that-modify-the-head-pointer-of-a-linked-list/

Code:

#include <stdio.h>
#include<malloc.h>
#include<conio.h>

struct node{
int info;
struct node *prev;
struct node *link;};

                       //-----------------------------------CREATE----------------------------------------------
                                                           
void Create_List_Single(struct node *& head,int data)//USING A TEMP VARIABLE
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=NULL;

if (head==NULL)
    {head=tmp;}
 else
    {q=head;
    while(q->link!=NULL)
        q=q->link;
    q->link=tmp;}
}

void Create_List_Circular(struct node *& last,int data)//WITHOUT USING A TEMP VARIABLE
{
struct node *tmp;//As we have to save the link of last first ,we have to use temp
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;

if (last==NULL)
    {last=tmp;
      tmp->link=last;}
else
    {
    tmp->link=last->link;//tmp points to first node that is link of last
    last->link=tmp;//
    last=tmp;
    }
}

void Create_List_Double(struct node *& head,int data)//WITHOUT USING A TEMP VARIABLE
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=NULL;


if (head==NULL)
    {tmp->prev=NULL;
      (head)=tmp;}
else
    {q=head;
    while(q->link!=NULL)
        q=q->link;
    q->link=tmp;
    tmp->prev=q;}
}

                   //-----------------------------------INSERT----------------------------------------------

void INSERT_LIST_SINGLE(struct node *& head,int data,int pos)
{
struct node *q,*tmp;
int i;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;

if(pos==1)
   {tmp->link=head;
    head=tmp;}

else
    {q=head;
    for (i=1;i<pos-1;i++)
    {    q=q->link;
    if(q==NULL)
        {printf("There is  less than %d elements",pos);
        return;}
    }  
    tmp->link=q->link;
    q->link=tmp;}
}

void Sorted_Insert_Single(struct node *& head,int num)
{
struct node *q,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=num;

if(head==NULL || num<(head)->info)
    {tmp->link=head;
     head=tmp;
     return;}
else
    {q=head;
     while(q->link!=NULL && q->link->info<num)
        q=q->link;
    tmp->link=q->link;
    q->link=tmp;}
}


void INSERT_LIST_Circular(struct node *& last,int data,int pos)
{
struct node *q,*tmp;
int i;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;


if (pos==1)
    {tmp->link=last->link;//Replace *head with last->link
    last->link=tmp;}
else
    {
    q=last->link;//Replace *head with last
    for (i=1;i<pos-1;i++)
    {    q=q->link;
    if(q==last->link && pos!=2)
        {printf("\nThere is  less than %d elements\n",pos);
        return;}
     }
    
    tmp->link=q->link;
    q->link=tmp;
    if(q==last)//As we also need to change pointer of last node
        last=tmp;}
}

void INSERT_LIST_DOUBLE(struct node *& head,int data,int pos)
{
struct node *q,*tmp;
int i;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;

if(pos==1)
{
tmp->link=head;// NEXT LINK of TEMP
tmp->prev=NULL;// PREV LINK of TEMP
head->prev=tmp;// PREV LINK of 2nd NODE pointing to TEMP
head=tmp;}//HEAD pointing to TEMP

else
    {q=head;
    for (i=1;i<pos-1;i++)
    {    q=q->link;
    if(q==NULL)
        {printf("There is  less than %d elements",pos);
        return;}
    }
    tmp->link=q->link;//next of TEMP
    tmp->prev=q;//PREV of TEMP
    if(q->link!=NULL) //Consideration for insertion at last position
         q->link->prev=tmp;//Needs to be done b4 this link is lost in next stmt--NEXT of q
    q->link=tmp;}//Prev of q->link}
}


                    //-----------------------------------DELETE----------------------------------------------

void Delete_LIST_Single(struct node *& head,int data)
{ struct node *tmp,*q;//TMP is used to freeing the node before deletion

if(head->info==data)// FIRST NODE-Needs to change head node
    {tmp=head;
    head=head->link;
    free(tmp);
    return;}
      
q=head;//In between NODE
while(q->link->link !=NULL)
{
    {if (q->link->info==data)
        {tmp=q->link;
         q->link=tmp->link;
         free(tmp);
         return;}
q=q->link;
    }

     if(q->link->info==data) //LAST NODE--Needs to set NULL
          {tmp=q->link;
           free(tmp);
           q->link=NULL;
           return;}

}   //END of WHILE

printf("Element is not present\n");
}

void Delete_LIST_Circular(struct node *& last,int data)
{
struct node *tmp,*q;//TMP is used to free the node before deletion

q=last;//As we have last pointer so we dont have to chnage head node;thus no first condition
while(q->link!=last)// same as checking q->link->link!=NULL in single case
{
    if (q->link->info==data)
        {tmp=q->link;
         q->link=tmp->link;
         free(tmp);
        return;}
q=q->link;
}

if(q->link->info==data)
  {    tmp=q->link;
     if (last->link==last && last->info==data)//Only 1 element-Need to set last to NULL
        last=NULL;
     else
        {q->link=last->link;  //Last element--: q->link=last
        last=q;}
    free(tmp);
    return;
   }
}

void Delete_LIST_DOUBLE(struct node *&head,int data)
{
struct node *tmp,*q;//TMP is used to free the node before deletion

if(head->info==data)// FIRST NODE-Needs to change head node
    {tmp=head;
    head=head->link;
    head->prev=NULL;//different than Single
    free(tmp);
    return;}
   
q=head;
while(q->link->link !=NULL)
{
    if (q->link->info==data)
        {tmp=q->link;
         q->link=tmp->link;
        tmp->link->prev=q;
         free(tmp);
        return;}
q=q->link;
}
if(q->link->info==data) //LAST NODE--Needs to set NULL
    {tmp=q->link;
    free(tmp);
    q->link=NULL;
    return;}
}

                      //-----------------------------------REVERSE----------------------------------------------

void REVERSE_ITERATIVE_LIST_SINGLE(struct node *&head)
{
struct node *p1,*p2,*p3;

if (head->link==NULL)
    return;
   
p1=head;
p2=p1->link;
p3=p2->link;
p1->link=NULL;
p2->link=p1;
while(p3!=NULL)
    {p1=p2;
     p2=p3;
     p3=p3->link;
    p2->link=p1;
    }
head=p2;
}

static void REVERSE_ITERATIVE_LIST_SINGLE_BETTER(struct node*& head)
{
    struct node* prev   = NULL;
    struct node* current = head;
    struct node* next;
    while (current != NULL)
    {
        next  = current->link;
        current->link = prev;
        prev = current;
        current = next;
    }
    head = prev;
}

void REVERSE_RECURSIVE_LIST_SINGLE(struct node*& head)//http://www.geeksforgeeks.org/archives/860
{
    struct node* first;
    struct node* rest;

    /* empty list */
    if (head == NULL)
       return; 

    /* suppose first = {1, 2, 3}, rest = {2, 3} */
    first = head;
    rest  = first->link;

    /* List has only one node */
    if (rest == NULL)
       return; 

    /* put the first element on the end of the list */
    REVERSE_RECURSIVE_LIST_SINGLE(rest);
    first->link->link  = first;

    /* tricky step -- see the diagram */
    first->link  = NULL;        

    /* fix the head pointer */
    head = rest;
}

void REVERSE_ITERATIVE_LIST_DOUBLE(struct node *&head)
{
struct node *p1,*p2;

if (head->link==NULL)
    return;
   
p1=head;
p2=p1->link;
p1->link=NULL;
p1->prev=p2;
while(p2!=NULL)
    {p2->prev=p2->link;
     p2->link=p1;
     p1=p2;
    p2=p2->prev;
    }
head=p1;
}

void display(struct node *head)
{struct node *q;
if(head==NULL)
{printf("List is empty");
return;
}
q=head;
printf("\nList is\n");
while(q!=NULL)
{printf("%d\n",q->info);
q=q->link;}
}

void display_circular(struct node *head)
{struct node *q;
if(head==NULL)
{printf("List is empty");
return;
}
q=head->link;
printf("\nList is\n");
while(q!=head)
{printf("%d\n",q->info);
q=q->link;}
printf("%d\n",head->info);
printf("%d",head->link->info);
}



int main(){
       int choice,n,m,position,i;
       struct node *head=NULL;
       struct node *head1=NULL;
       struct node *last=NULL;
       struct node *head2=NULL;
      
       Create_List_Single(head,4);
       Create_List_Single(head,8);
       Create_List_Single(head,1);
       Create_List_Single(head,67);
       Create_List_Single(head,53);
       Create_List_Single(head,104);
       //display(head);
       INSERT_LIST_SINGLE(head,9,6);
       INSERT_LIST_SINGLE(head,9,6);
       display(head);
      // Delete_LIST_Single(head,22);
      // display(head);
       //REVERSE_ITERATIVE_LIST_SINGLE(head);
       //REVERSE_RECURSIVE_LIST_SINGLE(head);
       REVERSE_ITERATIVE_LIST_SINGLE_BETTER(head);
       display(head);
      
      
       Sorted_Insert_Single(head1,89);
       Sorted_Insert_Single(head1,23);
       Sorted_Insert_Single(head1,123);
       Sorted_Insert_Single(head1,1);
       Sorted_Insert_Single(head1,43);
       //display(head1);
      
      
      
       Create_List_Circular(last,5);
       Create_List_Circular(last,76);
       Create_List_Circular(last,43);
       Create_List_Circular(last,23);
       Create_List_Circular(last,2);
       //display_circular(last);
       //INSERT_LIST_Circular(last,54,2);
       //display_circular(last);
       Delete_LIST_Circular(last,43);
      // display_circular(last);
      
      
      
        Create_List_Double(head2,4);
        Create_List_Double(head2,8);
        Create_List_Double(head2,45);
        Create_List_Double(head2,87);
        Create_List_Double(head2,11);
        Create_List_Double(head2,23);
        //display(head2);
        //INSERT_LIST_DOUBLE(head2,9,7);
        display(head2);
        Delete_LIST_DOUBLE(head2,4);
        display(head2);
        REVERSE_ITERATIVE_LIST_DOUBLE(head2);
         display(head2);
       
      
       getch();
       return 0;
        }