20161107:Pratical:C:Lists

Introduction

The purpose of this session is to learn lists implementation in C. We'll study classical linked lists implementation and vectors.

The expected format for your session is:

20161107_list/
  AUTHORS
  list/
    list.h
    list.c
  vector/
    vector.h
    vector.c

You can add files for your tests, but list.c and vector.c 'must not contains any main function.

Linked Lists

Our goal is to implement all classical operations (and some more) on linked lists. For that we use simply linked lists with sentinel and external allocation.

External allocation means that all allocations and free are done outside of the operations, the caller is responsible to provide already allocated list nodes for insertion. Delete operations give back the pointer to the node and let the caller free it if needed.

Sentinel means that our lists always have a fake node at the beginning, this little trick simplifies a lot of modification operations and enforce that the list entry point never changes.

The structure of the list is as follow (we implement list of integers):

struct list {
  struct list *next;
  int          data;
};

next contains the pointer to the next node and data the stored value in the current node.

Our goal is to provide implementation for the following list.h header:

/* Linked lists */
 
# ifndef EPITA_IP_LIST_H_
# define EPITA_IP_LIST_H_
 
/* Simply linked list of integers */
 
struct list {
  struct list *next;
  int          data;
};
 
/*
 * Standard operations
 * We're working with sentinels and external allocation
 * This means that our lists always have a fake head (the sentinel)
 * and all allocations (and free) are performed by the caller, not the operation
 */
 
/*
 * list_init(list)
 * initialise the sentinel node list
 */
void list_init(struct list *list);
 
/*
 * list_is_empty(list)
 * returns true if the list is empty
 * remember, we have a sentinel thus a list always has at least one node,
 * the list is empty if this node doesn't have a next.
 */
int list_is_empty(struct list *list);
 
/*
 * list_len(list)
 * returns the length of the list (don't count the sentinel)
 */
size_t list_len(struct list *list);
 
/*
 * list_push_front(list, elm)
 * attach elm in front of list, that is after the sentinel.
 * Note that elm is already a node, you just have to attach it.
 */
void list_push_front(struct list *list, struct list *elm);
 
/*
 * list_pop_front(list)
 * Extract the first element (not the sentinel) of list.
 * This operation detaches the element from the list and returns it (caller is
 * responsible for freeing it.)
 * If the list is empty, the function returns NULL.
 */
struct list* list_pop_front(struct list *list);
 
/*
 * list_find(list, value)
 * search for the first node containing value and returns (without detaching it)
 * the corresponding list node. The function returns NULL if the value is not
 * present in the list.
 */
struct list* list_find(struct list *list, int value);
 
/*
 * list_is_sorted(list)
 * check whether the list is sorted in increasing order
 */
int list_is_sorted(struct list *list);
 
/*
 * list_insert(list, elm)
 * insert elm in the sorted list (keeping the list sorted)
 * Like list_push_front, elm is already a list node.
 */
void list_insert(struct list *list, struct list *elm);
 
/*
 * More algorithms
 */
 
/*
 * list_rev(list)
 * reverse the list using the same nodes (just move them) and the same sentinel.
 */
void list_rev(struct list *list);
 
/*
 * list_half_split(list, second)
 * split the list in half and put the second half in second
 * second is an empty list (just a sentinel)
 */
void list_half_split(struct list *list, struct list *second);
 
# endif /* EPITA_IP_LIST_H_ */

• Implement all the operations listed in this list.h in the file list.c

Implementation notes

Here are some comments on implementations:

• list_init(list) takes the node used as sentinel and set the next pointer to NULL
• list_is_empty(list): a list is empty if the next pointer of the sentinel is NULL
• list_len(list): the number of nodes without the sentinel
• list_push_front(list, elm): elm is a list node containing the new value, you'll attach it after the sentinel
• list_pop_front(list) detaches the element after the sentinel and returns it
• list_half_split(list, second) can be implemented with only pass and without computing the length

Testing

In order to test, you'll write another C file testing operations one by one. The tests are your responsibility, but here are some useful trick.

In order to display the list, here is an example of a printing function for lists (beware, it contains a goto):

