Linked List General Algorithms(Traversal,Searching,Insertion,Deletion)

TRAVERSING:

Let list be a linked list in memory, this algorithm TRAVERSE_LIST applying & operation PROCESS to each element of LIST. The variable PTR point to the nodes currently being processed.

Step 1:-set PTR=START [initialize pointer PTR]

Step 2:-repeat step 3 & step 4 while PTR! = NULL

Step 3:-apply PROCESS to INFO[PTR]

STEP 4:-SET PTR=LINK [PTR]

[PTR now points to the next node]

End of step 2 loop

Step 5:-exit

 

SEARCHING:

Let list be a linked list in memory, this algorithm SEARCH_LIST applying & operation PROCESS to each element of LIST. The variable ITEM point to the nodes currently being processed.

SEARCH (INFO,LINK,START,ITEM,LOC)

LIST is a linked list in memory , this algorithm finds the location LOC of the node

where ITEM first appears in LIST or sets , LOC=NULL.

Step 1:-set PTR=START[initialize pointer PTR]

Step 2:-repeat step 3 while PTR ! = NULL

Step 3:-if ITEM = INFO[PTR]

Then set LOC = PTR & exit

Else

Set PTR = LINK[PTR]

[PTR now points to next node]

[End of if structure]

End of step 2 loop

Step 4:-[Search is unsuccessful]

Set LOC = NULL

Step 5:-Exit

INSERTION:

Let list be a linked list in memory, this algorithm INSERT_LIST applying & operation PROCESS to each element of LIST. The variable ITEM point to the nodes currently being processed.

Inserting the node at the beginning of the list:-

INSERT (INFO, LINK, START, AVAIL, ITEM)

Step 1:-[over flow?]

If AVAIL = NULL, then write over flow & exit

Step 2:-[REMOVE first node from AVAIL LIST]

Set NEW = AVAIL & AVAIL = LINK [AVAIL]

Step 3:-set INFO [NEW] = ITEM

[Copy is new data into new node]

Step 4:-set LINK [NEW] = START

[New node now points to original first node]

Step 5:-set START = NEW

[changes start so its point to new node]

Step 6:-exit

Inserting after a given node:-

INSLOC (INFO, LINK, START, AVAIL, LOC, ITEM)

This algorithm inserts ITEM. so that ITEM follows the node with location

[LOC] or insert ITEM as the first node when LOC = NULL

Step 1:-[over flow] if AVAIL = NULL, then write overflow & exit.

Step 2:-[Remove first node from AVAIL list]

Set NEW = AVAIL & AVAIL = LINK [AVAIL]

Step 3:-set INFO [NEW] = ITEM

[Copy is new data into new node]

Step 4:-if LOC = NULL, then [insert as first node]

Set LINK [NEW] = START & START = NEW

Else

[INSERT after node with location LOC]

Set LINK [NEW] = LINK [LOC] and LINK [LOC] = NEW

[End of if]

Step 5:-Exit

DELETION: 

Let list be a linked list in memory, this algorithm DEL LIST applying & operation PROCESS to each element of LIST. The variable INFO point to the nodes currently being processed.

Deletion from a linked list:-

DEL (INFO, LINK, START, AVAIL, LOC, LOCP)

This algorithm deletes the node N with location LOC, LOCP is the location

of the node LOCP = NULL.

Step 1:-if LOCP = NULL, then set = START=LINK [START]

[Delete first node]

Else

Set = LINK [LOCP] = LINK [LOC]

[Deletes node N]

[End of if]

Step 2:-[Return deleted node to the AVAIL LIST]

Set = LINK [LOC] = AVAIL & AVAIL = LOC

Step 3:-Exit