Question 6: (a) The code below reverses the order of items in a plain C++ array.

Question

Question 6: (a) The code below reverses the order of items in a plain C++ array. Explain the logic briefly. Can the same approach be used with a singly-linked list? What about a doubly-linked list? Justify your answers precisely. (3 marks) for int i = 0, j size-1; i size/2; i++, j-) { int v items [i]; items [1] items [j]; items [j] = v; } = = (b) Write the C+ function below that will reverse any singly-linked list starting at head, reversing all node pointers as illustrated below. (5 marks) void reverse Node*& head ) (c) Explain what Node'& is and why we need and & in the above. (1 mark)

Explanation / Answer

(A) We can't use the same approach in case of a singly or a doubly linked list because, the above program is swapping the i th element from the starting and the ending. But we can't directly access any element at an index in case of linked list as we can do in an array as linked list are not continuous structures like arrats are. So, the different nodes are not adjacent to each other in the memory.

(B)

void reverseList(Node*& head)

{

    // point trav to the head of the list

    Node *trav = head;

    // points to the node previous to the node pointed by trav

    Node *pre = NULL;

    // points to the node next to the node pointed by trav

    Node *ptr = NULL;

    // traverse through the list

    while (trav != NULL)

    {

        // make previous point to the next node of the current node

        ptr = trav->next;

        // make current ndoe point to the previous node

        trav->next = pre;

        // move the pointers to next nodes

        pre = trav;

        trav = ptr;

    }

   

    // update the new head of the list

    head = pre;

}

(C) Node* is the pointer to the node in the linked list. Node*& is the reference to the pointer to the node in the linked list. We need to use * as the node variable is dynamically created usign a pointer. So, we represent the node using a pointer. We use a & as we need to pass the reference to the pointer to the node so that any changes to the variable passed as argument inside the function will also reflect the change in the original variable.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.