Algorithm For Linked List

Download as doc, pdf, or txt
Download as doc, pdf, or txt
You are on page 1of 19

Algorithm for Singly Linked List

Struct node{ int data; struct node *next; }; typedef struct node NODE Function create(NODE ** start,int m) Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Step 9 Begin declare struct pointer variable temp and t [NODE *temp, *t] check if *start equal to NULL then Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Assign value to that node Set temp data = m Assign NULL to the address part Set temp next = NULL Assign address of the temp variable to start pointer. Set *start = NULL else Begin for loop for temp equal to *start in oder to temp next not equal to NULL with the one increment of address temp do [for(temp = (*start) ; tempnext !=NULL ; temp=tempnext); ]

End for loop Step 10 Allocate space to newly created node Set t = (NODE *) malloc ( sizeof(NODE)) Step 11 Assign value to information part of a node Set tdata = m Step 12 Assign NULL to the address part of NODE t Set tnext=NULL Step 13 Allocate Address of t to the tempnext part Set temp next= t Step 14 endif Step 15 End

Add element after the specified number of node


void addafter (NODE **start, int loc, int num)

Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Step 9

Step 10

Step 11 Step 12 Step 13 Step 14 Step 15 Step 16 Step 17

Begin declare struct pointer variable temp and t [Set NODE *temp, *t] check if equal to 1 than Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Assign value to that node Set temp data = m Assign *start to the address part Set temp next = (*start) Assign address of the temp variable to start pointer. Set *start = temp else Begin For Loop For i equal to 1 in order to i less than to loc-1 with one increment do Set for (i=1; i<loc-1; i++) increment temp one step ahead Set temp=temp->next Check if temp->next equal to NULL than Position not found Return Enif End For Loop Allocate space to newly created node Set t = (NODE *) malloc ( sizeof(NODE)) Assign value to information part of a node Set tdata = m Assign tempnext to the address part of NODE t Set tnext=tempnext Allocate Address of t to the tempnext part Set temp next= t End if End

Add a new node at first Position


void addfirst(NODE **start, int m) Step 1 Step 2 Step 3 Step 4 Begin declare struct pointer variable temp [Set NODE *temp] Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Assign value to that node Set temp data = m

Step 5 Step 6 Step 7

Assign value of *start into tempnext Set tempnext = (*start) Assign address of temp into *start Set *start = temp End

Delete nod at first position


void delfirst(NODE **start) Step 1 Step 2 Step 3 Step 4 Step 5 Begin declare struct pointer variable temp [Set NODE *temp] Assign value of *start to temp Set temp = (*start) Assign value of tempnext to *start Set *start = tempnext Free the temp Set free (temp)

Delete node at last position


void dellast (NODE **start) Step 1 Step 2 Step 3 Step 4 Begin declare struct pointer variable temp and t [Set NODE *temp, *t] Assign value of *start to temp Set temp = (*start) While Loop Begin while tempnext not equal to NULL do Set t = temp Set temp = temp next End while Check if *startnext equal to NULL Set *start = NULL Endif Assign NULL to tnext Set tnext = NULL Free the temp Set Free(temp) End

Step 5

Step 6 Step 7 Step 8

Delete a node at given position


void delposi(NODE **start, int pos) Step 1 Step 2 Begin declare struct pointer variable temp and t

[Set NODE *temp, *t]

Step 3 Step 4

Step 5 Step 6 Step 7

Step 8 Step 9 Step 10 Step 11

Assign value of *start to temp Set temp = (*start) Check if equal to 1 than Assign value of tempnext into *start Set *start = tempnext Free temp Set Free(temp) Endif else For Loop Begin for i equal to 1 in order to i less than and equal to pos -1 with one increment do Set t = temp Set temp = temp next Check if temp equal to NULL than Position not found Return Endif End for loop Assign value of tempnext to tnext Set tnext = tempnext Free temp Set Free(temp) Endif End

Ascending Order Linked List


void create (NODE **start, int m) Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Begin declare struct pointer variable temp and t [Set NODE *temp, *t] Assign value of *start to temp Set temp = (*start) Allocate space to newly created node Set t = (NODE *) malloc ( sizeof(NODE)) Assign data to tnext Set tnext = m Check if *start equal to NULL or (*start)data is greater than m tyan Set (*start) = t; Set (*start)next = temp; else While Loop Begin while temp not equal to NULL do check if tempdata is less than or equal to m and tempnextdata greater than m or tempnext equal to NULL than Set tnext = temp next

Step 7 Step 8

Set tempnext=t Return Endif Set temp=tempnext Endwhile Endif End

Step 9

Reverse a Linked list using one traversing


void reverse (NODE **start) Step 1 Step 2 Step 3 Begin Declare struct pointer variable temp, ptr and t Assign value of *start to temp and temp to NULL Set ptr = (*start) Set temp= NULL While Loop Begin while ptr not equal to NULL do Set cur = temp Set temp = ptr Set ptr = ptrnext Set tempnext = cur Endwhile Set (*start) = temp End

[Set NODE *temp, *t, *ptr]

Step 4

Step 5 Step 6

Sorting a Linked list (1) Exchange the data part of two node
void sort(int n, NODE **start) Step 1 Step 2 Step 3 Begin declare struct pointer variable temp and t [Set NODE *temp, *t] For Loop Begin for i equal to 0 in order to i is less than n-1 with one increment do Set temp = (*start) Set t= tempnext; For Loop Begin for j equal to 1 in order to i is less than n-i with one increment do check if tempdata greater than tdata than

Step 4 Step 5

Set p = tempdata Set tempdata = tdata Set tdata=p Step 6 Step 7 Step 8 Step 9 Step 10 Endif Set temp = tempnext; Set t = tnext; End for End for End

(2) Readjust the Link


void sort(NODE **start) Step 1 Step 2 Step 3 Step 4 Begin declare struct pointer variable *temp ,*p,*q,*r,*s [Set NODE *temp, *p, *q, *r, *s] Set s = NULL While Loop Begin while s not equal to (*start)next do Set r=p=(*start) Set q=pnext while p not equal to s do check if p data is greater than q data than check if p equal to (*start) than Set temp = q next Set q next = p Set p next = temp Set (*start) = q Set r = q else Set temp = q next Set q next =p Set p next =temp Set r next =q Set r = q Endif else Set r = p Set p = pnext Endif q= p next check if q equal to s than

Step 5 Step 6 Step 7

Step 8 Step 9

Step 10 Step 11 Step 12 Step 13 Step 14

Set s = p Step 15 Step 16 Step 17 Endif End while Endwhile End

Merging of two Singly Linked List


void merge (NODE **start, NODE **head, NODE **add) Step 1 Begin Step 2 Set p=(*start) Step 3 Set q=(*head) Step 4 if *start equal to NULL and *head equal to NULL than Display both linked list is empty endif Step5 while loop begin While p not equal to NULL and q not equal to NULL do Step 6 if *add equal to NULL than Step 7 Allocate space for data [ Set temp = (NODE *) malloc (sizeof (NODE)) ] Step 8 Assign temp to *add [ Set *add = temp ] Step 9 else Step 10 Allocate space for data [ Set ptr = (NODE *) malloc (sizeof (NODE)) ] Step 11 Assign ptr to temp next [Set tempnext = ptr] Step 12 Assign temp next to temp [Set temp = tempnext] Step 13 endif Step 14 Step 15 Step 16 Step 17 Step 18 Step 19 Step 20 Step 21 if p data less than qdata than Assign p data to temp data [ Set temp data = p data] Assign p next to p [ Set p = p next ] else if p data greater than to q data than Assign q data to temp data [ Set temp data = q data] Assign q next to q [ Set q next = q]

Step 22 Step 23 Step 24 Step 25 Step 26 Step 27 Step 28 Step 29 Step 30 Step 31 Step 32 Step 33 Step 34 Step 35 Step 36 Step 37 Step 38 Step 39 Step 40 Step 41 Step 42 Step 43 Step 44 Step 45 Step 46 Step 47

