The names of vegetables must be always held in alphabetical order in a list in the main memory. The application program should allow insertion and deletion of the names of vegetables from this list.
Compare the use of a dynamic linked list for holding these names of vegetables with a static one-dimensional array.
Award [1] for each comparison, up to [3 max]. The size of the dynamic list does not have to be predetermined as in an array; The size of the dynamic list is not fixed whilst the size of an array is always fixed; If names are sorted they can be added/deleted (more easily) by changing the pointers without having to shuffle the names; As records can be dynamically added/deleted the memory is better used because there are no wasted / missing spaces as in an array;
Sketch a single linked list holding these vegetables: potato, asparagus, lettuce, radish.
Award [1] for a node containing two fields / data(name) and link (pointer) to the next node and [1] for showing an external pointer pointing to the first vegetable on the list, and null pointer in the last node, and pointers which link the nodes in alphabetical orderup to [2 max].
List the steps required to insert cabbage into the linked list.
Award [1]for each step identified up to [4 max]. Create a new node containing cabbage; Traverse the list (from the beginning) to find the place to insert a new node; Cabbage should be inserted before lettuce and after asparagus; The pointer in new (cabbage) node should be set to point to the node that is before the insertion point / lettuce; The pointer in node before insertion point / asparagus / should now point to the new node / cabbage; Note: award marks for clearly labelled diagrams in candidates'answers.
Explain why deleting the first node in this list is different to deleting other nodes.
Award [1]for identifying a reason why deleting the first node is different to deleting other nodes and [1] for an expansion up to [2 max]. External pointer (First) must be changed/only in situation when deleting the beginning node the external pointer must be changed; And set to the pointer in the link field of the first node (Asparagus) which points to the second node/Lettuce;
State the dynamic data structure suitable for maintaining this list of vegetables which will allow faster searching for a given vegetable name.
Sketch the data structure suggested in part containing the vegetable names sorted in alphabetical order. The vegetable names are input in the following order: potato, asparagus, lettuce, radish.
