Algorithms for the Main Data Structures (OCR A Level Computer Science)

Lucas writes a program that makes use of a circular queue. The queue stores the data entered into the program. An array is used to represent the queue.

The program needs two pointers to access and manipulate the data in the queue.

State the purpose of the two pointers and give an appropriate identifier for each.

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

The function findNode will search the linked list and return either the position of the node that contains the data item, or -1 if the data item is not found.

The data held in a node at location x can be accessed with linkedList[x].data. The pointer of the node at location x can be accessed with linkedList[x].pointer.

For example, using the linked list shown in Fig. 3: linkedList[2].data returns green.
linkedList[2].pointer returns 8.

Complete the function, using pseudocode or program code.

function findNode(toFind, headPointer, linkedList)

  currentNode = ………………………………

  while(currentNode != ………………………………)

   if linkedList[currentNode]. ……………………………… == toFind 

    return currentNode

  else

   currentNode = linkedList[………………………………].pointer

  endif

 endwhile

 return ………………………………

 endfunction