void print_list(struct list *list)
{
  int line = 1;
  printf("[");
  if (list->next) {
    goto pastfst;
    while (list->next) {
      line += printf(";");
      if (line > 72) {
	printf("\n ");
	line = 1;
      }
      pastfst:
      line += printf(" %d", list->next->data);
      list = list->next;
    }
  }
  printf(" ]\n");
}

While testing you must take care of allocation/free, if you're looking for a nice strategy, you can try to use an array of node …

A way to test your sorted insertion function is to implement an insertion sort, here is the function:

void list_insert_sort(struct list *list)
{
  if (list_is_empty(list)        // nothing to do
    return;
  struct list fake_head = {0,0}; // temporary head
  while (!list_is_empty(list)) {
    struct list *elm = list_pop_front(list);
    list_insert(&fake_head, elm);
  }
  list->next = fake_head.next;   // reattach the sorted list to its sentinel
}

Vectors

Vectors are wrappers around arrays in order to provide list like operations. The vector structure contains an array, its capacity and the current number of cells used in the array.

The structure look like this:

struct vector {
  size_t        capacity, size;
  int          *data;
};

capacity is the number of cell in data (the array of integers) and size is the number of used cells.

One interesting approach is to make vectors grow automatically: when adding an element to the vector, if the number of used cells is equal to the capacity, you can use realloc(3) in order to obtain a bigger array. A common strategy to avoid to much resizing is to double the capacity each time we need to resize. Here is an example of usage of realloc(3) in order to double the size of data:

// returns false if something goes wrong (realloc fails)
int double_vector_size(struct vector *vect)
{
  int *tmp = realloc(vect->data, 2 * vect->capacity * sizeof (int));
  if (tmp == NULL) {
    // oups no more memory ?
    warn("realloc of data fails");
    return 0;
  }
  vect->data = tmp;
  vect->capacity *= 2;
  return 1;
}

• Implement the functions from the following header (vector.h):

/* vector.h : Simple vector implementation */
 
# ifndef VECTOR_H_
# define VECTOR_H_
 
# include <stdlib.h>
 
struct vector {
  size_t        capacity, size;
  int          *data;
};
 
/*
 * vector_make(capacity) create an empty vector
 * with initial storage size capacity
 */
struct vector* vector_make(size_t capacity);
 
/*
 * vector_push_back(vect, x) add x at the end of vect
 * if vect is full increase capacity
 */
void vector_push_back(struct vector *vect, int x);
 
/*
 * vector_pop_back(vect, &x) get the last element of vect
 * remove the element
 * store result in x
 * return true (!=0) if size > 0
 * return false (0) otherwise
 */
int  vector_pop_back(struct vector *vect, int *x);
 
/*
 * vector_push_front(vect, x) add x at the beginning of vect
 * if vect is full increase capacity
 */
void vector_push_front(struct vector *vect, int x);
 
/*
 * vector_pop_back(vect, &x) get the first element of vect
 * remove the element
 * store result in x
 * return true (!=0) if size > 0
 * return false (0) otherwise
 */
int  vector_pop_front(struct vector *vect, int *x);
 
/*
 * vector_insert_at(vect, pos, x) add x in pos cell of vect
 * return true (!=0) if pos <= size of vect
 * return false (0) otherwise
 * vector_insert_at(v, v->size, x) is equivalent to vector_push_back(v, x)
 * vector_insert_at(v, 0, x) is equivalent to vector_push_front(v, x)
 * if vect is full increase capacity
 */
int vector_insert_at(struct vector *vect, size_t pos, int x);
 
/*
 * vector_extract_at(vect, pos, &x) get the pos element of vect
 * remove the element
 * store result in x
 * return false (0) if size == 0 or pos >= size
 * vector_extract_at(v, v->size - 1, &x) is equivalent to vector_pop_back(v, &x)
 * vector_extract_at(v, 0, &x) is equivalent to vector_pop_front(v, &x)
 */
int vector_extract_at(struct vector *vect, size_t pos, int *x);
 
/*
 * vector_clone(vect) create a complete copy of vect
 * both storage contains the same elements but are not at the same memory place
 */
struct vector* vector_clone(struct vector *vect);
 
 
# endif