COMP 1917 Computing 1
Session 2, 2016

Tutorial - Week 10

Presentation Topic for Week 10

There are tools available that can help you debug your programs. Two of such tools are valgrind and gdb. Show how you would use these tools to check for memory leaks and debug segmentation faults. (For gdb show at least commands like where, info locals, print and how to set a breakpoint).

An alternative implementation of linked lists requires a separate struct to keep tack of the head and additional features. 
    typedef struct node* Lnode;

    struct node{
      int val;
      Lnode next;  
    };

    typedef struct list* List;

    struct list{
        Lnode head;
        int numNodes;
    };
  1. Write a function List newList(void) to dynamically allocate new list.

  2. Write a function void append(List l, Lnode new) that appends new node to an existing list.

  3. Write a function void printList(List l) that prints existing list.

  4. Write a function void deleteNode(List l, int val) that removes the first occurence of val in a list.

  5. Create a separate file called testList.c and test the above functions.

    How would implementation of the above functions and tests change if you use this representation.

  6. Write a function 
    void shuffle_merge(List l, List m)
    which merges two linked lists l and m, taking nodes alternatively between the two lists. 

  7. void reverse(List l)
    which reverses the nodes of a linked list, so that the ordering of the nodes becomes exactly the opposite of what it was before. The function should return a pointer to the head of the new list.

  8. Write a function 
    void swap(List l)
    which swaps every two nodes of the list l (e.g. 1->2->3->4->5 should become 2->1->4->3->5. Last element is not swapped as it doesn't have a pair.)

Presentation Topic for Week 11

Describe positives and negatives of arrays and linked lists. When would you use a linked list over an array?