Another thing to mention is the linked lists are a very old technique which was extremly usefull befor computers got very fast and had heaps of memory. Things like .NET, Java, and to a less extend the STL which allow you to have dynamic arrays are relativly new. If you were programming something in the 1980's then you either had to write your own dynamic array code or use a linked list. Both take about the same time to impliment but for the memory concious 1980's style programmer linked lists are definatly the better option in many situations (as has been said when deleting and inserting happens alot). Linked lists are still very handy today in all the areas stated, I'm just pointing out that historically they were quite important where as today we have more options.

EDIT: Added the word "impliment" to clear things up

[Edited by - kaysik on January 11, 2005 7:18:14 PM]

Quote:Original post by kaysik
Another thing to mention is the linked lists are a very old technique which was extremly usefull befor computers got very fast and had heaps of memory. Things like .NET, Java, and to a less extend the STL which allow you to have dynamic arrays are relativly new. If you were programming something in the 1980's then you either had to write your own dynamic array code or use a linked list. Both take about the same time but for the memory concious 1980's style programmer linked lists are definatly the better option in many situations (as has been said when deleting and inserting happens alot). Still linked lists can be very handy in all the areas stated, I'm just pointing out that historically they were quite important where as today we have more options.

dude, wtf r u smoking? .net and java's dynamic arrays ARE slower than C++'s linked lists plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses

Quote:Original post by caesar4
.net and java's dynamic arrays ARE slower than C++'s linked lists

They're entirely different structures with different algorithmic complexity. Your comparison makes no sense. Compare Java's and .NET's linked list implementation against C++'s, or compare their dynamic arrays against std::vector.

Quote:plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses

Certainly, that's one of the advantages of a linked list. It has disadvantages, however, such as the O(n) access time for elements not at either end.

Quote:Original post by caesar4
dude, wtf r u smoking? .net and java's dynamic arrays ARE slower than C++'s linked lists plus if u wonna insert an object at the beginning of a dyn array, u wuld have to MOVE the entire array whereas with a linked list all u have to do is create a new container and update a couple mem addresses

did you read my post? No where did I compare .net or java's dyamic arrays to c++'s linked lists ... my point was that historically linked lists were used in situations where now we have other options. If you were refereing to my comment "Both take about the same time but for the ..." then you misunderstood what I meant - my point was "Both take about the same time to IMPLIMENT but for ....", as in writing array code vs writing LL code isn't much different in terms of difficulty, but if you have 16k of memory you'll definatly choose linked lists instead of wasting mem on an array (if it fits the situation of course).

Quote:Original post by caesar4
there's no std implementation, but u may want to try creating chunked linked lists, which are a hybrid between linked lists and dynamic arrays

Am I wrong, or is that how deques are implemented?

Hi all,

I do reimplement linked-link to learn how exactly they work. It'll be helpful to learn how iterators work too for it'll increase the performance of the linked list for iteration.

I also believe that linked-list concept is a stepping stone to all other types of storage containers like hashtable, hashmap, map, tree and so on...

Afterall, we thought of using linked-list all because the use of arrays are way too troublesome and nasty most of the times. And things like trees and hashmaps came out to improve performance for object-search-and-get functions. I'm not sure if the original concept is derived from linked-list but I'm sure learning LL does help.

Using STL's storage algos is an easy way out having all the different types of containers suited for different purposes written nicely. However, to really use it properly and efficiently, you'll need to understand how it works logically.

Happy developing!!