else if p data equal to q data than Assign p data to temp data [ Set temp data = p data] Assign p next to p [Set p = pnext] Assign qnext to q [Set q = qnext] endif endif endif end while While Loop Begin while p not equal to NULL do Allocate space to data [Set ptr = (NODE *) malloc (sizeof(NODE))] Assign ptr to temp next [Set temp next = ptr] Assign temp next to temp [Set temp = temp next] Assign p data to temp data [Set temp data = p data] Assign p next to p [Set p = pnext] End while While Loop Begin while q not equal to NULL do Allocate space to data [Set ptr = (NODE *) malloc (sizeof(NODE))] Assign ptr to temp next [Set temp next = ptr] Assign temp next to temp [Set temp = temp next] Assign q data to temp data [Set temp data = q data] Assign p next to p [Set q = qnext] End while Assign NULL to tempnext End While

Algorithm for Circular Singly Linked List


Struct node{ int data; struct node *next; }; typedef struct node NODE Function create(NODE ** start,int m) Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Begin check if *start equal to NULL then Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Assign value to that node Set temp data = m Assign *start to the address part Set temp next = (*start) Assign address of the temp variable to start pointer. Set *start = temp else Begin for loop for temp equal to *start in oder to temp next not equal to *start with the one increment of address temp do [for(temp = (*start) ; tempnext !=(*start) ; temp=tempnext); ]

End for loop Step 9 Allocate space to newly created node Set t = (NODE *) malloc ( sizeof(NODE)) Step 10 Assign value to information part of a node Set tdata = m Step 11 Assign NULL to the address part of NODE t Set tnext=(*start) Step 12 Allocate Address of t to the tempnext part Set temp next= t

Step 13 Step 14

endif End

Add element after the specified number of node


void addafter (NODE **start, int pos, int m) Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Begin Assign *start to temp [Set temp = *start] Allocate Space newly created node Set t = (NODE *)malloc (sizeof(NODE)) if pos equal to 1 than Assign value to that node [Set t data = m] Assign temp to the address part of tnext [Set t next = temp] While Loop Begin while temp next not equal to *start do Assign temp next to temp [Set temp = temp next] End while Assign t to the address part of the temp pointer. [Set temp next = t] Assign t to the *start [Set *start = t] else Begin For Loop For i equal to 1 in order to i less than to pos-1 with one increment do Set for (i=1; i<loc-1; i++) increment temp one step ahead Set temp=temp->next if temp->next equal to *start than Position not found Return Endif End For Loop Assign value to information part of a node Set tdata = m Assign tempnext to the address part t Set tnext=tempnext Allocate Address of t to the tempnext part Set temp next= t End if

Step 9 Step 10 Step 11 Step 12

Step 13 Step 14

Step 15 Step 16 Step 17 Step 18 Step 19

Step 20

End

Add a new node at first Position


void addfirst(NODE **start, int m) Step 1 Begin Step 2 Assign *start to t [Set t = *start] Step 3 Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Step 4 Assign value to that node Set temp data = m Step 5 Assign value of *start into tempnext Set tempnext = (*start) Step 6 While Loop Begin while *start not equal to tnext do Assign tnext to t [Set t = t next] End while Step 7 Assign temp to address part of t Set t next = temp Step 8 Assign address of temp into *start Set *start = temp Step 9 End

Delete nod at first position


void delfirst(NODE **start) Step 1 Step 2 Step 3 Begin Assign value of *start to pointer variable temp and t [Set t = temp = (*start)] While Loop Begin while temp next not equal to *start Assign temp next to temp [Set temp = temp next] End while Assign value of tnext to *start Set *start = tnext Assign *start to address part of temp [Set temp next = (*start)] Free the t Set free (t)

Step 4 Step 5 Step 6

Delete node at last position

void dellast (NODE **start) Step 1 Step 2 Step3 Begin Assign value of *start to temp Set temp = (*start) While Loop Begin while tempnext not equal to *start do Set t = temp Set temp = temp next End while Assign temp next in to address part of the t [Set t next = temp next] if *startnext equal to (*start) Set *start = NULL Set Free (temp) else Set Free (temp) End if End

Step Step 5

Step 6 Step 7 Step 8

Delete a node at given position


