Printable View
Yes, that's a good summary.
When you set queue->last->next to x the first time around, queue->last and queue->first point the same thing. So queue->first->next is set to x. Next time, queue->first->next->next is being set, but it's not using this convoluted method, but rather the simple method of setting queue->last->next = x;
--
Mats
Except for when you do do it. Let's say the first node gets address 0x1000. We set the pointer in this node to NULL, and set q.first = q.last = 0x1000.Quote:
Originally Posted by Nazgulled
We then allocate another node; let's say it it gets address 0x1008. We need to hook it onto the chain, so we find q.last = 0x1000 and set the pointer in that node to point to 0x1008. The pointer in 0x1008 gets set to NULL and then q.last gets set to 0x1008. The situation is now:
q: 0x1000 -> 0x1008 -> NULL
q.first = 0x1000
q.first->next = pointer of 0x1000 = 0x1008
q.last = 0x1008
Note that when there was only one element in the queue, q.last = q.first. So setting q.last->next also sets q.first->next in this case, since q.last and q.first point to the same object. Just because it was referred to as q.last in your code, doesn't mean it can't equal q.first.
And if we added another one (say 0x1008 now points at 0x1010), so that
q: 0x1000 -> 0x1008 -> 0x1010 -> NULL
q.first = 0x1000
q.first->next = pointer of 0x1000 = 0x1008
q.first->next->next = pointer of (pointer of 0x1000) = pointer of 0x1008 = 0x1010.
Better?
(You know, I would think someone, somewhere, has turned this into a movie. I wonder who and where.)
That's somewhat the kind of explanation I was waiting for... I think I get a better picture of the whole thing now. Now that I got most of this whole thing... Thank you very much, all of you!
1) Why exactly do I need a queue with a pointer to the beginning and end of the queue? In what is this method helpful?
2) How would you code (in the most simple form) the print queue function?
3) Using this structure for the queue, how would you implement a circular buffer? Taking advantage of the first and last pointers. Or do I need another pointer to point to the next free space? I can't see how would I do this...
I just posted a response that will answer your first question, look near the end of page 1.Quote:
Originally Posted by Nazgulled
In the simplest form, to print a queue (from front to back) heres some pseudo-code:
Circular buffers are implemented using arrays, not linked lists. You could implement using a circularly linked list, where the last node's next pointer goes back to the front... but they are two entirely different beasts. Actually you can have constant-time enqueue and dequeue operations if you code everything correctly, there is no need for a circular buffer or a circularly-linked list. Just keep it the way it is.Code:define p as type pointer-to-node
let p = head of queue
while (p != NULL)
print data
let p = p->next
end while
First, it's quicker. You only beed to do q->first or q->last to find the last or first node in the list.Quote:
Originally Posted by Nazgulled
Otherwise you have to do q->first->next->next->next, etc until next is NULL, at which point you have found the end. It's simpler.
Second it's also faster because you don't have to walk the list to the end. You can just jump to the end directly.
@MacNilly
It doesn't matter if there is a need for a circular buffer or not, this is not an exercise or a school project, I just want to know how things work. And a circulary linked list is one of those things that I would like to know how it works and how it's coded. Can you provide any link explaining the whole thing? I tried to look for an example on google but couldn't find anything.
About your pseudo-code:
Why define p as as type pointer-to-node and assign the head of queue to p? Why can't I just traverse q->first directly?
@Elysia
But why do I need to access directly to the end of the queue? I will only have one element the end and the next pointer will be pointing to null, why would I need only this last element to use a method like his instead of the trivial q->next->next->next... that I'm used to? Why would I need to access the last element?
Well, an easy way would be to do q->last->next = q->first. Why? Because it would mak the last node in the list point to the first, so when you reach the end, and try to move further, you get back to the beginning again! Thus it's circular.Quote:
Originally Posted by Nazgulled
If you want to traverse a node and you don't know the end, then you need a temporary pointer which you can use to traverse with. You can do quene->first->next->next->next, but how do you know where the end is? Further, if you actually try to walk further than the end, you try to dereference NULL, which will lead to a crash.Quote:
About your pseudo-code:
Why define p as as type pointer-to-node and assign the head of queue to p? Why can't I just traverse q->first directly?
Therefore, we use a temporary variable, assign that to quene->first, and then check if p == NULL (in which case there's only one node in the list, since q->first is the first node and if the first node points to NULL, there is no second node, no node after the first node).
Because you get to the end of the list quickly!Quote:
@Elysia
But why do I need to access directly to the end of the queue? I will only have one element the end and the next pointer will be pointing to null, why would I need only this last element to use a method like his instead of the trivial q->next->next->next... that I'm used to? Why would I need to access the last element?
When you want to insert something at the end of the list, you need to set the last node's next to the new last, right? So you need to traverse the list to find the last node so you can assign its next!
But with a end pointer, you can simply use it to skip to the end directly. No need to traverse the list to get to the end. It's more efficient too.
Which method do you find more efficient - say you have a bunch of papers and you don't know which one is the last, but each paper points to the paper that comes next and you know which paper is the first. Would you examine all the papers to eventually get to the end or would you just check in a last or ask someone which paper is the last and get it directly?
It's the same thing.
I would completely agree with this: A circular buffer is a way to implement a FIFO[1], where a queue is a different implementation to solve a FIFO. There are different advantages with each of those solutions: a circular buffer is [usually] implemented as an array, where you have an "in" and an "out" index, so "stuff" is put into the "in" index, and the index is progressed to the next entry, and "stuff" is taken out at the "out" index and the index progressed to the next entry. The drawback of a array based FIFO is that it's limited to a certain size. You have to use the correct checks to make sure that the circular buffer doesn't overflow, and if you get into that situation, things can go very wrong.Quote:
Originally Posted by MacNilly
A queue FIFO requires allocation to insert, and freeing when you remove items from the list, but has an "unlimited"[2] size. You can of course add some sort of counter to track the number of entries in the queue, and "refuse" when it gets too long.
Which is better depends a lot on what the exact problem is.
[1] FIFO means "First in, first out", as opposed to a LIFO - last in, first out -> a stack.
[2] Obviously, there is a limit, but it's determined by the amount of memory, rather than something compiled into the code at build-time.
--
Mats
That's what I thought but that leaves me to another question. Let's say I do that (q->last->next = q->first) and in my print list I would "loop" until q->last->next != NULL, this would mean that I would be "looping" through all the queue elements over and over again right? There would be no real way to know which element is the first and which one is the last, right?Quote:
Originally Posted by Elysia
So, you are saying that this:Quote:
Originally Posted by Elysia
would crash? But wouldn't crash if I used a temporary variable?Code:do{ ... } while(q->first->next);
Got it!Quote:
Originally Posted by Elysia
@matsp
I only asked about Circularly Linked Lists because I saw something about them in Wikipedia:
And after reading this again, besides the point that Elysia pointed I'm not seeing how would I implement the insert, delete and print functions. And I would really like to know that. It's not for an exercise or something, I just want to know how things work so I have more knowledge on the subject.Quote:
Originally Posted by http://en.wikipedia.org/wiki/Linked_list#Singly-circularly-linked_list
A circular linked list just uses "first" as a marker for end, rather than NULL. It can be practical for certain types of implementations, as you can be guaranteed to NEVER hit a NULL pointer - but you still need to compare with "first" instead for most places where you now compare with NULL. And set the next pointer to "first" instead of NULL whenever you set up a new link.
As to your code example, you can not dereference queue->first->something if queue->first == NULL - that will crash.
--
Mats
The best way would be to keep track of the end of and the start of the list (those start and end pointer we're talking about). So you check to see if p->next is q->first. That would mean you found the last node because the last node points to the first!Quote:
Originally Posted by Nazgulled
As matsp points out, if q->first is NULL, then yes, it will crash.Quote:
So, you are saying that this:would crash? But wouldn't crash if I used a temporary variable?Code:do{ ... } while(q->first->next);
But you also need to advance in the list, so you need to store p->first first, then keep on looping while p->next is not NULL. Then you assign p->next to p and you get the next node. And so on.
About the crashing/listing the elements, I have a few questions as I did some testing using the same structures defined as in the first post.
I used the following code with a temporary variable just like you guys said like this:
This works, I can call this function over and over and it works fine. Then I tested the way you said it would crash, like this:Code:void listQueue(Queue *q) {
Node *ptr;
ptr = q->first;
while(ptr) {
printf("%d", ptr->elem);
ptr = ptr->next;
}
}
This also works, it didn't crash. Well, for some part. I mean, I called listQueue() once and it listed everything without crashing, however, calling it again, crashed with segmentation fault. This was the crashing you were talking about right?Code:void listQueue(Queue *q) {
while(q->first) {
printf("%d", q->first->elem);
q->first = q->first->next;
}
}
But, this happens because we are passing the queue argument as a pointer and I decided to do it like this instead:
For this to work, I would have to call the function like this, listQueue(*q), instead of, listQueue(q) as in the previous examples. So, isn't this a better way? I have a feeling you are going to say it's not and I should opt for the method with a temporary variable. But why is that method better? What are the differences?Code:void listQueue(Queue q) {
while(q.first) {
printf("%d", q.first->elem);
q.first = q.first->next;
}
}
Why is that code doing? It's overwriting the previous variable.
It's like erasing your index pointer to the first element and replacing it with first->next.
So when the function is complete q.first will be NULL. Oops! Yes. You lost track of the first element in the list.
While the second approach works, it's not necessarily the best and to me it looks like a very poor workaround. Basically you're just creating a copy of the Queue pointer for the function to mess around with. But it's also copying the entire Queue structure, which is larger than a single pointer. Your structure is currently 8 bytes, while a pointer is a mere 4 bytes.
Also, note that a for loop might be better for this purpose:
Also, since it's a pointer, the function can modify the data you passed it and it will reflect from the function that calls it. In this case, you would probably not want it to modify the memory because it's just listing the contents. So make it const. It tells the compiler that the function can't modify the memory it points to. And thus you get a compile error with the second of your examples because you modify the memory.Code:void listQueue(const Queue *q)
{
for (Node* ptr = q->first; p != NULL; p = p->next)
{
printf("%d", ptr->elem);
}
}
You are right... I'm stupid and confusing everything that I missed that. What you stated here it's so obvious that I feel ashamed. :xQuote:
Originally Posted by Elysia
Isn't that more like a syntax choice? That code and the code I posted earlier is basically the same thing isn't it?Quote:
Originally Posted by Elysia
What do you mean by that (the text in bold)? Are you telling me to declare some variable as 'const'? I'm used to that in another languages but I don't know how to do it C nor which variable you were talking about. Can you be more specific and also tell me how do I use 'const' in C or you meant something different?Quote:
Originally Posted by Elysia
And I'm still confused about this!Quote:
Originally Posted by Elysia
Yes, it's the same thing.Quote:
Originally Posted by Nazgulled
Let me show you with an example:Quote:
What do you mean by that (the text in bold)? Are you telling me to declare some variable as 'const'? I'm used to that in another languages but I don't know how to do it C nor which variable you were talking about. Can you be more specific and also tell me how do I use 'const' in C or you meant something different?
Code:void foo(const int* pNum)
{
*pNum = 50; /* Compile error! Not allowed to modify variable because it's const */
}
void foo2(int* pNum)
{
*pNum = 50;
}
int main()
{
int myint;
foo(&myint);
foo2(&myint);
/* myint is now 50 */
return 0;
}
Quote:
And I'm still confused about this!
Remember: in a circular list, the last node will point to the first node. q->first will also keep track of the first node in the list, so if they match... then it means that the pointer is pointing to the first node in the list!Code:void listQueue(const Queue *q)
{
for (Node* ptr = q->first; p != q->first; p = p->next)
{
printf("%d", ptr->elem);
}
}