DOUBLY LINKED LIST

 DOUBLY LINKED LIST

HEAD N1 NEXT PTR N2 N3 N4

23 34 56 52

N NULL

NULL

PREV PTR DATA

EXTRA SPACE IS CONSUMED FOR TRAVERSING IN BOTH WAY

2 POINTERS ARE REQUIRED/AVAILABLE IN DOUBLY LINKED LIST

Struct node

{

Int data;

Struct node *prev; //*struct node type pointer

Struct node*next;

}

Struct node *N1=(struct node*)malloc…….);

Struct node *N2=(struct node*)malloc…….);

Struct node *N3=(struct node*)malloc…….);

Struct node *N4=(struct node*)malloc…….);

//Linking nodes

N1->next->N2;

N1->Prev=Null;

N2

N3

N4

CIRCULAR LINKED LIST

8 7 11

HEAD

P=HEAD

P->DATA;

WHILE(P->NEXT!=HEAD);

PRINT(P->NEXT)

}

PRINT(P->DATA)

}

Do {

Print(p->data)

P=p->next;

}

While(p!=head)

}

Merging of linked list (sorted)

p-> 10,50,70,90,100,null

q->20,30,40,60,80,null

pointer = S INITIALLY S WILL POINT TO A SHORTER ELEMENT OF LIST

S will point to “10” in list in p

Node *merge(node*p, node*q, node*sorting)

{

Node*new head=NULL;

IF(p==null)return q;

If(q==null)return p;

If(p&&q)

{

If(p->data<=q->data)

{sorting=p;

P=sorting->next;

}

Else{sorting=q;

Q=sorting->next;

}

}

Newhead=sorting;

While(p&&q)

If(p->data<=q->data)

{

Sorting=p;

P=sorting->next

}

Else

{

Sorting->next=q;

Sorting=q;

Q=sorting->next;

}

If(p=null)sorting->next=q;

If(q=null)sorting->p;

Return new head;

}