void delposi(NODE **start, int pos) Step 1 Step 2 Step 3 Step 4 Step 5 Begin Assign value of *start to temp Set temp = (*start) Check if equal to 1 than assign *start to t [Set t = *start] While Loop Begin while temp next not equal to *start Assign temp next to temp [Set temp = temp next] End while Assign value of tnext to *start Set *start = tnext Assign *start to address part of temp [Set temp next = (*start)] Free the t Set free (t) else For Loop Begin for i equal to 1 in order to i less than and equal to pos -1 with one increment do Set t = temp Set temp = temp next

Step 6 Step 7 Step 8 Step 9 Step 10

Check if temp equal to (*start) than Display Position not found Return Endif Step 11 Step 12 Step 13 Step 14 End for loop Assign value of tempnext to tnext Set tnext = tempnext Free temp Set Free(temp) Endif End

Merging of two Circular Singly Linked List


void merge (NODE **start, NODE **head, NODE **add) Step 1 Begin Step 2 Set p=(*start) Step 3 Set q=(*head) Step 4 if *start equal to NULL and *head equal to NULL than Display both linked list is empty endif Step5 while loop begin While p not equal to (*start) and q not equal to (*head) do Step 6 if *add equal to NULL than Step 7 Allocate space for data [ Set temp = (NODE *) malloc (sizeof (NODE)) ] Step 8 Assign temp to *add [ Set *add = temp ] Step 9 else Step 10 Allocate space for data [ Set ptr = (NODE *) malloc (sizeof (NODE)) ] Step 11 Assign ptr to temp next [Set tempnext = ptr] Step 12 Assign temp next to temp [Set temp = tempnext] Step 13 endif Step 14 Step 15 Step 16 if p data less than qdata than Assign p data to temp data [ Set temp data = p data] Assign p next to p [ Set p = p next ]

Step 17 Step 18 Step 19 Step 20 Step 21 Step 22 Step 23 Step 24 Step 25 Step 26 Step 27 Step 28 Step 29 Step 30 Step 31 Step 32 Step 33 Step 34 Step 35 Step 36 Step 37 Step 38 Step 39 Step 40 Step 41 Step 42 Step 43

else if p data greater than to q data than Assign q data to temp data [ Set temp data = q data] Assign q next to q [ Set q next = q] else if p data equal to q data than Assign p data to temp data [ Set temp data = p data] Assign p next to p [Set p = pnext] Assign qnext to q [Set q = qnext] endif endif endif end while While Loop Begin while p not equal to (*start) do Allocate space to data [Set ptr = (NODE *) malloc (sizeof(NODE))] Assign ptr to temp next [Set temp next = ptr] Assign temp next to temp [Set temp = temp next] Assign p data to temp data [Set temp data = p data] Assign p next to p [Set p = pnext] End while While Loop Begin while q not equal to (*head) do Allocate space to data [Set ptr = (NODE *) malloc (sizeof(NODE))] Assign ptr to temp next [Set temp next = ptr] Assign temp next to temp [Set temp = temp next] Assign q data to temp data

Step 44 Step 45 Step 46 Step 47

[Set temp data = q data] Assign p next to p [Set q = qnext] End while Assign (*add) to tempnext End While

Algorithm for Doubly Linked List


Struct node{ int data; struct node *next; struct node *prev; }; typedef struct node NODE Function create(NODE ** start, NODE *tail, int m) Step 1 Step 2 Step 3 Step 4 Step 6 Step 7 Step 8 Step 9 Step 10 else Begin check if *start equal to NULL then Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Assign value to that node Set temp data = m Assign NULL to the next field of temp Set temp next = NULL Assign NULL to the prev field of temp Set temp prev = NULL Assign address of the temp variable to start and tail pointer. Set *start = *tail = temp Begin for loop for temp equal to *start in oder to temp next not equal to NULL with the one increment of address temp do [for(temp = (*start) ; tempnext !=NULL ; temp=tempnext); ]

End for loop Step 11 Allocate space to newly created node Set t = (NODE *) malloc ( sizeof(NODE)) Step 12 Assign value to information part of a node Set tdata = m Step 13 Assign NULL to the next field of NODE t Set tnext=NULL Step 14 Assign temp to the prev field of NODE t Set tprev =temp Step 15 Allocate Address of t to the tempnext part Set temp next= t Step 16 Assign address of t to *tail Set *tail = t; Step 17 endif Step 18 End

