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--;
}
