Algorithm createList (list)
Initializes metadata for list.
Pre list is metadata structure passed by referece
Post metadata initiazed
1 allocate (list)
2 set list head to null
3 set list count to 0
End createList
Algorithm insertNode(list, pPre, dataIn)
Inserts data into a new node in the list.
Pre list is metadata structure to a valid list
pPre is pointer to data’s logical predecessor
dataIn contains data to be inserted
Post data have been inserted in sequence
Return true if successful. False if memory overflow
1 allocate (pNew)
2 set pNew data to dataIn
3 if (pPre null)
Adding before first node or to empty list.
1 set pNew link to list head
2 set list list head to pNew
4 else
Adding in middle or at end.
1 set pNew link to pPre link
2 set pPre link to pNew
5 end if
6 return true
End insertNode
Algorithm deleteNode (list, pPre, pLoc, dataOut)
Deletes data from list & returns it to calling module.
Pre list is metadata structure to a valid list
pPre is poiter to predecessor node
pLoc is a pointer to node to be deleted
dataOut is variable to receive deleted data
Post data have been deleted and returned to caller
1 move pLoc data to dataOut
2 if (pPre null)
Deleting furst node
1 set list head to pLoc link
3 else
Deleting other nodes
1 set pPre link to pLoc link
4 end if
5 recycle (pLoc)
end deleteNode
Algorithm searchList (list, pPre, pLoc, target)
Searches list ad passes back address of node containing Target and its logical predecessor.
Pre list is metadata structure to a valid list
pPre is pointer variable for predecessor
pLoc is pointer variable for current node
target is the key being sought
Post pLoc points to first node with equal/greather key
-or- null if target > key of last node
pPre points to largest node smaller than key
-or- null if target < key of fiest node
Return true if found, false if nod found
1 set pPre to null
2 set pLoc to list head
3 loop (pLoc nod null AND target > pLoc key)
1 set pPre to pLoc
2 set pLoc to pLoc link
4 end loop
5 if (pLoc null)
Set return value
1 set found to true
6 else
1 if (target equal pLoc key)
1 set found to true
2 else
1 set found to false
3 end if
7 end if
8 return found
End searchList
Algorithm retreveNod (list, key, dataOut)
Retrieves data from a list.
Pre list is metadata structure to a valid list
Key is target of data to be retrieved
dataOut is variable to receive data
Post data placed in dataOut
-or- error returned if not found
Return true if successful, false if data not found
1 set found to searchList (list, pPre, pLoc, key)
2 if (found)
1 move pLoc data to dataOut
3 end if
4 return found
end retrieveNode
Algorithm emptyList (list)
Returns Boolean indicating whether the list is emply.
Pre list is metadata structure to a valid list
Return true if list empty, false if list contains data
1 if (list count equal 0)
1 return true
2 else
1 return false
end emptyList
Algorithm fullList (list)
Returns Boolean indicating whether or not the list is full.
Pre list is metadata structure to a valid list
Return false if room for ew node; true if memory full
1 if (memory full)
1 return true
2 else
1 return false
3 end if
4 return true
end fullList
Algorithm listCount (list)
Returns integer representing number of nodes in list.
Pre list is metadata structure to a valid list
Return count for number of nodes in list
1 return (list count)
end listCount
Algorithm getNext (list, fromWhere, dataOut)
Traverses a list. Each call returns the location of an element in the list.
Pre list is metadata Structure to a valid list
FromWhere is 0 to start at the first element
dataOut is reference to data variable
Post dataOut contains data and true returned
-or- if end of list, returns false
Return true if next element located
false if end of list
1 if (empty list)
1 return false
2 if (fromWhere is beginning)
Start from first
1 set list pos to list head
2 move current list data to dataOut
3 return true
3 else
Continue from pos
1 if (end of list)
End of list
1 return false
2 else
1 set list pos to next node
2 move current list data to node
3 return true
3 end if // added in [3]
4 end if
end getNext
Algorithm destroyList (pList) // [3]p.118
Deletes all data in list.
Pre list is metadata structure to a valid list
Post all data deleted
1 loop (not at end of list)
1 set list head to successor node
2 release memory to heap
2 end loop
No data left in list. Reset metadata.
3 set list pos to null
4 set list count to 0
end destroyList