LINKEDLIST FLATTENING

Start with a standard doubly-linked list. Now imagine that in addition to next and
previous pointers, each element has a child pointer, which may or may not point to a
separate doubly-linked list. These child lists may have one or more children of their
own, and so on, to produce a multilevel data structure, as shown in Figure 4-3.
Flatten the list so that all the nodes appear in a single-level, doubly-linked list. You
are given the head and tail of the first level of the list. Each node is a C struct with
the following definition:
typedef struct Node {  
struct Node *next;
struct Node *prev;
struct Node *child;
int          value;
} Node;


This algorithm is as follows:
Start at the beginning of the first level
While you are not at the end of the first level
If the current node has a child
  Append the child to the end of the first level
  Update the tail pointer
Advance to next node


The code for this algorithm is as follows:

void flattenList( Node *head, Node **tail)
Node *curNode =  head;
while( curNode ){
/* The current node has a child */
if( curNode->child ){
append( curNode->child, tail );
}
curNode = curNode->next;
}
}

/* Appends the child list to the end of the tail and updates  ;
* the tail.
*/

void append( Node *child, Node **tail ){
Node *curNode;
/* Append the child child list to the end */
(*tail)->next = child;
child->prev = *tail;

/*Find the new tail, which is the end of the child child   ;
*list.
*/

for( curNode = child; curNode->next;
curNode = curNode->next )
; /* Body intentionally empty */
/* Update the tail pointer now that curNode is the new 
* tail.
*/
*tail = curNode;
}

TRAVERSAL AND INSERTION IN LINKED LIST

A simple LinkedList program that deletes and insert node at a particular location .

#include <iostream>       

using namespace std;

 struct node {
 node *next ;

     int data ;

    } ;

 struct node *head ;   
node* init(int a[] , int n)

 {
  node *head = NULL , *p ;

  for(int i=0;i<n;i++)

   {

    node *nd = new node() ;

    nd->data = a[i] ;

    if(i==0)

    {
    head = p = nd ;   

    }

    p->next = nd ;

    p = p->next ;

      

   }

   return head ;

    

 }

 void display (node *head)

 {

     node *p ;

     p = head ;

    while(p!=NULL)

     {

           cout<<p->data<<endl;

           p = p->next ;

        

     }

    

 }

 bool deleteMe(int x)

  {

   node *p = head ;

   if(head->data ==x)

    {

        head = head->next ;

    }

    else

    {

    while(p->next->data != x)

     {

        

         p = p->next ;

     }

     if(p->next->data == x)

      {

         

          p->next = p->next->next ;

          return 1 ;

      }

    }

          return 0 ;

  }

 void insertMe(int loc , int data)

  { 

      node *nd = new node();

      nd->data =  data ;

     node *p = head ;

     if(loc==1)

      {

          nd->next = head ;

          head = nd ;

         

      }else

      {

          for(int i=1 ; i<loc-1 ; i++)

           {

               p = p->next ;

              

           }

           nd->next = p->next ;

           p->next = nd ;

         

      }

     

  }

int main()

{

  int a[] = {1,2,3,4,5,6,7,8,9} ;

  head = init(a , 9) ;

  display(head) ;

  deleteMe(1) ; //delete the node with the given data

  cout<<endl<<endl ;

  display(head) ;

  cout<<endl<<endl ;

  insertMe(3 , 10);

  display(head) ;

  return 0;

}

IMPLEMENTING STACK VIA LINKED-LIST 

We all know what stack do . Its follows a  Last In First Out methodology and here in this program i have implemented the same via LinkedList . I hope you all know what a LinkedList does . 
struct node
{
  node *next ;
  int data ;
};
struct node *head = NULL , *p=NULL ;
void display()
{
  node *temp = new node() ;
  temp = head ;
  while(temp!=NULL)
  {
    printf("%d\n",temp->data) ;
    temp = temp->next ;
  }
}
void push(int x)
{
  node *nd = new node() ;
  nd->data = x ;
  if(head==NULL)
  {
    head = p = nd ;

  }else
  {
    p->next  = nd ;
    p = p->next ;
  }
  display() ;
}
void pop ()
{
  node *temp = new node() ;
  temp = head ;
  while(temp->next->next!=NULL)
  {
      temp = temp->next ;
  }
  printf("popped element %d\n",temp->next->data) ;
  temp->next = NULL ;
  display() ;
}
int _tmain(int argc, _TCHAR* argv[])
{
    int value , x , v ;
    do
    {
        printf("1. push") ;
        printf("2. pop");
        printf("choose...") ;
        scanf_s("%d",&value) ;
        switch(value)
        {
        case 1 :
            printf("Enter data");
            scanf_s("%d",&x);
            push(x) ;
            break;
        case 2 :
            pop() ;
        }
        printf("press 3 to continue") ;
        scanf_s("%d",&v) ;
    }while(v==3) ;

    return 0;
}