A Queue implementation of doubly linked list in C

[arnuld]

This is my 3rd data structure. I am learning to implement most of the
data structures in C. Niklaus Wirth one said:

Algorithms + Data Structures = Programs

and it took me 3 years to know the truth behind his comment. I wrote a C
program (for my employer) which produced around 30 bugs just because I did
not know how to implement a Queue in C. As usual, I am posting it here to
get suggestions, advice on improving the program etc.(You know I Love that


/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.0
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use 0 for true and everything else for false */
enum { VAL_TRUE = 0, VAL_FALSE = 1 };
enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
void make_null( struct my_queue* );
int is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );




int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );
printf("Front = ");
queue_print_element( front(m) );
printf("is_empty = %d\n", is_empty(m) );

return 0;
}




struct my_queue* enqueue( struct my_queue* s, const char* c )
{
struct my_list* p = malloc( 1 * sizeof *p );

/* Check 1: the new element just malloc()ed */
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__ );
return s;
}

if( strlen(c) < SIZE_ARR )
{
strcpy( p->arrc, c );
p->prev = p->next = NULL;
}
else
{
printf("Size of array of the element is larger than required\n");
free(p);
return s;
}

/* Check 2: the original queue */
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
/* printf("Adding First element to Queue\n"); */
s->head = s->tail = p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
return s;
}
else
{
/* printf("Adding element to the tail\n"); */
s->tail->next = p;
s->tail = p;
}

return s;
}


struct my_queue* dequeue( struct my_queue* s )
{
struct my_list* r = NULL;

if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
printf("There are no elements in the queue\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
}
else
{
/* printf("Removing element\n"); */
r = s->head;
s->head = s->head->next;
free(r);
}


return s;
}



void make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );
}
else
{
while( s->head ) dequeue(s);
}
}


struct my_list* front( struct my_queue* s )
{
return s->head;
}


int is_empty( struct my_queue* s )
{
if( NULL == s->head && NULL == s->tail )
{
return VAL_TRUE;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, there is somethign wrong with the assignment of the queue's head/tail\n", __LINE__);
}

return VAL_FALSE;
}



struct my_queue* queue_new( void )
{
struct my_queue* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf( stderr, "LINE: %d, malloc() failed, can not initialize queue\n", __LINE__ );
exit( EXIT_FAILURE );
}

p->head = p->tail = NULL;

return p;
}


void queue_print( struct my_queue* s )
{
struct my_list* p = NULL;

if( NULL == s )
{
printf("Can not print a NULL queue\n");
}
else
{
for( p = s->head; p; p = p->next )
{
queue_print_element(p);
}
}

printf("--------------------------------------\n");

}


void queue_print_element( struct my_list* p )
{
printf("arrc = [%s]\n", p->arrc);
}

====================== OUTPUT =======================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra double-LL_queue.c
[arnuld@dune programs]$ ./a.out
--------------------------------------
arrc = [comp]
arrc = [.]
arrc = [lang]
arrc = [.]
arrc = [c]

 

[Nate Eldredge]

This is my 3rd data structure. I am learning to implement most of the
data structures in C. Niklaus Wirth one said:

Algorithms + Data Structures = Programs

and it took me 3 years to know the truth behind his comment. I wrote a C
program (for my employer) which produced around 30 bugs just because I did
not know how to implement a Queue in C. As usual, I am posting it here to
get suggestions, advice on improving the program etc.(You know I Love that


/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.0
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use 0 for true and everything else for false */
enum { VAL_TRUE = 0, VAL_FALSE = 1 };

I don't care for this.

I think the idiom is a little more nuanced than that. Functions which
are predicates, i.e. whose return values give the answer of a yes/no
question, should return 1 for true and 0 for false. Functions which
attempt to perform some action but might fail should return 0 for
success (or perhaps some positive result value) and nonzero (perhaps -1)
for failure.

The fact that you gave your function the name `is_empty' is a suggestion
that you are in the first of these cases. It asks whether a particular
statement about the queue is true or false. It doesn't perform any
particular action, and there's not a clear sense of which case is
"success" and which is "failure". Moreover, a name starting with `is_'
just begs to be used like

if (is_empty(q)) { /* deal with q being empty }

which won't work under your convention. I suspect this would be the
source of many bugs.

So I would have is_empty return 1 if the queue is empty, and 0 if it is
not.

enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};

I would be inclined to have the my_list node contain a pointer to the
string which it should store, rather than an array. enqueue could use
malloc to store a copy of the string it gets passed, and store a pointer
to the malloc'ed space in the node. This has the benefit of avoiding
the arbitrary limit on the string size.

Other than that, I think it looks pretty good. Nice work!

 

[Ike Naar]

[...]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use 0
for true and everything else for false */
enum { VAL_TRUE = 0, VAL_FALSE = 1 };

Not really: in C, the expression (2+2==4) is true, and yields 1;
(2+2==5) is false and yields 0.
It would be slightly less confusing if you used different names,
e.g. VAL_SUCCESS and VAL_FAILURE.

enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};

You never do anything useful with the prev pointer.

struct my_queue
{
struct my_list* head;
struct my_list* tail;
};

struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
void make_null( struct my_queue* );
int is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );

int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );
printf("Front = ");
queue_print_element( front(m) );
printf("is_empty = %d\n", is_empty(m) );

return 0;
}

struct my_queue* enqueue( struct my_queue* s, const char* c )
{
struct my_list* p = malloc( 1 * sizeof *p );

The ``1 *'' part is not necessary.

If you would place the malloc call after the sanity checks below,
you wouldn't need to free(p) when one of the checks fails.
(you're also forgetting to free(p) in a couple of cases).

/* Check 1: the new element just malloc()ed */
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__ );
return s;
}

if( strlen(c) < SIZE_ARR )
{
strcpy( p->arrc, c );
p->prev = p->next = NULL;
}
else
{
printf("Size of array of the element is larger than required\n");
free(p);
return s;
}

/* Check 2: the original queue */
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );

Memory leak: forgot to free(p).

}
else if( NULL == s->head && NULL == s->tail )
{
/* printf("Adding First element to Queue\n"); */
s->head = s->tail = p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is
not, WHY ???\n", __LINE__ );

Memory leak: forgot to free(p).

return s;
}
else
{
/* printf("Adding element to the tail\n"); */
s->tail->next = p;
s->tail = p;
}

return s;
}

In the previous function, you always return s.
That is not wrong in itself, but it is redundant.
s is already available to the caller, even if the function would
not return it.
So why not make it a void function, and return nothing?

struct my_queue* dequeue( struct my_queue* s )
{
struct my_list* r = NULL;

if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
printf("There are no elements in the queue\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is
not, WHY ???\n", __LINE__ );
}
else
{
/* printf("Removing element\n"); */
r = s->head;
s->head = s->head->next;
free(r);

Small nit: in general it is a good idea to make the scope of variables
as small as necessary. In this case, you could remove the declaration
(and redundant initialization) of r from the outer block of the function,
and move it to the subblock:

{
struct my_list *r = s->head;
s->head = s->head->next;
free(r);

}

return s;
}

Same thing as before: what's the point in returning s?

void make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );
}
else
{
while( s->head ) dequeue(s);
}
}

A better name would be make_empty, since that is what the function does.
There is a difference between a null queue (it has not been initialized)
and an empty queue (it has been initialized properly, it just contains
no elements).

struct my_list* front( struct my_queue* s )
{

No check here if s is NULL.

return s->head;
}

int is_empty( struct my_queue* s )
{

No check here if s is NULL.

if( NULL == s->head && NULL == s->tail )
{
return VAL_TRUE;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, there is somethign wrong with the
assignment of the queue's head/tail\n", __LINE__);

There is somethign wrong with the error message ;-)

}

return VAL_FALSE;
}

As mentioned before, your usage of true and false is counterintuitive: this

if (is_empty(my_queue)) do_stuff();

will do_stuff() if my_queue is not empty.

struct my_queue* queue_new( void )
{
struct my_queue* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf( stderr, "LINE: %d, malloc() failed, can not initialize
queue\n", __LINE__ );
exit( EXIT_FAILURE );
}

p->head = p->tail = NULL;

return p;
}


void queue_print( struct my_queue* s )
{
struct my_list* p = NULL;

if( NULL == s )
{
printf("Can not print a NULL queue\n");
}
else
{
for( p = s->head; p; p = p->next )
{
queue_print_element(p);
}
}

printf("--------------------------------------\n");

}


void queue_print_element( struct my_list* p )
{
printf("arrc = [%s]\n", p->arrc);
}

 

[Phil Carmody]

This is my 3rd data structure. I am learning to implement most of the
data structures in C. Niklaus Wirth one said:

Algorithms + Data Structures = Programs

and it took me 3 years to know the truth behind his comment. I wrote a C
program (for my employer) which produced around 30 bugs just because I did
not know how to implement a Queue in C. As usual, I am posting it here to
get suggestions, advice on improving the program etc.(You know I Love that

I've never understood comments like this. I could implement a queue in C
within half a day of first seeing K&R.

struct my_queue* enqueue( struct my_queue* s, const char* c )
{
struct my_list* p = malloc( 1 * sizeof *p );

/* Check 1: the new element just malloc()ed */
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__ );
return s;
}

if( strlen(c) < SIZE_ARR )
{
strcpy( p->arrc, c );
p->prev = p->next = NULL;
}
else
{
printf("Size of array of the element is larger than required\n");
free(p);
return s;
}

Why did you allocate p, and then only check to see if the copy of the
string pointed to by c will fit after that?

/* Check 2: the original queue */
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );

WHy didn't you check that first?
You're leaking memory here.

}
else if( NULL == s->head && NULL == s->tail )
{
/* printf("Adding First element to Queue\n"); */
s->head = s->tail = p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
return s;

Why didn't you check that at the top too?
Again, you're leaking memory.

}
else
{
/* printf("Adding element to the tail\n"); */
s->tail->next = p;
s->tail = p;

You haven't told p that it's in the list. Have you forgotten about
those p->prev and p->next elements that actually make the list a
(doubly-linked) list.

}

return s;
}

Rest skipped, if adding to a list is this messed up, I fear for
what the other functions may contain.

Phil

 

[Guest]

This is my 3rd data structure. I am learning to implement most of the
data structures in C. Niklaus Wirth one said:

   Algorithms + Data Structures = Programs

and it took me 3 years to know the truth behind his comment. I wrote a C
program (for my employer) which produced around 30 bugs just because I did
not know how to implement a Queue in C.

30 bugs in such a simple program seems rather high. Did you test it
before
you "shipped" it?

something like

void basic_test (void)
{
Queue q = q_init();
char *q_val;
assert (q_add (q, "red") == NO_ERROR);
assert (q_add (q, "blue") == NO_ERROR);
assert (q_add (q, "green") == NO_ERROR);
assert (q_remove (q, &q_val) == NO_ERROR);
assert (strcmp(q_val, "red") == 0)
assert (q_remove (q, &q_val) == NO_ERROR);
assert (strcmp(q_val, "blue") == 0)
assert (q_remove (q, &q_val) == NO_ERROR);
assert (strcmp(q_val, "green") == 0)
assert (q_is_empty(q));
}


<snip>

 

[Ben Bacarisse]

/* A Queue implementation in C using doubly linked list.

Why? The extra linkage gives you no benefit at all. The fact that
you don't maintain both links and the queue still works should be a
bit hint that you have redundant data.

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use 0 for true and everything else for false */
enum { VAL_TRUE = 0, VAL_FALSE = 1 };

I'll add my voice to the crowd saying that is a bad idea. Code like
this:

if (is_empty(q)) ...

while (!is_empty(q)) {
...
dequeue(q);
}

is natural to write and easy to understand. You have to write

while (is_empty(q)) {...}

or

while (is_empty(q) == VAL_FALSE) {...}

The first is crazy and the second is overlong and prone to being
"corrected" incorrectly.

<snip>

 

[arnuld]

Why? The extra linkage gives you no benefit at all.

I just wanted to learn about how to write a doubly linked list in C.

The fact that
you don't maintain both links and the queue still works should be a
bit hint that you have redundant data.

Yes, there is new modified code in my other post which does that.

I'll add my voice to the crowd saying that is a bad idea. Code like
this:

if (is_empty(q)) ...

while (!is_empty(q)) {
...
dequeue(q);
}

is natural to write and easy to understand. You have to write

while (is_empty(q)) {...}

or

while (is_empty(q) == VAL_FALSE) {...}

The first is crazy and the second is overlong and prone to being
"corrected" incorrectly.

I don't get it, how these last 2 are different from first 2 ? .

 

[arnuld]

I've never understood comments like this. I could implement a queue in C
within half a day of first seeing K&R.

May be you have a gifted skill then, I don't. I am just an average man.

You haven't told p that it's in the list. Have you forgotten about
those p->prev and p->next elements that actually make the list a
(doubly-linked) list.

.. SNIP...

Rest skipped, if adding to a list is this messed up, I fear for
what the other functions may contain.

Here is the new fixed code, see if there are any more errors:

/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.1
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use 0 for true and everything else for false */
enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
struct my_list* make_null( struct my_queue* );
struct my_list* is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );


int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );
printf(" Front = ");
queue_print_element( front(m) );

is_empty( m );

make_null( m );
free( m );
m = NULL;

return 0;
}


struct my_queue* enqueue( struct my_queue* s, const char* c )
{
struct my_list* p = malloc( 1 * sizeof *p );

/* Check 1: the new element just malloc()ed */
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__ );
return s;
}

if( strlen(c) < SIZE_ARR )
{
strcpy( p->arrc, c );
p->prev = p->next = NULL;
}
else
{
printf("Size of array of the element is larger than required\n");
free(p);
return s;
}

/* Check 2: the original queue */
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
free(p);
}
else if( NULL == s->head && NULL == s->tail )
{
/* printf("Adding First element to Queue\n"); */
s->head = s->tail = p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
free(p);
return s;
}
else
{
/* printf("Adding element to the tail\n"); */
s->tail->next = p;
p->prev = s->tail;
s->tail = p;
}

return s;
}


struct my_queue* dequeue( struct my_queue* s )
{
struct my_list* r = NULL;

if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
printf("There are no elements in the queue\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
}
else
{
/* printf("Removing element\n"); */
r = s->head;
s->head = s->head->next; /* head removed from the queue */
free(r);

if( NULL == s->head ) /* in case we removed the last remaining element */
{
s->tail = s->head;
}
else
{
s->head->prev = NULL; /* set the prev of the to the NULL */
}
}


return s;
}



struct my_list* make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );
}
else
{
while( s->head ) dequeue(s);
}

return s->head; /* head will be NULL if make_null was success */
}


struct my_list* front( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue not initialized ?\n", __LINE__);
}

return s->head;
}


struct my_list* is_empty( struct my_queue* s )
{
struct my_list* retp; /* will have some garbage value */

if( NULL == s )
{
printf("There is no Queue ?? \n");
retp = NULL;
}
else if( NULL == s->head && NULL == s->tail )
{
printf("Queue is empty\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, there is something wrong with the assignment of the queue's head/tail\n", __LINE__);
retp = NULL;
}
else
{
printf("Queue NOT empty\n");
}

return retp;
}



struct my_queue* queue_new( void )
{
struct my_queue* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf( stderr, "LINE: %d, malloc() failed, can not initialize queue\n", __LINE__ );
exit( EXIT_FAILURE );
}

p->head = p->tail = NULL;

return p;
}


void queue_print( struct my_queue* s )
{
struct my_list* p = NULL;

if( NULL == s )
{
printf("Can not print a NULL queue\n");
}
else
{
for( p = s->head; p; p = p->next )
{
queue_print_element(p);
printf("NEXT = ");
queue_print_element(p->next);
printf("PREV = ");
queue_print_element(p->prev);
printf("\n\n");
}
}

printf("--------------------------------------\n");

}


void queue_print_element( struct my_list* p )
{
printf("arrc = [%s]\n", p->arrc);
}


======================= OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra double-LL_queue.c
[arnuld@dune programs]$ ./a.out
--------------------------------------
arrc = [comp]
NEXT = arrc = [.]
PREV = arrc = [(null)]


arrc = [.]
NEXT = arrc = [lang]
PREV = arrc = [comp]


arrc = [lang]
NEXT = arrc = [.]
PREV = arrc = [.]


arrc = [.]
NEXT = arrc = [c]
PREV = arrc = [lang]


arrc = [c]
NEXT = arrc = [(null)]
PREV = arrc = [.]

 

[arnuld]

You never do anything useful with the prev pointer.

I just wanted to learn how to write/use a doubly-linked list.

In the previous function, you always return s.
That is not wrong in itself, but it is redundant.
s is already available to the caller, even if the function would
not return it.
So why not make it a void function, and return nothing?

Because I have made a habit that my functions will always return
something, except of those who only print information.

Small nit: in general it is a good idea to make the scope of variables
as small as necessary. In this case, you could remove the declaration
(and redundant initialization) of r from the outer block of the function,
and move it to the subblock:

{
struct my_list *r = s->head;
s->head = s->head->next;
free(r);

You can't do that in C89. I use C99 mostly but most people here don't have
C99 conforming compiler (I guess including Richard Heathfield), so it
limits the scope of getting useful answers.

 

[Chris Dollin]

You can't do that in C89.

Yes, you can. Why do you think you can't?

(The restriction you may be thinking of is that you can't in C90 have
a declaration /directly following a statement/, ie

printf( "here we go gathering nuts in May.\n" );
int nuts = 0;

is illegal.)

 

[James Kuyper]

I just wanted to learn how to write/use a doubly-linked list.

You're not learning that, if you have a doubley-linked list, and don't
actually make use of the double linkage.

....

Because I have made a habit that my functions will always return
something, except of those who only print information.

That's not a useful habit to form. Only return something it it's
actually of use to the caller.

....

You can't do that in C89.

Yes you can. Mixing statements and declarations within a block is a C99
feature, but even in C90 each block was allowed to have it's own set of
declarations.

 

[Guest]

I just wanted to learn about how to write a doubly linked list in C.


Yes, there is new modified code in my other post which does that.









I don't get it, how these last 2 are different from first 2 ? .

you can't see why

while (!is_empty(q))
dequeue();

makes more sense than

while (is_empty(q))
dequeue();

your version goes against the normal C conventions and *will* confuse
other programmers. The first just reads better

"while the queue isn't empty remove things from it"

and
while (is_empty(q) == VAL_FALSE)

is unnecessarily long winded

 

[Keith Thompson]

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always
use 0 for true and everything else for false */

[...]

*Please* don't do this.

Truth vs. falsehood and success vs. failure are two distinct sets of
concepts. There is a convention, in *some* contexts, to use zero for
success and non-zero values for failure; the reason for this is
typically that a non-zero failure code can represent different kinds
of failure. (That's probably more a Unix convention than a C
convention.) But apart from that, C *always* uses zero for false and
some non-zero value (particularly 1) for true.

In your original program, your is_empty() function returned 1 for
false and 0 for true; several people explained why this is a Really
Bad Idea. In the latest version, is_empty() returns a pointer, and
the one time you call it you ignore the result anyway. I haven't
studied your code enough to determine how to fix it.

 

[Keith Thompson]

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use
0 for true and everything else for false */
enum { VAL_TRUE = 0, VAL_FALSE = 1 };

[...]
while (is_empty(q) == VAL_FALSE) {...}

[...]

But then because false is ANY non-zero value, comparing with VAL_FALSE is
a bad idea, just as comparing with 1 for true in non-opposite-world C is.
So you'd want

while (is_empty(q) != VAL_TRUE) {...}

I have a hard time believing the original post was meant as serious...

I think the idea is that true is represented only by VAL_TRUE, and
false is represented only by VAL_FALSE. If you can manage to maintain
this with 100% consistency, then
is_empty(q) == VAL_FALSE
is just as safe as
is_empty(q) != VAL_TRUE

Of course this breaks down as soon as you try to apply any of C's
built-in conditional operations to a VAL_TRUE/VAL_FALSE value.

(No, that "/" is not a division operator.)

The right thing to do is to treat zero as false, non-zero as true, and
simply write
while (is_empty(q)) { ... }
or
while (!is_empty(q)) { ... }
depending on which condition you want.

 

[Barry Schwarz]

Here is the new fixed code, see if there are any more errors:

/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.1
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* IN C, 0 always means success ( e.g. EXIT_SUCCESS ), so I always use 0 for true and everything else for false */

Rubbish that has already been discussed.

enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
struct my_list* make_null( struct my_queue* );
struct my_list* is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );


int main( void )
{
struct my_queue* m = queue_new();

An empty queue.

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

The queue now has 5 nodes.

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );

The queue is again empty.

dequeue( m );

dequeue handles an empty queue properly.

queue_print( m );
printf(" Front = ");
queue_print_element( front(m) );

But queue_print_element does not. This invokes undefined behavior.

is_empty( m );

make_null( m );
free( m );
m = NULL;

return 0;
}
snip

struct my_queue* dequeue( struct my_queue* s )
{
struct my_list* r = NULL;

if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
printf("There are no elements in the queue\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
}
else
{
/* printf("Removing element\n"); */
r = s->head;
s->head = s->head->next; /* head removed from the queue */
free(r);

if( NULL == s->head ) /* in case we removed the last remaining element */
{
s->tail = s->head;
}
else
{
s->head->prev = NULL; /* set the prev of the to the NULL */
}
}


return s;
}
snip

struct my_list* front( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue not initialized ?\n", __LINE__);
}

return s->head;

The only time front is called, s->head is NULL.

}
snip

void queue_print( struct my_queue* s )
{
struct my_list* p = NULL;

if( NULL == s )
{
printf("Can not print a NULL queue\n");
}
else
{
for( p = s->head; p; p = p->next )
{
queue_print_element(p);
printf("NEXT = ");
queue_print_element(p->next);

This call also invokes undefined behavior when p==s->tail.

printf("PREV = ");
queue_print_element(p->prev);

This call also invokes undefined behavior when p==s->head.

printf("\n\n");
}
}

printf("--------------------------------------\n");

}

void queue_print_element( struct my_list* p )

When called with the value returned by front, p is NULL.

{
printf("arrc = [%s]\n", p->arrc);

Attempting to dereference p invokes undefined behavior in this case.

}


======================= OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra double-LL_queue.c
[arnuld@dune programs]$ ./a.out

What happened to the output from the first call to queue_print before
any nodes were added?

And you think this came from where?

arrc = [.]
NEXT = arrc = [lang]
PREV = arrc = [comp]


arrc = [lang]
NEXT = arrc = [.]
PREV = arrc = [.]


arrc = [.]
NEXT = arrc = [c]
PREV = arrc = [lang]


arrc = [c]
NEXT = arrc = [(null)]
Ditto?

PREV = arrc = [.]

Since this line (and its two previous clones) is the result of
undefined behavior, it is neither correct nor incorrect. Many other
systems will produce a very different result. Since the preceding and
following output confirm the queue is empty, why did you even consider
this as acceptable?

Queue is empty
[arnuld@dune programs]$

 

[arnuld]

If you wish this queue code to be generally useful, I recommend that
you remove the printf calls from the lower level functions, the
ones that are likely to be re-used. It is normally not a library
function's job to write error messages. Allow the caller to decide
what to write.

Take an example, is_empty() being called in main(), then I have to move
the printing of whether the queue was empty or not to main(). I have done
that but that increases the size of main() and I thought main() should not
be a larger function (counting number of lines). I have done the change
though. I return 0 for false and 1 for true But how do I differentiate
between "queue was empty" and "There was no queue at all". Using different
return values, like I have done down here.

I'm just going to point out one bug in your code. I have no doubt
there are more, but this is the first one I happened to spot. (It
is possible that it has been reported already and that you haven't
fixed it. I don't know, as I haven't read this thread very
thoroughly.)

...and you then evaluate retp, invoking undefined behaviour.

I learned that from the code of libmicrohttpd, a small web-server of GNU
family, I thought it returns the garbage value (which is never NULL). I
have changed fixed the code, see if there are more stupidities I have
done:



/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.2
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { QUEUE_NOT_EMPTY, QUEUE_EMPTY, QUEUE_NOT_INITIALIZED };
enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
struct my_list* make_null( struct my_queue* );
int is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );


int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );
printf(" Front = ");
queue_print_element( front(m) );

if( is_empty(m) )
{
printf("Queue is empty\n");
}
else
{
printf("Queue not empty\n");
}


make_null( m );
free( m );
m = NULL;

return 0;
}


struct my_queue* enqueue( struct my_queue* s, const char* c )
{
struct my_list* p = malloc( 1 * sizeof *p );

/* Check 1: the new element just malloc()ed */
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__ );
return s;
}

if( strlen(c) < SIZE_ARR )
{
strcpy( p->arrc, c );
p->prev = p->next = NULL;
}
else
{
printf("Size of array of the element is larger than required\n");
free(p);
return s;
}

/* Check 2: the original queue */
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
free(p);
}
else if( NULL == s->head && NULL == s->tail )
{
/* printf("Adding First element to Queue\n"); */
s->head = s->tail = p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
free(p);
return s;
}
else
{
/* printf("Adding element to the tail\n"); */
s->tail->next = p;
p->prev = s->tail;
s->tail = p;
}

return s;
}


struct my_queue* dequeue( struct my_queue* s )
{
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
printf("There are no elements in the queue\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
}
else
{
/* printf("Removing element\n"); */
struct my_list* r = s->head;
s->head = s->head->next; /* head removed from the queue */
free(r);

if( NULL == s->head ) /* in case we removed the last remaining element */
{
s->tail = s->head;
}
else
{
s->head->prev = NULL; /* set the prev of the head to the NULL */
}
}


return s;
}



struct my_list* make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );
}
else
{
while( s->head ) dequeue(s);
}

return s->head; /* head will be NULL if make_null was success */
}


struct my_list* front( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue not initialized ?\n", __LINE__);
}

return s->head;
}


int is_empty( struct my_queue* s )
{
int ret_value = QUEUE_NOT_EMPTY;

if( NULL == s )
{
ret_value = QUEUE_NOT_INITIALIZED;
}
else if( NULL == s->head && NULL == s->tail )
{
ret_value = QUEUE_EMPTY;
}

return ret_value;
}



struct my_queue* queue_new( void )
{
struct my_queue* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf( stderr, "LINE: %d, malloc() failed, can not initialize queue\n", __LINE__ );
exit( EXIT_FAILURE );
}

p->head = p->tail = NULL;

return p;
}


void queue_print( struct my_queue* s )
{
struct my_list* p = NULL;

if( NULL == s )
{
printf("Can not print a NULL queue\n");
}
else
{
for( p = s->head; p; p = p->next )
{
queue_print_element(p);
printf("PREV = ");
queue_print_element(p->prev);

printf("NEXT = ");
queue_print_element(p->next);
printf("\n\n");
}
}

printf("--------------------------------------\n");

}


void queue_print_element( struct my_list* p )
{
if( NULL == p )
{
printf("[NULL element]\n");
}
else
{
printf("[%s]\n", p->arrc);
}
}





===================== OUTPUT =================================
[arnuld@dune programs]$ ./a.out
--------------------------------------
[comp]
PREV = [NULL element]
NEXT = [.]


[.]
PREV = [comp]
NEXT = [lang]


[lang]
PREV = [.]
NEXT = [.]


[.]
PREV = [lang]
NEXT = [c]


[c]
PREV = [.]
NEXT = [NULL element]

 

[arnuld]

You're not learning that, if you have a doubley-linked list, and don't
actually make use of the double linkage.

Can you provide some practical exercise (small one) better than that ?

That's not a useful habit to form. Only return something it it's
actually of use to the caller.

In this small program I am not checking for the return value, but in the
programs I write for my employer, which is actually a part of a much
larger software (not written by me). Hence I always have to check the
return value otherwise all hell breaks loose, this is the only reason I
always return some value.

Yes you can. Mixing statements and declarations within a block is a C99
feature, but even in C90 each block was allowed to have it's own set of
declarations.

Thats a new thing I learned today

 

[arnuld]

..SNIP....
Since this line (and its two previous clones) is the result of
undefined behavior, it is neither correct nor incorrect. Many other
systems will produce a very different result. Since the preceding and
following output confirm the queue is empty, why did you even consider
this as acceptable?

No I don't, I really wonder why it even worked, it should have Segfaulted.
I have changed it, see my new code in my reply to Richard Heathfield.

 

[arnuld]

*Please* don't do this.

Truth vs. falsehood and success vs. failure are two distinct sets of
concepts. There is a convention, in *some* contexts,

Okay, I finally understood I think.

 

[James Kuyper]

Can you provide some practical exercise (small one) better than that ?

I haven't the time to come up with one, but the key thing that justifies
the use of doubly-linked lists is the necessity of traversing the list
in each direction. Try to imagine an application where you would need to
look backwards from a specified point in a list, as well as forward (If
you only needed to search backwards, just use a singly-linked list in
the opposite direction).

In this small program I am not checking for the return value, but in the
programs I write for my employer, which is actually a part of a much
larger software (not written by me). Hence I always have to check the
return value otherwise all hell breaks loose, this is the only reason I
always return some value.

The project I work on has coding standards that require that our
delivered code should always check for any error indicators returned by
a function. This is a good idea, in my opinion, for most functions.
However, if a function can't fail, at least not in a detectable fashion,
it should not return an error indicator that always says "no error", and
those coding standards don't apply to such a function.

Any function that can fail, and that can detect the fact that it can
fail, should report that fact back to the calling routine, and the
function's return value is my preferred way of doing so. For any
function that isn't already using the return value for an error code,
and which needs to return some other information back to the calling
routine, the designer should consider passing at least some of that
information back through the return value. However, if neither of those
apply, it shouldn't return something just for the sake of having
something to return.

The main exception to the "always check error indicators" rule is output
I/O functions. The standard I/O library provides "sticky" error
indicators, which means that they remain set until you explicitly clear
them with clearerr(). I sometimes take advantage of that by checking for
output errors only once, just before closing the output file. This
approach has obvious disadvantages, and should not be used where those
disadvantages matter. It's not a good idea to use this approach for
input functions: when one of those fail, the memory that was supposed to
contain your input data now contains garbage, and if you process it
without checking for the I/O error it usually can cause the rest of your
program to malfunction badly.