Last active
March 12, 2018 12:52
-
-
Save ericek111/a0e6c916105054187435ac6fac420040 to your computer and use it in GitHub Desktop.
[C] Double linked list
This file contains 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
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
/* Linked list entry */ | |
typedef struct llEntry { | |
struct llEntry* prev; | |
struct llEntry* next; | |
void* data; | |
} llEntry; | |
/* Double linked list */ | |
typedef struct llList { | |
llEntry* first; | |
llEntry* last; | |
int count; | |
} llList; | |
llList* newList(void); | |
void deleteList(llList* list); | |
llEntry* pushEntry(llList* list, void* data); | |
llEntry* getEntry(llList* list, int idx); | |
llEntry* popEntryIndex(llList* list, int idx); | |
llEntry* iterateUpwards(llList* list, int from, int to, void (*callback)(llList*, llEntry*, int)); | |
///////////////////////////////////////////// IMPLEMENTATION ////////////////// | |
// Allocate a new list with 0 elements. | |
llList* newList(void) { | |
llList* newl = malloc(sizeof(llList)); | |
memset(newl, 0, sizeof(llList)); | |
return newl; | |
} | |
// Free every element and the list itself. | |
void deleteList(llList* list) { | |
llEntry* curr = list->first; | |
while(curr) { | |
free(curr); | |
curr = curr->next; | |
} | |
free(list); | |
} | |
// Push llEntry to the very end of the list. | |
llEntry* pushEntry(llList* list, void* data) { | |
llEntry* newe = malloc(sizeof(llEntry)); | |
if(newe == NULL) | |
return NULL; | |
memset(newe, 0, sizeof(llEntry)); | |
newe->data = data; | |
if(list->first == NULL) { | |
list->first = newe; | |
list->last = newe; | |
list->count = 1; | |
//printf("newe: %p - first: %p, last: %p - newe->prev: %p, newe->next: %p\n", newe, list->first, list->last, newe->prev, newe->next); | |
return newe; | |
} | |
newe->prev = list->last; | |
list->last->next = newe; | |
list->last = newe; | |
list->count++; | |
//printf("newe: %p - first: %p, last: %p - newe->prev: %p, newe->next: %p\n", newe, list->first, list->last, newe->prev, newe->next); | |
return newe; | |
} | |
// Returns one entry from the linked list according to its index in list | |
llEntry* getEntry(llList* list, int idx) { | |
if(idx == 0) | |
return list->first; | |
if(idx + 1 == list->count) | |
return list->last; | |
if(idx >= list->count) | |
return NULL; | |
llEntry* curr = list->first; | |
while(idx-- && curr) { | |
//printf("%d: curr: %p, next: %p\n", idx, curr, curr->next); | |
curr = curr->next; | |
} | |
return curr; | |
} | |
// Remove element from linked list and return the following one | |
llEntry* popEntryIndex(llList* list, int idx) { | |
if(idx == 0) { | |
if(list->count == 1) { | |
free(list->first); | |
memset(list, 0, sizeof(llList)); | |
return NULL; | |
} | |
list->first->next->prev = NULL; | |
list->count--; | |
list->first = list->first->next; | |
return list->first; | |
} | |
if(idx + 1 == list->count) { | |
list->last->prev->next = NULL; | |
llEntry* temp = list->last; | |
list->last = list->last->prev; | |
list->count--; | |
free(temp); | |
return NULL; | |
} | |
llEntry* curr = list->first; | |
while(idx-- && curr) { | |
curr = curr->next; | |
} | |
curr->prev->next = curr->next; | |
curr->next->prev = curr->prev; | |
list->count--; | |
llEntry* toReturn = curr->next; | |
free(curr); | |
return toReturn; | |
} | |
// Iterate the linked list upwards and return the final entry. | |
llEntry* iterateUpwards(llList* list, int from, int to, void (*callback)(llList*, llEntry*, int)) { | |
if(list->count <= from) | |
return NULL; | |
if(from > to) | |
return NULL; | |
llEntry* curr = getEntry(list, from); | |
if(curr == NULL) | |
return NULL; | |
for (int i = from; i <= to; ++i) { | |
curr = curr->next; | |
(*callback)(list, curr, i); | |
} | |
return curr; | |
} | |
void myCallback(llList* list, llEntry* entry, int idx) { | |
printf("Called for %d\n", idx); | |
} | |
int main(int argc, char const *argv[]) { | |
llList* ll = newList(); | |
int x = 5, y = 7, z = 9, za = 10; | |
pushEntry(ll, &x); | |
pushEntry(ll, &y); | |
pushEntry(ll, &z); | |
pushEntry(ll, &za); | |
for (int i = 0; i < ll->count; ++i) { | |
llEntry* e = getEntry(ll, i); | |
printf("#%d: %d\n", i, *((int*)e->data)); | |
} | |
popEntryIndex(ll, 2); | |
printf("\n"); | |
for (int i = 0; i < ll->count; ++i) { | |
llEntry* e = getEntry(ll, i); | |
printf("#%d: %d\n", i, *((int*)e->data)); | |
} | |
printf("\nITERATE UPWARDS: %d\n", ll->count); | |
iterateUpwards(ll, 0, ll->count - 1, myCallback); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment