IB COMPUTER SCIENCE HL

Maximum mark: $15]$

Consider the following circular linked list:

where head is an external pointer that points to the first node in the circular linked list.

Three operations are performed on this circular linked list in the following order:

$1$ A node containing the number $30$ is inserted at the beginning of the circular linked list.

$2$ The last node is deleted from the circular linked list.

$3$ The first node is deleted from the beginning of the circular linked list.

$($a$)$ Sketch a diagram showing the resulting circular linked list.$[3]$

Complete here or on another sheet of paper

$($b$)$ Outline how the last node of the circular linked list is identified. $[2]$

Complete here or on another sheet of paper

$($c$)$ Describe the steps required to calculate the sum of all numbers held in this

circular linked list. $[4]$

Respond here

$($d$)$ Compare the use of arrays and linked lists.$[4]$

Respond here

$($e$)$ A linked list can be used to implement a data structure queue. Identify two

applications of a queue data structure.$[2]$

Respond here

$[$Maximum mark: $3]$

Sketch a double linked list that holds the following sequence of names: Anne, Lana,

Mary.$[3]$

Complete here or on another sheet of paper

$[$Maximum mark: $3]$

Compare the use of a linked list with an array to store and process the daily sales in a

business.$[3]$

Respond Here