Skip to content

Instantly share code, notes, and snippets.

@erenon
Created November 19, 2010 20:46
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save erenon/707140 to your computer and use it in GitHub Desktop.
Save erenon/707140 to your computer and use it in GitHub Desktop.
Simple double linked list implementation in C
#include <stdio.h>
#include <stdlib.h>
#define SENTINEL_VALUE -1
typedef struct _list {
int value;
struct _list *prev;
struct _list *next;
} list;
list *list_create_item(int value) {
list *item;
item = (list *)malloc(sizeof(list));
//if null die
item->value = value;
item->prev = NULL;
item->next = NULL;
return item;
}
list *list_create() {
list *head, *tail;
head = list_create_item(SENTINEL_VALUE);
tail = list_create_item(SENTINEL_VALUE);
head->next = tail;
tail->prev = head;
return head;
}
int is_sentinel(list *item) {
return (item->value == SENTINEL_VALUE) ? 1 : 0;
}
int list_cmp(list *l1, list *l2) {
if (l1->value < l2->value) {
return -1;
} else if (l1->value == l2->value) {
return 0;
} else {
return 1;
}
}
void list_insert_after(list *before, list *item) {
list *after;
if (before->next == NULL) {
fprintf(stderr, "Inserting after tail sentinel");
return;
}
after = before->next;
before->next = item;
item->prev = before;
item->next = after;
after->prev = item;
}
void list_insert_before(list *after, list *item) {
if (after->prev == NULL) {
fprintf(stderr, "Inserting before head sentinel");
return;
}
list_insert_after(after->prev, item);
}
void list_insert_by_order(list *head, list *item) {
//skip head
head = head->next;
while (!is_sentinel(head) && list_cmp(head, item) < 0) {
head = head->next;
}
list_insert_before(head, item);
}
void list_append(list *head, list *item) {
while (!is_sentinel(head->next)) {
head = head->next;
}
list_insert_after(head, item);
}
void list_swap(list *a, list *b) {
list *tmp_swap, tmp;
//b is left neighbour of a
if (b->next == a) {
tmp_swap = b;
b = a;
a = tmp_swap;
}
//...ab...
if (a->next == b) {
b->next->prev = a;
a->prev->next = b;
b->prev = a->prev;
a->next = b->next;
a->prev = b;
b->next = a;
} else
//..a...b..
{
tmp = *b;
b->prev = a->prev;
b->next = a->next;
a->prev->next = b;
a->next->prev = b;
a->next = tmp.next;
a->prev = tmp.prev;
tmp.prev->next = a;
tmp.next->prev = a;
}
}
void list_prepend(list *head, list *item) {
list_insert_after(head, item);
}
void list_print(list *head) {
//skip head
head = head->next;
while (!is_sentinel(head)) {
printf("%d ", head->value);
head = head->next;
}
printf("\n");
}
void list_delete(list *head) {
list *next;
while (head->next != NULL) {
next = head->next;
free(head);
head = next;
}
free(head);
}
int main() {
list *simple, *ordered;
list *a, *b, *c, *d;
printf("simple list:\n");
//create simple unordered list
simple = list_create();
a = list_create_item(1);
b = list_create_item(5);
c = list_create_item(7);
d = list_create_item(4);
//append
list_append(simple, a);
list_append(simple, b);
list_append(simple, c);
printf("157:\t");
list_print(simple);
list_prepend(simple, d);
printf("4157:\t");
list_print(simple);
list_swap(b, a);
printf("4517:\t");
list_print(simple);
list_swap(c, d);
printf("7514:\t");
list_print(simple);
//fail
list_insert_before(simple, list_create_item(4));
list_delete(simple);
printf("\nordered list:\n");
//ordered list
ordered = list_create();
list_insert_by_order(ordered, list_create_item(0));
list_insert_by_order(ordered, list_create_item(5));
list_insert_by_order(ordered, list_create_item(2));
list_insert_by_order(ordered, list_create_item(8));
list_insert_by_order(ordered, list_create_item(2));
printf("02258:\t");
list_print(ordered);
list_delete(ordered);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment