Algorithms in Linked List

Algorithms in Linked List

Traversing:

  1. Initialize the Current pointer with the beginning of the List.
  2. Move the Current pointer to point to the next node in the list and go to step-1, till the list is not over or else quit.

Searching:

  1. Initialize the Current pointer with the beginning of the List.
  2. Compare the KEY value with the Current node value; if they match then quit here.                                else go to step-3.
  3. Move the Current pointer to point to the next node in the list and go to step-2, till the list is not over or else quit.

Insertion :

  1. Get the value for NEW node to be added to the list and its position.
  2. Create a NEW, empty node by calling malloc(). If malloc() returns no error then go to step-3 or else say “Memory shortage”.
  3. Insert the data value inside the NEW node’s data field.
  4. Add this NEW node at the desired position (pointed by the “location”) in the LIST.
  5. Go to step-1 till you have more values to be added to the LIST.

At Beginning:

Insert_At_Beg (INFO, START, NEXT)

  1. Create a new node and assign the address to any node say PTR.
  2. Overflow, If(PTR = NULL)
    1. write: Overflow and EXIT.
  3. Assign INFO[PTR] = ITEM                         //assigning the data
  4. If(START = NULL)
    1. Assign NEXT[PTR] = NULL
    2. Else
    3. Assign NEXT[PTR] = START
  5. Assign START = PTR                               //inserting in the beginning
  6. Exit.

 

At Any Loc:

Insert_At_loc_(INFO, NEXT, START, END, LOC, SIZE)

  1. Set NLOC = LOC-1 , N=1
  2. Create a new node and address in assigned to PTR.
  3. Check[overflow] if(PTR==NULL)

write: overflow and exit

  1. Set INFO[PTR]=ITEM;
  2. if(START=NULL)

set NEXT[PTR] = NULL

set START = PTR

else if(NLOC<=SIZE)

repeat steps a and b while(N != NLOC)

  1. LOC = NEXT[LOC]                                        //changing the location
  2. N = N+1

[end of while statement]

NEXT[PTR] = NEXT[LOC]

NEXT[LOC] = PTR                            //inserting after LOC

else

set LAST = START;

repeat step (a) while(NEXT[LAST]!= NULL)

  1. LAST=NEXT[LAST]

[end of while statement]

LAST->NEXT = PTR ;

[end of if statement]

  1. Exit.

Deletion:

From The beginning:

Delete At Beg(INFO, NEXT, START)

  1. If(START=NULL), Underflow & Exit
  2. Assign PTR = START
  3. Assign TEMP = INFO[PTR]
  4. Assign START = NEXT[PTR]
  5. Free(PTR)                                             //deleting the node
  6. Return(TEMP)
  7. Exit.

 

From The End:  

Delete End(INFO, NEXT, START)

  1. if(START=NULL)

Print Underflow and Exit.

  1. if(NEXT[START]==NULL)

Set PTR =START and START=NULL.

Set TEMP = INFO[PTR].

else CPTR = START and PTR = NEXT[START].

Repeat steps(a) and (b) while(NEXT[PTR]!=NULL)

(a) set CPTR = PTR

(b) set PTR = NEXT[PTR]

[end of while statement]

set NEXT[CPTR] = NULL

TEMP = INFO[PTR]

[end of if statement]

  1. FREE(PTR)                                      // deleting the node
  2. return TEMP
  3. Exit

 

Author: Indrajeet Gupta

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s