Skip to content

Instantly share code, notes, and snippets.

@devendranaga
Created March 12, 2022 16:11
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/7d7cc8984f931226d5b1a46cfc08a1af to your computer and use it in GitHub Desktop.
Save devendranaga/7d7cc8984f931226d5b1a46cfc08a1af to your computer and use it in GitHub Desktop.
o(1) based linked list implementation
#include <stdio.h>
#include <stdlib.h>
struct list {
void *data;
struct list *next;
};
static struct list *head, *last;
void list_init()
{
head = last = NULL;
}
int list_add(void *data)
{
struct list *new = calloc(1, sizeof(struct list));
if (!new) {
return -1;
}
new->data = data;
if (!head) {
head = new;
last = new;
} else {
last->next = new;
last = new;
}
return 0;
}
int list_add_head(void *data)
{
struct list *new = calloc(1, sizeof(struct list));
if (!new) {
return -1;
}
new->data = data;
new->next = head;
head = new;
return 0;
}
int list_delete_node(void *data, void (*callback)(void *data))
{
struct list *elem = head;
int found = -1;
if (head->data == data) {
if (callback)
callback(head->data);
if (last == head) {
last = NULL;
}
head = head->next;
free(elem);
found = 0;
} else {
struct list *prev;
prev = head;
elem = head->next;
for (elem = head->next, prev = head; elem; prev = elem, elem = elem->next) {
if (elem->data == data) {
if (elem == last) {
last = prev;
prev->next = NULL;
} else {
prev->next = elem->next;
}
free(elem);
break;
found = 0;
}
}
}
return found;
}
int list_for_each(void (*callback)(void *data))
{
struct list *elem;
if (!callback) {
return -1;
}
for (elem = head; elem; elem = elem->next) {
callback(elem->data);
}
return 0;
}
void print(void *val)
{
printf("%d ", *(int *)val);
}
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(print);
printf("\n");
list_delete_node(&elems[1], NULL);
list_for_each(print);
printf("\n");
list_delete_node(&elems[0], NULL);
list_for_each(print);
printf("\n");
list_delete_node(&elems[9], NULL);
list_for_each(print);
printf("\n");
int test[10];
for (i = 0; i < 10; i ++) {
test[i] = elems[i];
list_add(&test[i]);
}
list_for_each(print);
printf("\n");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment