Last active
January 30, 2019 06:02
-
-
Save astei/6e4e6d4a9749a74aef93ecf778826d7f to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* A linked list implementation. | |
* | |
* Iteration is done by deferencing the head (or tail) of the list. | |
* Insertions at the front or back of the list will be O(1) (which | |
* is the only insertion operation supported), iteration is O(n), | |
* and removal is O(n) (unless the node being removed is the head or | |
* tail, which is O(1)). | |
* | |
* This implementation is a doubly-linked list. It is not thread safe. | |
*/ | |
#include <assert.h> | |
#include <stdbool.h> | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <string.h> | |
typedef struct node { | |
int val; | |
struct node *prev; | |
struct node *next; | |
} gr_linked_list_node; | |
typedef struct { | |
size_t size; | |
gr_linked_list_node *head; | |
gr_linked_list_node *tail; | |
} gr_linked_list; | |
gr_linked_list_node* _linked_list_create_node(int val) { | |
void *node_ptr = malloc(sizeof(gr_linked_list_node)); | |
if (node_ptr == NULL) { | |
return NULL; | |
} | |
gr_linked_list_node *node = (gr_linked_list_node *)node_ptr; | |
node->val = val; | |
return node; | |
} | |
int linked_list_insert_head(gr_linked_list *list, int val) { | |
gr_linked_list_node *node = _linked_list_create_node(val); | |
if (node == NULL) { | |
// TODO: Better return here | |
return EXIT_FAILURE; | |
} | |
if (list->head != NULL) { | |
// update the node | |
node->prev = NULL; | |
node->next = list->head; | |
list->head->prev = node; | |
list->head = node; | |
} else if (list->head == NULL && list->tail == NULL) { | |
// list is empty, as far as we know | |
list->head = list->tail = node; | |
node->prev = NULL; | |
node->next = NULL; | |
} | |
list->size++; | |
return EXIT_SUCCESS; | |
} | |
int linked_list_insert_tail(gr_linked_list *list, int val) { | |
gr_linked_list_node *node = _linked_list_create_node(val); | |
if (node == NULL) { | |
// TODO: Better return here | |
return EXIT_FAILURE; | |
} | |
if (list->tail != NULL) { | |
// update the node | |
node->prev = list->tail; | |
node->next = NULL; | |
list->tail->next = node; | |
list->tail = node; | |
} else if (list->head == NULL && list->tail == NULL) { | |
// list is empty, as far as we know | |
list->head = list->tail = node; | |
node->prev = NULL; | |
node->next = NULL; | |
} | |
list->size++; | |
return EXIT_SUCCESS; | |
} | |
void linked_list_reverse(gr_linked_list *list) { | |
// iterate backwards | |
gr_linked_list_node *old_tail = list->tail; | |
gr_linked_list_node *last_processed = NULL; | |
gr_linked_list_node *next_node = list->tail; | |
while (next_node != NULL) { | |
// swap prev and next | |
gr_linked_list_node *old_next = next_node->next; | |
next_node->next = next_node->prev; | |
next_node->prev = old_next; | |
last_processed = next_node; | |
next_node = next_node->next; | |
} | |
// now set the new head/tail | |
list->tail = last_processed; | |
list->head = old_tail; | |
} | |
void _linked_list_removal_fixup(gr_linked_list *list, gr_linked_list_node *node) { | |
// fix up the pointers in the list itself | |
if (node == list->head) { | |
list->head = node->next; | |
} | |
if (node == list->tail) { | |
list->tail = node->prev; | |
} | |
// now fix up other pointers | |
if (node->next != NULL) { | |
node->next->prev = node->prev; | |
} | |
if (node->prev != NULL) { | |
node->prev->next = node->next; | |
} | |
// free the node and decrement the list size | |
free(node); | |
list->size--; | |
} | |
bool linked_list_remove_first(gr_linked_list *list, int val) { | |
gr_linked_list_node *node = list->head; | |
while (node != NULL && node->val != val) { | |
node = node->next; | |
} | |
if (node == NULL) { | |
// no element found | |
return false; | |
} | |
_linked_list_removal_fixup(list, node); | |
return true; | |
} | |
bool linked_list_remove_last(gr_linked_list *list, int val) { | |
gr_linked_list_node *node = list->tail; | |
while (node != NULL && node->val != val) { | |
node = node->prev; | |
} | |
if (node == NULL) { | |
// no element found | |
return false; | |
} | |
_linked_list_removal_fixup(list, node); | |
return true; | |
} | |
gr_linked_list* new_linked_list() { | |
void *linked_list = malloc(sizeof(gr_linked_list)); | |
if (linked_list == NULL) { | |
// memory allocation failed | |
return NULL; | |
} | |
memset(linked_list, 0, sizeof(gr_linked_list)); | |
return (gr_linked_list*) linked_list; | |
} | |
void walk(gr_linked_list *list) { | |
gr_linked_list_node *current = list->head; | |
while (current != NULL) { | |
printf("%d\n", current->val); | |
current = current->next; | |
} | |
} | |
int main(int argc, char **argv) { | |
gr_linked_list* list = new_linked_list(); | |
assert(list != NULL); | |
assert(linked_list_insert_head(list, 42) == EXIT_SUCCESS); | |
assert(linked_list_insert_head(list, 666) == EXIT_SUCCESS); | |
assert(linked_list_insert_tail(list, 13) == EXIT_SUCCESS); | |
assert(linked_list_insert_tail(list, 17) == EXIT_SUCCESS); | |
printf("moving from head to tail\n"); | |
walk(list); | |
printf("reversing that shit\n"); | |
walk(list); | |
printf("doing crazy shit\n"); | |
assert(linked_list_remove_first(list, 42)); | |
assert(linked_list_remove_last(list, 17)); | |
assert(!linked_list_remove_last(list, 17)); | |
walk(list); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment