A linked list is an example of an Abstract Data Type (ADT). A linked list is implemented using a 1D array for the data items, a 1D array for the link pointers, and a start pointer. The linked list maintains the data items in alphabetical order.

The state of the linked list after five data items have been added is:

the linked list after five data items have been added, drawn as linked boxes: a start pointer box holding 5, pointing to a box labelled ANT with pointer value 3, then a box labelled BISON with pointer value 2, then a box labelled DOG with pointer value 1, then a box labelled LEOPARD with pointer value 4, then a box labelled ZEBRA with pointer value 0

Complete the diagram to show the StartPointer and the contents of the arrays Data and Pointer, for array indexes 1 to 5 (indexes 6 to 20 stay unused).

Array index	Data	Pointer
StartPointer		Table answer start_Pointer
1	Table answer r1_Data	Table answer r1_Pointer
2	Table answer r2_Data	Table answer r2_Pointer
3	Table answer r3_Data	Table answer r3_Pointer
4	Table answer r4_Data	Table answer r4_Pointer
5	Table answer r5_Data	Table answer r5_Pointer

6(b)Linked ListsEasy1 mark

State what the pointer value 0 (null pointer) indicates.

6(c)(i)Linked ListsMedium1 mark

To maintain the linked list, algorithms are required to insert a new data item into the linked list and to delete a data item from the linked list. The data item 'DOG' is to be deleted from the linked list given in 6(a). Complete the diagram to show the new state of the linked list.

Draw with the mouse or a finger.

6(c)(ii)Linked ListsMedium2 marks

To delete a data item, the algorithm will have special cases. One special case is the linked list is empty. Describe two other special cases which must be considered when deleting a data item.

Answer

0 words

6(d)Linked ListsHard6 marks

The linked list given in 6(a) is repeated here. Data item 'BAT' is to be added to the linked list.

the linked list from part (a) repeated: a start pointer box holding 5, pointing to a box labelled ANT with pointer value 3, then a box labelled BISON with pointer value 2, then a box labelled DOG with pointer value 1, then a box labelled LEOPARD with pointer value 4, then a box labelled ZEBRA with pointer value 0

Describe how the data item 'BAT' is added to the linked list. Do not attempt to write pseudocode.

Answer

0 words