Add a new node at first Position


void addfirst(NODE **start, int m) Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Begin Allocate Space to newly created node Set temp = (NODE *)malloc (sizeof(NODE)) Assign value to that node Set temp data = m Assign value of *start into tempnext Set tempnext = (*start) Assign NULL into tempprev Set tempprev=NULL Assign address of temp into *start Set *start = temp End

Add a Node at given Position


void position(NODE **start, int pos, int m) Step 1 Begin Step 2 if pos equal to 1 than Step 3 Allocate space for new node Set t = (NODE *) malloc(sizeof(NODE)) Step 4 Assign m to tdata part Set tdata = m

Step 5 Step 6 Step 7 Step 8 Step 9 Step 10

Assign value of (*start) to tnext part Sst tnext = (*start) Assign t to (*start)next part Set (*start)next = t Assign NULL to tprev part Set tprev = NULL Assign t to (*start) Set (*start) = t else Begin For Loop For i equal to 1 in order to i less than to pos-1 with one increment do Set for (i=1; i<pos-1; i++) increment temp one step ahead Set temp=temp->next if temp->next equal to NULLthan Position not found Return Endif End For Loop Allocate space for new node Set t=(NODE *) malloc (sizeof(NODE)) Assign m to tdata Set tdata = m Assign tempnext to tnext part Set tnext = tempnext Assign temp to tprev part Set tprev = temp Assign t to tempnextprev part Set tempnextprev = t Assign t to tempnext part Set tempnext = t Endif End

Step 11 Step 12

Step 13 Step 14 Step 15 Step 16 Step 17 Step 18 Step 19 Step 20 Step 21

Delete at first NODE


void atfirst(NODE **start) Step 1 Begin Step 2 Assign value of (*start) to temp Step 3 Assign tempnext to (*start)

[Set temp = (*start) ] [Set (*start) = temp next]

Step 4 Step 5 Step 6 End

Assign NULL to (*start)prev part Free temp pointer [Set free(temp)]

[Set (*start) prev = NULL]

Delete at Last NODE


First Method void atlast( NODE **start) Step 1 Begin Step 2 Assign value of (*start) to temp [Set temp = (*start) ] Step 3 WHILE LOOP BEGIN while temp next not equal to NULL do Assign temp to t [Set t = temp ] Assign tempnext to temp [Set temp = temp next] End while Step 4 if *start next equal to NULL than Assign NULL to *start and *tail [Set *tail = *start = NULL] Endif Step 5 Assign NULL to t next [Set t next = NULL] Step 6 Set t = *tail Step 7 Set free temp pointer Step 8 End

Second Method
void atlast(NODE **start, NODE **tail) Step 1 Begin Step 2 Assign *tail to temp pointer and tempprev to t Pointer Set temp = (*tail) Set t = tempprev Step 3 if (*tail) prev equal to NULL and (*tail) next equal to NULL than Set *tail = *start = NULL Set free temp pointer Endif Step 4 Set *tail = t Step 5 Assign NULL to t next [Set t next = NULL] Step 6 Free temp poinbter

Step 7 End

Delete a node at given position


void delposi(NODE **start, int pos) Step 1 Step 2 Step 3 Step 4 Step 5 Begin Assign value of *start to temp Set temp = (*start) Check if equal to 1 than Assign tempnext to *start [Set *start = temp next] Assign NULL to (*start) prev Set *start prev = NULL Set Free temp pointer else For Loop Begin for i equal to 1 in order to i less than and equal to pos -1 with one increment do Set t = temp Set temp = temp next Check if temp equal to NULL than Display Position not found Return Endif End for loop Assign value of tempnext to tnext Set tnext = tempnext Assign value of t to tempnextprev Set tempnextprev = t Free temp Set Free temp pointer Endif if tnext equal to NULL than Set *tail = t End

Step 6 Step 7

Step 12 Step 13

Step 14 Step 15 Step 16 Step 17

You might also like