Linked list Algorithm 2

Header Linked List:

It has two types: Circular header linked list and grounded header linked list.

In circular, the last node is linked to the header node and in grounded, the last node is linked to the NULL.

Traversing in a circular header linked list

  1. Set PTR = LINK [START]                                        //initializing a pointer
  2. Repeat step 3 and 4, while PTR ≠ START       //PTR ≠ NULL for grounded list
  3. Apply PROCESS to INFO [PTR]
  4. Set PTR = LINK [PTR]                                           //PTR points to the next node

[End of while loop]

  1. Exit

 

Two way linked list

Insertion (INFO, NEXT, PREV, AVAIL, LOCA, LOCB, ITEM)

  1. If AVAIL = NULL, then write: Overflow and Exit                             //checking for overflow
  2. Set NEW = AVAIL, AVAIL = NEXT [AVAIL], INFO [NEW] = ITEM.

                                                             //removing node from AVAIL list and copy the ITEM into it

  1. Set NEXT [LOCA] = NEW, NEXT [NEW] = LOCB,

PREV [LOCB] = NEW, PREV [NEW] = LOCA                                 //inserting node into the list

  1. Exit.

//INFO: Data part of the node

//NEXT: Next pointer of the node

//PREV: Previous pointer of the node

//AVAIL: First node of the AVAIL list

//LOCA and LOCB: Locations in which the new node is to be inserted.

Deletion (INFO, NEXT, PREV, AVAIL, LOC)

  1. Set NEXT [PREV [LOC]] = NEXT [LOC] and PREV [NEXT [LOC]] = PREV [LOC]

//deleting node

  1. Set NEXT [LOC] = AVAIL and AVAIL = LOC //inserting node to the AVAIL list
  2. 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