Linked List Practice

In this lab, we'll implement additional linked list operations to gain practice manipulating linked structures. Implement these functions in your linked list implementation of the list ADT, list.h and list.c, taken from the reading. Make sure to include an appropriate set of tests demonstrating the correctness of your implementation in main.c. Also make sure that your overall programs compiles and runs cleanly with ASan, i.e., compile with -g -fsantize=address.

  1. Write a function, int index_of(list_t *l, int v), that returns the index of the left-most occurrence of v in l or -1 if v is not in l.
  2. Write a function, void insert(list_t *l, int i, int v), that inserts v into index i, shifting the elements of the list to the right. For example, if the list contains the elements [0, 1, 3, 4, 5] and we insert 2 into index 2, the list becomes [0, 1, 2, 3, 4, 5]. If i is not a valid index in l, then the function does nothing.
  3. Write a function, void clear(list_t *l), that clears a list of its contents. Make sure that the nodes that are removed from the list are properly cleaned up!
  4. Write a function, void to_string(list_t *l), that prints out the elements of the list l in the following format: [0, 1, 2, 3, 4, 5]. (Hint: break up the function into three cases: empty list, a list with one element, and a list with more than one element).
  5. Write a function, void dappend(list_t *l1, list_t *l2), that destructively appends l2 onto l1. The nodes of l2 are appended onto the end of l1 so that l2 is empty after completion of dappend.
  6. Write a function, void append(list_t *l1, list_t *l2), that appends l2 onto l1. Copies of the nodes of l2 are appended onto the end of l1. l2 is left un-modified by the function.
  7. Write a function void remove_all(list_t *l, int v) that removes all occurrences of v from l.
  8. Write a function void unique(list_t *l) that removes all duplicate elements from l. (Hint: can you leverage prior functions to make this implementation easier?)
  9. Write a function void reverse(list_t *l) that reverses the list l. (Hint: draw a diagram if you implement this using iteration. If you implement reverse recursively, you will certainly need a helper function with additional arguments.)

For additional practice, try implementing list functions found in other standard libraries from other languages. Here are some examples for you to try out: