[Home]
[Edit this page]
[Recent Changes]
[Special Pages]
[Help]
talk:Queue
This page is to discuss "Queue". You can ask questions or make comments.
What is a talkpage?
even a circular queue will run into the constraint that it can't get any larger than the array that contains it. linked lists are the best choice, IMO.
infidel 2002-12-16
Isn't a linked list also constrained to the size of the array that it's data is being stored in?
Jonathan 2002-12-17
No, linked lists are not arrays and do not use arrays for anything. They are simply a chain of user defined types strung together by pointers. Each node in the list is allocated dynamically when it is needed and destroyed when it is no longer needed. Individual nodes can be scattered throughout memory in any order because they use pointers within themselves to link together. The only constraint on the size of a linked list is the amount of memory availble for allocation to variables.
In contrast, an array is a specific block of memory that is allocated once to the size of one element times the number of elements. Arrays are more useful for implementing stacks, but only as long as you don't overflow them.
infidel 2002-12-17
I forgot to mention, it was the tutors at my college that taught me about linked lists. There, I was only shown an implementation where you had an array where one column was the pointer to the next bit of data, then the second the data. Figures huh?
Thanks for the explanation and for "showing me the light".
Jonathan 2002-12-19
You also need to take into account the language the linked list is implemented in:
In C++, you can dynamically allocate new UDTs and use a linked list "properly".
In VB, you can't allocate new UDTs dynamically. However, since you can non-destructively resize an array (to add an element), it makes a decent choice (and almost the only choice) for holding a linked list.
KDivad Leahcim
Dec 22
Well, I was shown them in VB, so I guess it figures I would only have seen the array implementation.
Jonathan 2002-12-22
[Edit this page] [Page history] [What links here] [Printer Friendly]
talk:Queue
This page is to discuss "Queue". You can ask questions or make comments.
What is a talkpage?
even a circular queue will run into the constraint that it can't get any larger than the array that contains it. linked lists are the best choice, IMO.
infidel 2002-12-16
Isn't a linked list also constrained to the size of the array that it's data is being stored in?
Jonathan 2002-12-17
No, linked lists are not arrays and do not use arrays for anything. They are simply a chain of user defined types strung together by pointers. Each node in the list is allocated dynamically when it is needed and destroyed when it is no longer needed. Individual nodes can be scattered throughout memory in any order because they use pointers within themselves to link together. The only constraint on the size of a linked list is the amount of memory availble for allocation to variables.
In contrast, an array is a specific block of memory that is allocated once to the size of one element times the number of elements. Arrays are more useful for implementing stacks, but only as long as you don't overflow them.
infidel 2002-12-17
I forgot to mention, it was the tutors at my college that taught me about linked lists. There, I was only shown an implementation where you had an array where one column was the pointer to the next bit of data, then the second the data. Figures huh?
Thanks for the explanation and for "showing me the light".
Jonathan 2002-12-19
You also need to take into account the language the linked list is implemented in:
In C++, you can dynamically allocate new UDTs and use a linked list "properly".
In VB, you can't allocate new UDTs dynamically. However, since you can non-destructively resize an array (to add an element), it makes a decent choice (and almost the only choice) for holding a linked list.
KDivad Leahcim
Dec 22
Well, I was shown them in VB, so I guess it figures I would only have seen the array implementation.
Jonathan 2002-12-22
[Edit this page] [Page history] [What links here] [Printer Friendly]
