My Ruminations on Software

Queue (singly linked list)

June 21, 2012 at 5:02 pm | Posted in Uncategorized | Leave a comment
Tags: enqueue/dequeue, Linked List, push/pop, Queue, queue in c, stack

After a long time I created a Queue(). Can you see what is wrong with it ? Just compile the program, can you spot at least 3 problems without running it ?

/* A queue implementation with the operations that I need:
 *  (1) Add an element to the front (head) of the queue
 *  (2) Remove an element from rear (tail) of the queue
 *  (2) remove an element with a unique ID (string constant)
 *  (3) compare 2 elements (string comparison) 
 *  (4) print queue
 *
 * VERSION 0.0
 */

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

enum { SIZE_ID = 100, SIZE_ARR = 20, REPS = 3 };

struct myQ
{
  char id[SIZE_ID+1];
  struct myQ* next;
};

struct myList
{
  struct myQ* head;
  struct myQ* tail;
};



struct myList* allocmyList(void);
int enqueue(struct myList* s, const char* id);
struct myQ* dequeue(struct myList** s); 
void removeElement(struct myList* s, const char* id);
struct myQ* searchElement(struct myList* s, const char* is, struct myQ** pr);
void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev);
void printQ(struct myList* s);


int main(void)
{
  struct myList* s = allocmyList();
  int i;
  for(i = 0; i < REPS; ++i)
    {
      int r;
      char arrc[SIZE_ARR+1];
      r = sprintf(arrc, "%d", i);
      if(0 > r) 
	{
	  printf("ERROR-SPRINF() = %d\n", r);
	}
      else
	{
	  enqueue(s, arrc);
	}
      printf("s->head = %p, s->tail = %p\n", (void*)s->head, (void*)s->tail);
    }
 
  printQ(s);
  dequeue(&s);
  printQ(s);
  free(s);

  return 0;
}


int enqueue(struct myList* s, const char* id)
{
  struct myQ *p;
  if(NULL == s || NULL == id) return -1;
  p = malloc(1 * (sizeof *p));
  if(NULL == p) return -1;
  strcpy(p->id, id);

  if(s->head)
    {
      p->next = s->head;
      s->head = p;
    }
  else
    {
      s->head = s->tail = p;
    }

  return 1;
}


struct myQ* dequeue(struct myList** s)
{
  struct myQ *temp, *prev;
  if(NULL == s || NULL == *s) return 0;
  if(NULL == (*s)->head) return 0;
  prev = (*s)->head;
  temp = (*s)->head;
  if(NULL == (*s)->head->next)
    {
      struct myQ* retp = (*s)->head;
      (*s)->head = (*s)->tail = NULL;
      return retp;
    }
  
  while(temp->next)
    {
      prev = temp;
      temp = temp->next;
    }

  (*s)->tail = prev;

  return temp;
}
       

void removeElement(struct myList* s, const char* id)
{
  struct myQ *p, *prev;
  if(NULL == s || NULL == id) return;
  p = searchElement(s, id, &prev);
  if(p)
    {
      deleteElement(s, p, prev);
    }
}


struct myQ* searchElement(struct myList* s, const char* id, struct myQ** pr)
{
  struct myQ *prev, *cur;
  prev = s->head;
  for(cur = s->head; cur; cur = cur->next)
    {
      if(0 == strcmp(cur->id, id)) { *pr = prev; return cur;}
      else prev = cur;
    }

  return NULL;
}


void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev)
{
  if(0 == strcmp(s->head->id, q->id)) /* removing head */
    {
      s->head = q->next;
      free(q);
    }
  else 
    {
      prev->next = q->next;
      free(q);
    }
}

void printQ(struct myList* s)
{
  if(s)
    {
      struct myQ* t;
      for(t = s->head; t; t = t->next) printf("ID = %s\n", t->id);
    }
  else
    {
      printf("Nothing to print\n");
    }

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

struct myList* allocmyList(void)
{
  struct myList* p = malloc(1 * (sizeof *p));
  if(NULL == p) exit(EXIT_FAILURE);
  p->head = NULL;
  p->tail = NULL;
  return p;
}

There are 3 problems:

1. Dequeue operation is O(N). In Queue, addition and deletion are O(1). Can you see why deletion is O(N) here ?
2. Dequeue does not need to take the address of original pointer. It is not needed.
3. Memory Leak. None of the elements are free()ed.
4. Enqueue() allocated new element but does not set its “next pointer” to NULL. This error was completely ignored by gcc on CentOS 5 machine I am using.

Here is the correct code:

/* A queue implementation with the operations that I need:
 *  (1) Add an element to the front (head) of the queue
 *  (2) Remove an element from rear (tail) of the queue
 *  (2) remove an element with a unique ID (string constant)
 *  (3) compare 2 elements (string comparison) 
 *  (4) print queue
 *
 * VERSION 0.1
 */

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

enum { SIZE_ID = 100, SIZE_ARR = 20, REPS = 3 };

struct myQ
{
  char id[SIZE_ID+1];
  struct myQ* next;
};

struct myList
{
  struct myQ* head;
  struct myQ* tail;
};



struct myList* allocmyList(void);
int enqueue(struct myList* s, const char* id);
struct myQ* dequeue(struct myList* s); 
void removeElement(struct myList* s, const char* id);
struct myQ* searchElement(struct myList* s, const char* is, struct myQ** pr);
void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev);
void printQ(struct myList* s);


int main(void)
{
  struct myQ* temp = NULL;
  struct myList* s = allocmyList();
  int i;
  for(i = 0; i < REPS; ++i)
    {
      int r;
      char arrc[SIZE_ARR+1];
      r = sprintf(arrc, "%d", i);
      if(0 > r) 
	{
	  printf("ERROR-SPRINF() = %d\n", r);
	}
      else
	{
	  enqueue(s, arrc);
	}
      printf("s->head = %p, s->tail = %p\n", (void*)s->head, (void*)s->tail);
    }
 
  printQ(s);
  temp = dequeue(s);
  free(temp);
  printQ(s);
  temp = dequeue(s);
  free(temp);
  printQ(s);
  temp = dequeue(s);
  free(temp);
  printQ(s);
  temp = dequeue(s);
  free(temp);
  printQ(s);
  free(s);

  return 0;
}


int enqueue(struct myList* s, const char* id)
{
  struct myQ *p;
  if(NULL == s || NULL == id) return -1;
  p = malloc(1 * (sizeof *p));
  if(NULL == p) return -1;
  strcpy(p->id, id);
  p->next = NULL;

  if(NULL == s->head) s->head = p;
  else s->tail->next = p;
  s->tail = p;

  return 1;
}


struct myQ* dequeue(struct myList* s)
{
  struct myQ *retp;
  if(NULL == s || NULL == s->head) return NULL;
  
  retp = s->head;
  s->head = s->head->next;
  if(NULL == s->head) s->tail = s->head;
  return retp;
}
       

void removeElement(struct myList* s, const char* id)
{
  struct myQ *p, *prev;
  if(NULL == s || NULL == id) return;
  p = searchElement(s, id, &prev);
  if(p)
    {
      deleteElement(s, p, prev);
    }
}


struct myQ* searchElement(struct myList* s, const char* id, struct myQ** pr)
{
  struct myQ *prev, *cur;
  prev = s->head;
  for(cur = s->head; cur; cur = cur->next)
    {
      if(0 == strcmp(cur->id, id)) { *pr = prev; return cur;}
      else prev = cur;
    }

  return NULL;
}


void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev)
{
  if(0 == strcmp(s->head->id, q->id)) /* removing head */
    {
      s->head = q->next;
      free(q);
    }
  else 
    {
      prev->next = q->next;
      free(q);
    }
}

void printQ(struct myList* s)
{
  if(s)
    {
      struct myQ* t = NULL;
      for(t = s->head; t; t = t->next) printf("ID = %s\n", t->id);
    }
  else
    {
      printf("Nothing to print\n");
    }

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

struct myList* allocmyList(void)
{
  struct myList* p = malloc(1 * (sizeof *p));
  if(NULL == p) exit(EXIT_FAILURE);
  p->head = NULL;
  p->tail = NULL;
  return p;
}

Deletion was O(N) because you get O(1) only if you add to tail and remove from head (in case of singly linked list) whereas I was adding to head and removing from tail and because of that I had to find previous pointer and set the tail of Queue to point to it and this operation was O(N).

 

Copyright © 2012 Arnuld Uttre, Village – Patti, P.O – Manakpur, Tehsil – Nangal, Distt. – Ropar, Punjab (INDIA)

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.