Tutorial Exercises Week 1

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
   • 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).
   • 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 (ls2);
     printList (reverse (ls));
     printList (ls);
     printList (ls2);
     return 0;
   }
   

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.
• Modify the length function you wrote in excercise 1 to work with our new implementation.
• 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);
  

• 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;
  }
  

  What are the advantages and disadvantages of your adapted version over the one discussed in the lecture? Which operations can be implemented more efficiently?

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)

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)