Linked List (Ordered)

TYPE Node DECLARE data, pointer : INTEGER ENDTYPE DECLARE list : ARRAY[1:5] OF Node DECLARE freeListPointer, headPointer : INTEGER CALL Reset() CALL AddNode(3) CALL AddNode(2) CALL AddNode(5) CALL AddNode(1) CALL AddNode(4) CALL RemoveNode(5) CALL RemoveNode(1) CALL RemoveNode(3) CALL AddNode(7) CALL AddNode(6) CALL AddNode(8) FOR n ← 0 TO 8 OUTPUT n, ": ", Search(n) NEXT n CALL OutputListArray() CALL OutputListPretty() PROCEDURE Reset() DECLARE currentPointer : INTEGER //create the free list - all nodes have data of -1 and point to the subsequent node FOR currentPointer ← 1 TO LENGTH(list) - 1 list[currentPointer].data ← -1 list[currentPointer].pointer ← currentPointer + 1 NEXT currentPointer list[LENGTH(list)].data ← -1 list[LENGTH(list)].pointer ← -1 //last node points to null pointer headPointer ← -1 //head is null = empty list freeListPointer ← 1 //free list starts at index 1 ENDPROCEDURE //add node at correct position (in ascending order) PROCEDURE AddNode(data : INTEGER) DECLARE currentPointer, previousPointer, newNodePointer : INTEGER //check list not full IF freeListPointer <> -1 THEN //use first node from free list to be new node newNodePointer ← freeListPointer list[newNodePointer].data ← data //add data to new node freeListPointer ← list[freeListPointer].pointer //update freeListPointer to point to next available free list node //start searching from beginning of list currentPointer ← headPointer previousPointer ← -1 //while not end of life and not found position to add WHILE currentPointer <> -1 AND list[currentPointer].data < data DO previousPointer ← currentPointer currentPointer ← list[currentPointer].pointer //go to next node ENDWHILE //if insert at start IF previousPointer = -1 THEN list[newNodePointer].pointer ← headPointer //new node should point to previous first node headPointer ← newNodePointer //set new node as being the first node ELSE list[newNodePointer].pointer ← list[previousPointer].pointer //make new node point to next node list[previousPointer].pointer ← newNodePointer //make previous node point to new node ENDIF OUTPUT "Added: ", data ELSE OUTPUT "List full" ENDIF ENDPROCEDURE //find an element in an ordered linked list FUNCTION Search(data : INTEGER) RETURNS BOOLEAN DECLARE currentPointer : INTEGER //start searching from beginning currentPointer ← headPointer //search while not at end of list and current node's data is <= search data - since otherwise, we have passed where that value would be if it existed, hence can stop searching WHILE currentPointer <> -1 AND list[currentPointer].data <= data DO //if found IF list[currentPointer].data = data THEN RETURN TRUE ENDIF currentPointer ← list[currentPointer].pointer //go to next node ENDWHILE //if searched all possible positions on not found node, then it doesn't exist RETURN FALSE ENDFUNCTION PROCEDURE RemoveNode(data : INTEGER) DECLARE currentPointer, previousPointer : INTEGER DECLARE found : BOOLEAN found ← FALSE //not found node we're removing currentPointer ← headPointer //start searching from head previousPointer ← headPointer //can't use -1, so also start from head //while not end of list, not removed node and not passed node's possible position WHILE currentPointer <> -1 AND found = FALSE AND list[currentPointer].data <= data DO //if found IF list[currentPointer].data = data THEN //set previous node's pointer to pointer to this node's pointer - effectivelly 'cutting out' the current node by bypassing it list[previousPointer].pointer ← list[currentPointer].pointer //if removing the first element IF currentPointer = headPointer THEN headPointer ← list[currentPointer].pointer //make the head point to the 2nd node (might be null pointer if only 1 node) ENDIF //add removed node to beginning of free list list[currentPointer].pointer ← freeListPointer freeListPointer ← currentPointer OUTPUT "Removed: ", data found ← TRUE ENDIF previousPointer ← currentPointer //set previous pointer for next loop iteration currentPointer ← list[currentPointer].pointer //go to next node ENDWHILE IF found = FALSE THEN OUTPUT "Didn't remove ", data, " - it doesn't exist in list" ENDIF ENDPROCEDURE PROCEDURE OutputList() DECLARE currentPointer : INTEGER currentPointer ← headPointer //loop while nodes are remaining WHILE currentPointer <> -1 DO OUTPUT list[currentPointer].data currentPointer ← list[currentPointer].pointer //go to next node ENDWHILE ENDPROCEDURE PROCEDURE OutputListPretty() DECLARE line : STRING DECLARE currentPointer : INTEGER OUTPUT "--- List ---" currentPointer ← headPointer line ← "" //loop while nodes are remaining WHILE currentPointer <> -1 DO line ← line & NUM_TO_STR(list[currentPointer].data) currentPointer ← list[currentPointer].pointer //go to next node //add "->" seperator if not last node IF currentPointer <> -1 THEN line ← line & " -> " ENDIF ENDWHILE OUTPUT line OUTPUT "" ENDPROCEDURE //a "helper" procedure to display the contents of the linked list array for debugging/understanding - note, you won't need to write this in the exam (unless they specifically ask you to create a helper method to visualise the array contents) PROCEDURE OutputListArray() DECLARE index : INTEGER OUTPUT "Head Pointer: ", headPointer OUTPUT "Free List Pointer: ", freeListPointer //index, data, pointer OUTPUT " I | D | P" FOR index ← 1 TO LENGTH(list) OUTPUT " ", index, " | ", list[index].data, " | ", list[index].pointer NEXT index ENDPROCEDURE