Created
June 1, 2012 19:11
-
-
Save gtklocker/2854467 to your computer and use it in GitHub Desktop.
Doubly linked list implementation in C
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
/* | |
* An implementation of doubly linked lists in C. | |
* | |
* API: | |
* * init() | |
* Initializes a doubly linked list and returns it. | |
* * push( list, value ) | |
* Appends a new element with value to the list. | |
* * destroy( list, value ) | |
* Destroys the first element with value found in the list. | |
* * print( list ) | |
* Prints a linear representation of the list. | |
* * remove( list, element ) | |
* Remove element from list and free it. | |
* * find( list, value ) | |
* Finds the first element in list with value. | |
* * remove_by_value( list, value ) | |
* Destroy first element of list with value. | |
* * pop( list ) | |
* Pop the last element of the list. | |
* * shift( list ) | |
* Pop the first element of the list and return it. | |
* * unshift( list, value ) | |
* Prepend value to the list. | |
*/ | |
#include <stdio.h> | |
#include <stdlib.h> | |
struct list_f { | |
struct list_f *l_next; | |
struct list_f *l_prev; | |
int l_value; | |
}; | |
/* Functions */ | |
struct list_f* init(); | |
void push( struct list_f *list, int value ); | |
void delete( struct list_f *list, struct list_f *rem ); | |
struct list_f* find( struct list_f *list, int value ); | |
void remove_by_value( struct list_f *list, int value ); | |
void pop( struct list_f *list ); | |
int shift( struct list_f *list ); | |
void unshift( struct list_f *list, int value ); | |
void print( struct list_f *list ); | |
struct list_f* init() { | |
struct list_f *ret; | |
ret = ( struct list_f* )malloc( sizeof( *ret ) ); | |
ret->l_next = ret; | |
ret->l_prev = ret; | |
ret->l_value = 0; | |
return ret; | |
} | |
void push( struct list_f *list, int value ) { | |
struct list_f *element; | |
struct list_f *tail = list->l_prev; | |
element = ( struct list_f* )malloc( sizeof( *element ) ); | |
element->l_next = list; | |
element->l_prev = tail; | |
element->l_value = value; | |
tail->l_next = element; | |
list->l_prev = element; | |
} | |
void delete( struct list_f *list, struct list_f *rem ) { | |
rem->l_prev->l_next = rem->l_next; | |
rem->l_next->l_prev = rem->l_prev; | |
} | |
struct list_f* find( struct list_f *list, int value ) { | |
struct list_f *r; | |
for ( r = list->l_next; r != list; r = r->l_next ) { | |
if ( r->l_value == value ) { | |
return r; | |
} | |
} | |
return NULL; | |
} | |
void remove_by_value( struct list_f *list, int value ) { | |
struct list_f* f = find( list, value ); | |
if ( f == NULL ) { | |
return; | |
} | |
delete( list, f ); | |
} | |
void pop( struct list_f *list ) { | |
delete( list, list->l_prev ); | |
} | |
int shift( struct list_f *list ) { | |
int ret = list->l_next->l_value; | |
delete( list, list->l_next ); | |
return ret; | |
} | |
void unshift( struct list_f *list, int value ) { | |
struct list_f *prep; | |
prep = ( struct list_f* )malloc( sizeof( *prep ) ); | |
prep->l_value = value; | |
prep->l_prev = list; | |
prep->l_next = list->l_next; | |
list->l_next = prep; | |
list->l_next->l_prev = prep; | |
} | |
void print( struct list_f *list ) { | |
struct list_f *l; | |
for ( l = list->l_next; l != list; l = l->l_next ) { | |
printf( "%d ", l->l_value ); | |
} | |
putchar( '\n' ); | |
} | |
int main() { | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi!
ret = ( struct list_f* )malloc( sizeof( *ret ) );