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
.
- Write a function,
int index_of(list_t *l, int v)
, that returns the index of the left-most occurrence ofv
inl
or-1
ifv
is not inl
. - Write a function,
void insert(list_t *l, int i, int v)
, that insertsv
into indexi
, shifting the elements of the list to the right. For example, if the list contains the elements[0, 1, 3, 4, 5]
and we insert2
into index2
, the list becomes[0, 1, 2, 3, 4, 5]
. Ifi
is not a valid index inl
, then the function does nothing. - 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! - Write a function,
void to_string(list_t *l)
, that prints out the elements of the listl
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). - Write a function,
void dappend(list_t *l1, list_t *l2)
, that destructively appendsl2
ontol1
. The nodes ofl2
are appended onto the end ofl1
so thatl2
is empty after completion ofdappend
. - Write a function,
void append(list_t *l1, list_t *l2)
, that appendsl2
ontol1
. Copies of the nodes ofl2
are appended onto the end ofl1
.l2
is left un-modified by the function. - Write a function
void remove_all(list_t *l, int v)
that removes all occurrences ofv
froml
. - Write a function
void unique(list_t *l)
that removes all duplicate elements froml
. (Hint: can you leverage prior functions to make this implementation easier?) - Write a function
void reverse(list_t *l)
that reverses the listl
. (Hint: draw a diagram if you implement this using iteration. If you implementreverse
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: