Week 8 Tutorial — Sample Solutions

1. In the notation below, the contents of the stack is indicated by << >>, with the top on the left.
   In other words: <<top, ... >>
   • pop removes an element from the top of stack
   • push places an element on the top of stack

   Initially: << >> After push 1: <<1>> After push 5: <<5, 1>> After push 3: <<3, 5, 1>> After pop: <<5, 1>> After push 4: <<4, 5, 1>> After push 2: <<2, 4, 5, 1>> After pop: <<4, 5, 1>> After pop: <<5, 1>> After pop: <<1>> After pop: << >>

   • the sequence will be: 3 2 4 5 1

2. In the notation below, the contents of the queue is indicated by << >>, with the start on the left and the end on the right
   In other words: <<start, ..., end>>
   • dequeue removes an element from the start of queue
   • enqueue places an element at the end of queue

   Initially: << >> After enqueue 1: <<1>> After enqueue 5: <<1, 5>> After enqueue 3: <<1, 5, 3>> After dequeue: <<5, 3>> After enqueue 4: <<5, 3, 4>> After enqueue 2: <<5, 3, 4, 2>> After dequeue: <<3, 4, 2>> After dequeue: <<4, 2>> After dequeue: <<2>> After dequeue: << >>

   • the sequence will be: 1 5 3 4 2

3. 1. The new node is being placed at the head of the list, but it will not work because the head is not being returned. The code should be:

      NodeT *insertHead(NodeT *head, int v) { // create new node with data NodeT *new = (NodeT *)malloc(sizeof(NodeT)); assert (new != NULL); new->data = v; new->next = head; return new; }

      This is called head insertion.

   2. Insert a node at the end of a linked list (called tail insertion):

      NodeT *insertTail(NodeT *head, int v) { // create new node with data NodeT *new = (NodeT *)malloc(sizeof(NodeT)); assert (new != NULL); new->data = v; new->next = NULL; if (head != NULL) { // check if at least 1 node NodeT *cur; cur = head; // start at the head while (cur->next != NULL) { // this must be defined cur = cur->next; } cur->next = new; // cur->next was NULL } else { head = new; } return head; }

4. • Right rotation
   1. copy strategy:
      1. Starting at the second node, traverse the list, copying previous node's data field into the current node (using a temporary variable to always 'remember' the latest data value before overwriting it).
      2. When you reach the end, copy the last node's data to head node
      3. The original head node remains the head node
      This is a data-based strategy. The links are not affected.
   2. relink strategy:
      1. The 'penultimate' node should point to NULL.
      2. The last node should point to the original head node.
      3. The last node becomes the new head.
      This is a link-based strategy. The data is not affected.
   • Left rotation
   1. copy strategy:
      1. Starting at the second node (and using a second pointer to always remember the previous node), traverse the list, copying the current node's data into the previous node's data field.
      2. When you reach the end node, overwrite the data with the head node's data
      3. The original head node remains the head node
   2. relink strategy:
      1. Let the head node point to NULL
      2. The last node should point to this head node
      3. The second node is the new head

   • Special cases:
   • if the linked list is empty or consists of just one node then no rotation should take place.

   Variations of the 2 strategies are of course possible.

5. An implementation of a duplicate checker:

   // assumes the linked list is sorted int hasDupList(NodeT *head) { // 1 if dup found, otherwise 0 int found = 0; if (head != NULL && head->next != NULL) { // need at least 2 nodes NodeT *cur; cur = head; while (cur->next != NULL && !found) { // walk the list if (cur->data == cur->next->data) { found = 1; // we found a dup } else { cur = cur->next; } } } return found; }