Doubly Linked List implementation

Question

At university we shortly started using C. I thought it would be a good exercise for almost everything that has to do with basic C to do a doubly linked list implementation. I tried to do it from scratch without looking at other implementations. Also I tried to apply some C code style, but I prefer the Java brace style over the C Kernel style.

I tested it and it seems to work fine. I'm especially interested in the correctness of the destroy function, since I am still a bit uncomfortable with what to free(). Also the insert and remove functions offend my eye.

list.h:

#ifndef LIST_H_
#define LIST_H_
typedef struct _Node Node;
typedef struct _Node{
 void * data;
 Node * next;
 Node * prev;
} Node;
typedef struct _List{
 size_t length;
 Node * head;
 Node * tail;
} List;
List* new_list();
void destroy_list(List *);
void list_append(List *, void *);
int list_length(List *);
void* list_get(List *, size_t);
void list_insert(List *, void *, size_t);
void list_remove(List *, size_t);
#endif /* LIST_H_ */

list.c

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
/*
 * Initialize a new empty list.
 */
List* new_list() {
 List * list;
 list = (List*) malloc(sizeof(List));
 list->head = NULL;
 list->tail = NULL;
 list->length = 0;
 return list;
}
/*
 * Free a list.
 */
void destroy_list(List * list) {
 Node * current = list->head;
 while (current->next) {
 free(current->prev);
 current = current->next;
 }
 free(list->tail);
 free(list);
}
/*
 * Return the element at the given index.
 */
void* list_get(List * list, size_t index) {
 Node * current;
 if (index < (list->length / 2)) {
 current = list->head;
 int i = 0;
 while (current->next && i != index) {
 current = current->next;
 i++;
 }
 } else {
 current = list->tail;
 int i = list->length - 1;
 while (current->prev && i != index) {
 current = current->prev;
 i--;
 }
 }
 return current->data;
}
/*
 * Append an element to the list.
 */
void list_append(List * list, void * elem) {
 Node * new;
 new = (Node*) malloc(sizeof(Node));
 new->data = elem;
 new->next = NULL;
 if (list->tail) {
 new->prev = list->tail;
 list->tail->next = new;
 list->tail = new;
 } else if (!list->tail && !list->head) {
 list->tail = new;
 list->head = new;
 new->prev = NULL;
 }
 list->length++;
}
/*
 * Prepend an element to the list.
 */
void list_prepend(List * list, void * elem) {
 Node * new;
 new = (Node*) malloc(sizeof(Node));
 new->data = elem;
 new->prev = NULL;
 if (list->head) {
 new->next = list->head;
 list->head->prev = new;
 list->head = new;
 } else if (!list->tail && !list->head) {
 list->tail = new;
 list->head = new;
 new->next = NULL;
 }
 list->length++;
}
/*
 * Insert an element into the list at the given index
 * (previous elements are shifted to the right by one).
 */
void list_insert(List * list, void * elem, size_t index) {
 Node * new;
 Node * current;
 new = (Node*) malloc(sizeof(Node));
 new->data = elem;
 if (index >= list->length) {
 return;
 } else if (index == 0) {
 new->next = list->head;
 new->prev = NULL;
 list->head->prev = new;
 list->head = new;
 } else if (index == list->length - 1) {
 list->tail->prev->next = new;
 new->prev = list->tail->prev;
 list->tail->prev = new;
 new->next = list->tail;
 } else if (index < (list->length / 2)) {
 current = list->head;
 int i = 0;
 while (current->next && i != index) {
 current = current->next;
 i++;
 }
 new->next = current;
 new->prev = current->prev;
 current->prev->next = new;
 current->prev = new;
 } else {
 current = list->tail;
 int i = list->length - 1;
 while (current->prev && i != index) {
 current = current->prev;
 i--;
 }
 new->next = current;
 new->prev = current->prev;
 current->prev->next = new;
 current->prev = new;
 }
 list->length++;
}
/*
 * Remove the element at the given index from the list.
 */
void list_remove(List * list, size_t index) {
 Node * current;
 if (index >= list->length) {
 return;
 } else if (index == 0) {
 current = list->head->next;
 current->prev = NULL;
 free(list->head);
 list->head = current;
 } else if (index == list->length - 1) {
 current = list->tail->prev;
 current->next = NULL;
 free(list->tail);
 list->tail = current;
 } else if (index < (list->length / 2)) {
 current = list->head;
 int i = 0;
 while (current->next && i != index) {
 current = current->next;
 i++;
 }
 current->prev->next = current->next;
 current->next->prev = current->prev;
 free(current);
 } else {
 current = list->tail;
 int i = list->length - 1;
 while (current->prev && i != index) {
 current = current->prev;
 i--;
 }
 current->prev->next = current->next;
 current->next->prev = current->prev;
 free(current);
 }
 list->length--;
}

Answer 1

• There seem to be a bug in list_remove. If a list size is 1, head and tail both point the same node. When it is removed, both head and tail shall become NULL, whereas your code only updates one of them.

• Linked list doesn't work well with sequential access. I recommend to have basic functions to work with node pointers, and (if you really want an index based access) a helper function to find a node by index. For example, a node removal function becomes

  void remove(List * list, Node * node)
  {
   if (node->prev) {
   node->prev->next = node->next;
   } else {
   assert(list->head == node);
   list->head = node->next;
   }
   if (node->next) {
   node->next->prev = node->prev;
   } else {
   assert(list->tail == node);
   list->tail = node->prev;
   }
   free(node);
   list->length--;
  }
  remove_by_index(List * list, int index)
  {
   Node * node = find_node(list, index);
   if (node) {
   remove(list, node);
   }
  }
  

  Same way you can greatly simplify insertion.

• You must take care about invariants: list->head == NULL, list->tail == NULL and list->size == 0 must be simultaneously valid, or simultaneously invalid. A side effect of invariant is that a condition

  } else if (!list->tail && !list->head) {
  

  in list_prepend is redundant. In fact, you should only care of list->head to update the list->tail when necessary:

  list_prepend(List * list, Node * node)
  {
   node->next = list->head;
   if (list->head) {
   list->head->prev = node;
   } else {
   assert(list->tail == NULL);
   assert(list->size == 0);
   list->tail = node;
   }
   list->head = node;
   list->size++;
  

• Benjoyo: Really, this is beautiful. One question: do you simply put assert()s everywhere where you think something could go wrong, to debug it? I have never used this before.
• vnp: @Benjoyo Asserts may be instrumental in debugging, but IMHO they first and foremost serve documentation purposes. See them as executable comments. In this case, they tell which invariants are (supposed to be) maintained.