Skip to content

Instantly share code, notes, and snippets.

@gtklocker
Created June 1, 2012 19:11
Show Gist options
  • Save gtklocker/2854467 to your computer and use it in GitHub Desktop.
Save gtklocker/2854467 to your computer and use it in GitHub Desktop.
Doubly linked list implementation in C
/*
* 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;
}
@thatskriptkid
Copy link

Hi!

  1. You allocate pointer size space but you need space for struct.
    ret = ( struct list_f* )malloc( sizeof( *ret ) );
  2. You dont free memory after delete element from list

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment