quote:223ms to insert a node? Do you really think the STL could only insert 5 nodes per second on your computer?

He actually said 0. 223ms to insert a node. So that's about 4484 inserts a second.

Edited by - Zipster on November 4, 2001 2:20:03 AM

quote:Original post by Grib
The frustration that c_wraith feels is I think the fact that for most people the linked list is used as a general purpose expanding container. Not only is it in every data structures book, it''s the first data structure, and often the most advanced you learn in an intro programming course. stl::vector can handle 90% of the cases that a lot of people are writing thier own linked lists for. 90% of the remaining 10% are better with a stl::map.

Precisely. And I''ll stand by my assertion that Linked Lists are very rarely the best data type to use... When looking at what operations will be used by a given application in one of its data structures, the ones used most often are rarely the ones that are efficient in a linked list.

As Stoffel pointed out, there are a couple cases where linked lists are more efficient than anything else. But those are very rare applications.

The thing I think you're missing is the extensibility of linked lists. You can use them for stacks, skiplists, queues, deques, heaps, hash tables, and I'm sure many other containers that I didn't mention. All of those can be implemented easily using a linked list. There are ways to make them almost as fast as arrays too if you do your research. What other containers would you use for dynamic data anyway?? You can't make much use of an array because you'd continually need to resize it which is much less efficient than a simple node insertion. The bottom line is that if you don't know your data management requirements, you need a dynamic data structure; enter the linked list.

BTW, Magmai:
I'm fairly new to using the VC++ profiler and realized that the listed times are in seconds, not milliseconds. The profiler readout is misleading in that it denotes the data as milliseconds. So 0.013 is actually 13 milliseconds. I clocked, in release build insertion time for one int. Performance optimization was turned on for the build. The stl list clocked in at 13 milliseconds. My list clocked in at 3. I'm also going to profile it using the performance counter, but I think the results will be similar. That seems obscurely slow, but then again I'm only testing with a p2 450. ; )

Edited by - lunarss on November 5, 2001 1:24:29 AM

quote:Original post by lunarss
What other containers would you use for dynamic data anyway?? You can''t make much use of an array because you''d continually need to resize it which is much less efficient than a simple node insertion. The bottom line is that if you don''t know your data management requirements, you need a dynamic data structure; enter the linked list.

Dynamically reallocated arrays are a lot more efficient than you give them credit for... Have you actually timed them?

In my remarkably quick test using on-hand data structures (java''s java.util.LinkedList and java.util.Vector classes) I found that creating million element lists with each was about twice as fast with a dynamic array implementation (Vector) than with the linked list (LinkedList) implementation.

You may want to do more thorough testing in C, so that the environment is more deterministic. Due to hotspot optimizations, I saw some interesting (factor of two) fluctuations in performance at runtime in java. Still, the value I reported above is using the best time for the LinkedList, and the worst time for the Vector. I was just doing some quick and dirty testing to get some preliminary experimental numbers.

It all comes down to usage. If you often remove or add elements from anywhere but one end of the container, vector will not be a good idea. If the order of those elements is important (e.g. unsorted), linked lists are the way to go. Otherwise you want a map or hash table of some kind.

Oh, there is one really useful thing I forgot about linked lists. They can often be superimposed onto other data structures (ones not designed for easy traversal, in particular) for great benefit.

One common examples are threaded BSTs, which superimpose a linked list onto a BST to provide easier in-order traversal algorithms. Another is using singly linked lists to chain a hash table, or using doubly-linked lists to provide insertion order traversal of elements in a (usually sparse) hash table.

In those cases linked lists are very good choices because they involve adding very little to the existing structure, and take advantage of memory allocation already being done.

By the way, Stoffel... Let''s take a look at the usage pattern you specified: frequent adds and removes from the middle of an order-preserving (but not necessarily sorted) list.

That leaves out an important bit of information, which is the method of specifying where to add or remove. I think there are three basic approaches: Search for an element with a known value, use a given index to add/remove, or having a pointer to the value to add/remove.

In the third case, a linked list is most appropriate. However, the third case is a fairly rare case.

In the first, the best choice would be to use a doubly linked hash table, as described above. This gives the rapid searching advantage of a hash table.

The second case is the most interesting. In it, it''s possible to provide a balanced binary tree which isn''t a search tree. By including a tiny bit of bookkeeping information per node (the size of its subtrees), it''s possible to give O(lg n) insert by index, remove by index, and retrieve by index. In the case of a high amount of random access, that beats both linked lists and arrays easily.