Searching operation on header linked list

Searching operation on header linked list 

Algorithm:SEARCH(HEAD,ITEM)- given a non empty unsorted header linked list LIST in memory and address of the first node is stored in LINK(HEAD) .this algorithm find and returns the location LOC of the note where item is first appeared in the list if search  is successful or set Loc = Null if  search is unsuccessful .here  LOC is a local variable

1. LOC àNULL

2. PTRàLINK(HEAD)

[ search for item ]

3. repeat step 4  for while PTR≠ NULL and ITEM ≠INFO(PTR)

4. PTRàLINK(PTR)

[ end of step 3 loop]

5.  if ITEM =INFO(PTR) then [successful]

PTRàLOC

[end of if structure]

6. Return LOC

Deletion operation on header linked list

Algorithm:DELETE (HEAD ,AVAIL, LOC):- given list be a header linked list in memory and LINK(HEAD) pointer pointing to its first node this algorithm delete a node pointed by LOC where we are using local variable PTR to find the desired node to be deleted and PREVLOC  to keep track of its predecessor . The local variable AVAIL point to the first node of the free storage list.

      [ empty list?]

1.  if LINK(HEAD) = NULL then

 write “underflow in linked list”

 return PTR

[end of if structure]

2. PTRàLINK(HEAD)

[ set PTR to LINK(HEAD) i.e. first node of header linked list and PREVLOC to head ]

PREVLOC àHEAD

3. [ find location so as to find predecessors location that is PREVLOC]

 Repeat while PTR≠ LOC and  LINK (PTR)≠ NULL

[update pointers]

a) PREVLOC àPTR

b) PTR àLINK(PTR)

[end of step 3 loop]

4. If PTR≠LOC

 then write “ node not found”

 return

[end of if structure]

5. [ delete node appointed by LOC]

If PREVLOC=NULL  then

[deleting first node]

LINK(HEAD)àLINK(PTR)

else

LINK(PREVLOC) àLINK(LOC)

[end of its structure]

6. [ Return deleted notes to free storage list]

a)LINK(LOC) àLINK(AVAIL)[here AVAIL is also a headerd linked list of available nodes]

b)LINK(AVAIL) àLOC

7. Return