Queue (singly linked list)
June 21, 2012 at 5:02 pm | Posted in Uncategorized | Leave a commentTags: 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:
- Dequeue operation is O(N). In Queue, addition and deletion are O(1). Can you see why deletion is O(N) here ?
- Dequeue does not need to take the address of original pointer. It is not needed.
- Memory Leak. None of the elements are free()ed.
- 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.
Linked List implementation of a Queue in C
May 13, 2009 at 11:51 am | Posted in C++ | 6 CommentsTags: C++, CIA, CIA bogus software, comp.lang.c, Linked List, open source, propriet, proprietary software, Queue, russian pipeline explosion
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.
Blog at WordPress.com. | Theme: Pool by Borja Fernandez.
Entries and comments feeds.
