Tutorial Solutions Week 1

A file with all the code solutions for exercise 2 and its helper functions can be found here: ListsAlternate_sol.c

Exercise 1 - Linked Lists

1. Consider the material on linked lists that we discussed in the lecture with the following definition (Item is a char now):

   typedef char Item;
   
   typedef struct node *link;
   
   struct node {
     Item item;
     link next;
   };
   

   Write the following functions:

   • A function called length that takes a link to the first element of a list and returns the length of the list

   int length (link ls) {
      link curr;
      int len = 0;
      for (curr = ls; curr != NULL; curr = curr->next) {
          len++;
      }
      return len;
   }
   
   
   

   An alternate recursive solution

   int length(link ls) {
       if (ls == NULL) {
           return 0;
       }
       return 1 + length(ls->next);
   }
   

   • A function called duplicate that takes a link to the first element of a list as an argument and returns a copy of the list (ie a new list that contains the same data, in the same order).

   link duplicate (link ls) {
       link new = NULL;
       link curr;
   
       if (ls != NULL) {
           new = newNode (ls->item);
           curr = new;
           ls = ls->next;
       }
       while (ls != NULL) {
           insertNext (curr, newNode (ls->item));
           curr = curr->next;
           ls = ls->next;
       }
       return new;
   }
   

   An alternate recursive solution

   link duplicate(link ls) {
       link new;
       if (ls == NULL) {
           return NULL;
       }
       new = newNode(ls->item);
       new->next = duplicate(ls->next);
       return new;
   }
   
   

   • Here are the prototypes for some functions you may wish to use for this task (you can take the code from the lecture)

   // Create a new node, initialised with the item provided. Return
   // pointer to node (link)
   link newNode (Item item);
   
   // Insert a new node into a given non-empty list
   // The node is inserted directly after the head of the list ls
   void insertNext (link ls, link node);
   
   

2. Assume we have a function printList which, given a list of characters, prints each character, and a function `cstrToList` which converts a regular C string (i.e., `\0` terminated array of characters) into a list of characters. What is the output of the following program? (See implementation of reverse in Exercise 2.)

   int main (int argc, const char * argv[]) {
     link ls = cstrToList ("hello world!");
     link ls2 = duplicate(ls);
     printList (ls);
     printList (reverse (ls));
     printList (ls);
     printList (ls2);
     return 0;
   }
   

List elements: hello world!
List elements: hello world!
List elements: !dlrow olleh
List elements: h
List elements: hello world!

reverse returns a pointer to the beginning of the reversed list, so when we print it out using printList(reverse (ls)); we get the list printed in reverse as we would expect. However, we did not assign the beginning of the reversed list back to our ls variable, so it is still pointing to the original head of the list which has the item 'h' in it. This node has now been modified to point to NULL during the reverse function, so printing out the ls list now results in simply an 'h' being printed out. If we wanted our ls variable to now contain the list in reverse we would have had to have used the return value as such ls = reverse(ls) . The duplicate list, ls2, as we would hope, has not been changed by calling the reverse function, as it has its own copies of all the nodes.

Exercise 2 - Linked Lists, an alternative implementation

• The following implementation of lists distinguishes between a link to a sequence of items and a list. The list contains additional information, in this case, the length and also a pointer to the last element of the list.

  typedef char Item;
  
  typedef struct node *link;
  
  struct node {
    Item item;
    link next;
  };
  
  typedef struct listImpl *list;
  
  struct listImpl {
    int size;
    link first;
    link last;    
  };
  
  

• Write a function called createList to create a new empty list. Discuss the difference between an empty list in our original implementation and our current implementation.

  list createList(void){
      list newList = malloc(sizeof ( *newList ));
      newList->first = NULL;
      newList->last = NULL;
      newList->size = 0;
      return newList;
  }
  

  In the original implementation an empty list is simply a list with no nodes, set to NULL with no memory allocated to it. In the new implementation an empty list actually has a piece of memory allocated to it and is a listImpl struct, with a size field set to 0, and first and last pointers set to NULL.

• Modify the length function you wrote in excercise 1 to work with our new implementation.

  int length(list ls){
     int len = 0; 
     if(ls != NULL){
         len = ls->size;       
     } 
     return len;
  }
  

• How does the prototypes of the following function change as a consequence of the alternative implementation:

  link reverse (link ls);
  void insertNext(link ls, link node);
  void deleteNext(link ls);
  

Note: I have changed the name of the functions too :)

void reverseList(list ls);
void insertNextList(list ls, link curr,link node);
void deleteNextList(list ls, link curr);

• Below is the code presented in the lecture for reversing a list, by passing in a pointer to the first element of the list. Adapt this code to work on the list type described above.

  link reverse (link ls) {
    link tmp;
    link curr = ls;
    link rev  = NULL; 
    while (curr != NULL) {
      tmp = curr->next; 
      curr->next = rev; 
      rev  = curr; 
      curr = tmp;
    } 
    return rev;
  }
  

  
  void reverseList(list ls){
      if(ls != NULL){
          link originalHead = ls->first;
          ls->first = reverse(ls->first);
          ls->last = originalHead;
      }
  }
  
  link reverse (link ls) {
      link tmp;
      link curr = ls;
      link rev  = NULL;
      while (curr != NULL) {
          tmp = curr->next;
          curr->next = rev;
          rev  = curr;
          curr = tmp;
      }
      return rev;
  }
  

  What are the advantages and disadvantages of your adapted version over the one discussed in the lecture? Which operations can be implemented more efficiently?
This version allows us to keep track of the size of the list, making the length function more efficient as we do not need to traverse the whole list. It would make inserting a node at the end of the list more efficient as again, we would not need to traverse the whole list to find the last node, as we have a pointer to it.

This implementation requires us to keep track of the size and tail when we add or delete nodes from the list so we need to be careful to consistently do that. The overhead of the extra memory to store the list struct is negligable.

Exercise 3 - Double linked lists

In the lecture, we briefly discussed doubly linked lists.

typedef char Item;

typedef struct dnode *dlink;

struct dnode {
    Item  item;
    dlink next;
    dlink prev;
};

Write a function

dlink append (dlink list1, dlink2 list2)

dlink append(dlink list1, dlink list2){
    dlink curr;
    dlink newList;
    if(list1 != NULL){
        for(curr = list1; curr->next != NULL; curr = curr->next){
        }
        curr->next = list2;
        if(list2 != NULL){
            list2->prev = curr;
        }
        newList = list1;
    } else {
        newList = list2;
    }
    return newList;      
}

which attaches the list list2 at the end of list1 and returns the resulting list.

Is it necessary to return the resulting list, or would the following interface work (as list1 is altered)

void append (dlink list1, dlink list2)