Skip to content

Instantly share code, notes, and snippets.

@devendranaga
Created March 12, 2022 16:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save devendranaga/927921bff1411a4f57d446e25d762ece to your computer and use it in GitHub Desktop.
Save devendranaga/927921bff1411a4f57d446e25d762ece to your computer and use it in GitHub Desktop.
o(1) based double linked list implementation
#include <stdio.h>
#include <stdlib.h>
struct list {
void *data;
struct list *prev, *next;
};
static struct list *head, *last;
void list_init()
{
head = last = NULL;
}
int list_add(void *data)
{
struct list *elem = calloc(1, sizeof(struct list));
if (!elem) {
return-1;
}
elem->data = data;
if (!head) {
head = elem;
last = elem;
} else {
last->next = elem;
elem->prev = last;
last = elem;
}
return 0;
}
int list_for_each_front(void (*callback)(void *data))
{
struct list *elem;
if (!callback)
return -1;
for (elem = head; elem; elem = elem->next) {
callback(elem->data);
}
return 0;
}
int list_for_each_back(void (*callback)(void *data))
{
struct list *elem;
if (!callback)
return -1;
for (elem = last; elem != NULL; elem = elem->prev) {
callback(elem->data);
}
return 0;
}
void list_delete(void *data)
{
struct list *elem = head;
if (head->data == data) {
if (last == head) {
last = NULL;
}
head = head->next;
head->prev = NULL;
free(elem);
} else {
for (elem = head->next; elem; elem = elem->next) {
if (elem->data == data) {
if (elem == last) {
last = elem->prev;
elem->prev->next = NULL;
} else {
elem->prev->next = elem->next;
elem->next->prev = elem->prev;
}
free(elem);
break;
}
}
}
}
void print(void *data)
{
printf("%d ", *(int *)(data));
}
int main()
{
int elems[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int i;
for (i = 0; i < 10; i ++) {
list_add(&elems[i]);
}
list_for_each_front(print);
printf("\n");
list_for_each_back(print);
printf("\n");
list_delete(&elems[0]);
list_for_each_front(print);
printf("\n");
list_for_each_back(print);
printf("\n");
list_delete(&elems[4]);
list_for_each_front(print);
printf("\n");
list_for_each_back(print);
printf("\n");
list_delete(&elems[9]);
list_for_each_front(print);
printf("\n");
list_for_each_back(print);
printf("\n");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment