Linked List implementation of a Queue in C

May 13, 2009 at 11:51 am | Posted in C++ | 7 Comments
Tags: , , , , , , , , ,

A Queue is a FIFO based data structure. I tried to create one and got lots of advices and improvements from comp.lang.c folks. I am posting it here, in case someone gets benefit from that. I believe in Open Sharing of source code, it helps the community, it helpes the poor people like me who either did not have money to join some course or did not have enough of experience or a Master’s degree to get a job. Working on an Open Source software greatly improves the ability of the people to write quality code and also (as a side-effect) consumer always gets a robust product, a piece of software that they can trust. I am defnitely sure, you can’t trust a proprietary software, no one knows what its doing on your computer (except of the compnay who created it). MNCs are only intersted in making money and taking control of the market and doing a dishonest business always makes more money than doing an honest business. Having secrets of other corporations delievered to your doorstep always helpes in building a monopoly and I think proprietary software is a brilliant concept to spy on other companies and homes of general public. Never ever forget the Russian gas piple-line scandal. Perhaps reading some news will help.. You can even check amazon. Whether you are a government or an organization or an individual, you can not trust a piece of proprietary software, you don’t know what it does, you will never know.

I have seen people writing poor quality C code for years. They wrote poor C programs when they were 23 ( starting their Master’s degree) and when they were 25 (first day of the job) and now they are 29 and after 4 years of experience they still write poor quality code (Mostly these people are also the ones who have passed their professional degree in first division). Its because they are working in proprietary software based business company because of which they can not share their code. No critics and hence no improvement and in their spare time they never tried to read comp.lang.c archives though they do get time to shake beer glasses with their friends sometime or joke about the habist of their fellow team-mates or their boss or whetever they like but they never get time to read comp.lang.c

. You can always find the original duscussion of my program on Usenet.

/* This Queue implementation of singly linked list in C implements 3 
 * operations: add, remove and print elements in the list.  Well, actually, 
 * it implements 4 operations, lats one is list_free() but free() should not 
 * be considered the operation but  a mandatory practice like brushing 
 * teeth every morning, otherwise you will end up loosing some part of 
 * your body(the software) Its is the modified version of my singly linked 
 * list suggested by Ben from comp.lang.c . I was using one struct to do 
 * all the operations but Ben added a 2nd struct to make things easier and 
 * efficient.
 *
 * I was always using the strategy of searching through the list to find the
 *  end and then addd the value there. That way list_add() was O(n). Now I 
 * am keeping track of tail and always use  tail to add to the linked list, so 
 * the addition is always O(1), only at the cost of one assignment.
 *
 *
 * VERISON 0.5
 *
 */

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


struct my_struct
{
  int num;
  struct my_struct* next;
};


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


struct my_list* list_add_element( struct my_list*, const int);
struct my_list* list_remove_element( struct my_list*);


struct my_list* list_new(void);
struct my_list* list_free( struct my_list* );

void list_print( const struct my_list* );
void list_print_element(const struct my_struct* );


int main(void)
{
  struct my_list*  mt = NULL;

  mt = list_new();
  list_add_element(mt, 1);
  list_add_element(mt, 2);
  list_add_element(mt, 3);
  list_add_element(mt, 4); 
  
  list_print(mt);

  list_remove_element(mt);
  list_print(mt);

  list_free(mt);   /* always remember to free() the malloc()ed memory */
  free(mt);        /* free() if list is kept separate from free()ing the structure, I think its a good design */
  mt = NULL;      /* after free() always set that pointer to NULL, C will run havon on you if you try to use a dangling pointer */

  list_print(mt);

  return 0;
}



/* Will always return the pointer to my_list */
struct my_list* list_add_element(struct my_list* s, const int i)
{
  struct my_struct* p = malloc( 1 * sizeof(*p) );

  if( NULL == p )
    {
      fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
      return s; 
    }

  p->num = i;
  p->next = NULL;


  if( NULL == s )
    {
      printf("Queue not initialized\n");
      free(p);
      return s;
    }
  else if( NULL == s->head && NULL == s->tail )
    {
      /* printf("Empty list, adding p->num: %d\n\n", p->num);  */
      s->head = s->tail = p;
      return s;
    }
  else if( NULL == s->head || NULL == s->tail )
    {
      fprintf(stderr, "There is something seriously wrong with your assignment of head/tail to the list\n");
      free(p);
      return NULL;
    }
  else
    {
      /* printf("List not empty, adding element to tail\n"); */
      s->tail->next = p;
      s->tail = p;
    }

  return s;
}


/* This is a queue and it is FIFO, so we will always remove the first element */
struct my_list* list_remove_element( struct my_list* s )
{
  struct my_struct* h = NULL;
  struct my_struct* p = NULL;

  if( NULL == s )
    {
      printf("List is empty\n");
      return s;
    }
  else if( NULL == s->head && NULL == s->tail )
    {
      printf("Well, List is empty\n");
      return s;
    }
  else if( NULL == s->head || NULL == s->tail )
    {
      printf("There is something seriously wrong with your list\n");
      printf("One of the head/tail is empty while other is not \n");
      return s;
    }

  h = s->head;
  p = h->next;
  free(h);
  s->head = p;
  if( NULL == s->head )  s->tail = s->head;   /* The element tail was pointing to is free(), so we need an update */

  return s;
}
  

/* ---------------------- small helper fucntions ---------------------------------- */
struct my_list* list_free( struct my_list* s )
{
  while( s->head )
    {
      list_remove_element(s);
    }

  return s;
}

struct my_list* list_new(void)
{
  struct my_list* p = malloc( 1 * sizeof(*p));

  if( NULL == p )
    {
      fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
    }

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


void list_print( const struct my_list* ps )
{
  struct my_struct* p = NULL;

  if( ps )
    {
      for( p = ps->head; p; p = p->next )
	{
	  list_print_element(p);
	}
    }

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


void list_print_element(const struct my_struct* p )
{
  if( p ) 
    {
      printf("Num = %d\n", p->num);
    }
  else
    {
      printf("Can not print NULL struct \n");
    }
}

 

 


Copyright © 2006, 2007, 2008 Arnuld Uttre, #331/type-2/sector-1, Naya Nangal, Distt. – Ropar, Punjab (INDIA) – 140126

Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium, provided this notice, and the copyright notice, are preserved.

Advertisements

7 Comments »

RSS feed for comments on this post. TrackBack URI

  1. I think I’ve found a possible memory leak in the above code,

    On line 75, in the add_element you test whether the list has been initialised, and return on an error, without freeing the memory malloc’ed to p.


    if( NULL == s )
    {
    printf("Queue not initialized\n");
    free(p);
    return s;
    }

    • you did not find a memory leak because I already know this 😉 . Actually, I never got time to correct it. I will correct it as soon I find time to get into wordpress.com . Trouble is my browser becomes too slow and unresponsive when I open wordpress.com, this has something to do with my browser and not with wordpress website. I don’t have a computer at home, so I will correct it when I get one, it may take a few months . You can search comp.lang.c and IIRC, someone already mentioned this when I was learning this data structure.

      Thanks anyway. I like it when someone finds my mistakes (whether typos or real ones) 🙂

      • Memory Leak Corrected

  2. dont u have to store the returned pointer for the function called from main( the insert and delete function) ??

    • > dont u have to store the returned pointer for the function
      > called from main( the insert and delete function) ??

      I hope you meant “returned pointer from the function called from main”, and not “for the function”.

      It depends.

      If, in real life code, you want to use the returned pointer or want to validate whether the element was added or not then you can use the returned element. I just wanted to show the implementation of the concept and wanted to do it in as simple and as practical manner as possible and thats what you see.

  3. Kernighan and Ritchie explain a similar design (for a different purpose) in “self-referential structures”.

  4. I personally find that handling the creation of the nodes outside of the queue implementation is a lot better. In this case, it doesn’t make a whole lot of difference, but the “queue” by definition is only in charge of the FIFO process. You should put something in and retrieve it in the same form.

    In your code above, you put in and int, but you can’t get an int back. This makes it complicated if you want to put the element back in the queue. I would suggest writing functions like this:

    void list_add_element( struct my_list*, struct my_struct*); //You don't need to return the same pointer that you input.
    struct my_struct* list_get_element( struct my_list*); //You can use this to get the element or throw it away by not storing it
    my_struct* create_element(int i);
     
     
    struct my_list* list_new(void);
    struct my_list* list_free( struct my_list* );
     
    void list_print( const struct my_list* );
    void list_print_element(const struct my_struct* );
    

    Most of the time if you are using a queue, it means you will be adding more elements while you are removing them. This implementation allows you to work directly with the nodes, which is more elegant in my humble opinion.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: