Given the following list structure:

template class Link {

public:

Elem element; // Value for this node

Link *next; // Pointer to next node

};

template

class LList : public List {

private:

Link* head; // Point to list header

Link* tail; // Pointer to last Elem

Link* fence; // Last element on left

bool insert(const Elem& item) {

fence->next = new Link(item, fence->next);

if (tail == fence) tail = fence->next;

return true;

}

void print() const {

Link* temp = head;

cout

while (temp != fence) {

cout next->element

temp = temp->next;

}

cout

while (temp->next != NULL) {

cout next->element

temp = temp->next;

}

cout

}

}

Given that score is a variable of List and its values are:

a)

What is the output of score.print()?

(5 marks)

b)

Draw the linked list including the head, fence and tail pointers after executing

score.insert(2).

(5 marks)

c)

Assume Elem and Link cost 32 and 8 bytes. Calculate the overhead fraction for the singly

linked list.

(3 marks)

d)

List one advantage and one disadvantage of singly list comparing with array-based list?

(4 marks)

[17 marks) Given the following list structure: template class Link { public: Elem element; // value for this node Link *next; 77 Pointer to next node }; template class LList : public List { private: Link Elem>* head; // Point to list header Link* tail; // Pointer to last Elem Link Elem>* fence; 77 Last element on left bool insert (const Elem& item) { fence->next = new Link(item, fence->next); if (tail == fence) tail = fence->next; return true; } void print() const { Linknext->element next; } cout next != NULL) { cout next->element next; } cout