Suppose I have a linked list that stores a book struct and the next node pointer:
struct book {
unsigned short size_of_content;
unsigned short price;
unsigned char *content;
};
struct list {
struct book p;
struct list *next;
};
And when I am constructing the linked list, I will check if the new book's price is the same as the price of one of the books that have been linked. Basically make sure that there is no duplicate prices.
I have an idea of constructing an price array and compare the new price with the existing ones. However, since C does not support unlimited size of arrays, I dont think my way is a good idea. What should I do? Thanks
Instead of creating an array or all that jazz you could just check if the price already exists in the linked list. Another method could be to add the price as you are adding it to the linked list to a dynamically sized array using the malloc function. http://www.cplusplus.com/reference/cstdlib/malloc/
But that seems inefficient because you will have to check the array every single time even as it grows to n size.
I think that would be the better way to do it.
You could even use a better data structure which is based on a linked list and its called a skip list.
Read here on skip lists http://en.wikipedia.org/wiki/Skip_list
These are actually really cool. Might be worth the time to try and implement this way.
EDIT: As the others have commented a binary search tree would be a better data structure for this problem.
If your price is an integer, that will be easy: allocate some bytes, initialize them to 0. Before you add a new book with price m, check the m-th bit in these bytes, if it is 1, then you have already had the price; if not, add this book and set the m-th bit to 1. In this case, you don't need to go through the linked list again and again to find the price and also the storage cost is limited.
