Thread: Binary Tree -vs- Linked List

If a binary tree's worst-case-scenario is a structure already in order (i.e. a linked list), then what benefit is there to -ever- use a linked list? Since you're guaranteed equal or better efficiency with a binary tree, I see no logical reason for linked lists to even exist functionally, yet I find them everywhere?

I'm sorry if this is off-topic for this forum, but I'm actually curious about this question in relation to the C language, since I'm unsure if the answer would be different depending on that or not, and it's the only language I use. Thanks for any help.

Linked lists are
- much simpler to implement
- not a performance problem for small lists
- work well when you don't have an ordering relationship.
- you don't need to do lots and lots of searching.

Trees are
- harder to write
- can be very expensive to keep balanced
- imply that the elements can be ordered

So if you have a large amount of fairly static data which you need to search a lot, and you have some kind of ordering relationship, then building a balanced tree out of it might be worth doing.

Ok, if I had a list of up to, say, 1000 nodes, and could order them with a fairly 'random' key (good for balancing), would the efficiency that a binary tree provides even be noticeable over a 1000 node linked list?

Obviously if I had a list of hundreds of thousands or millions of nodes, the efficiency would show. But what about for smaller sized lists (like 1000 nodes)?

How can I reliably test this in my code? I know I'd need to be able to get the time at a certain point before the traversal, then get it at the end and compare the difference - but what function(s) is/are reliable and accurate enough to compare the miniscule times I'd be getting?

Instead of trying to measure the thickness of one piece of paper, measure the thickness of 100 pieces of paper and then divide by 100.

> would the efficiency that a binary tree provides even be noticeable over a 1000 node linked list?
Efficiency of what?
Inserting at head/tail of a linked list is trivial compared to the cost of inserting the last node into a binary tree.
It's definitely got the edge on searching, but unless you do a lot of it, its hard to know where the cut-off point is.

If for example your list is actually the lines of a file in the order the lines where read from a file, then storing that in a tree makes no sense at all.

> but what function(s) is/are reliable and accurate enough to compare the miniscule times I'd be getting?
State your OS/Compiler for more information.
http://msdn.microsoft.com/library/de...ncecounter.asp
Or my use of rdtsc here http://cboard.cprogramming.com/showt...ighlight=rdtsc

@ Salem:

I guess I was referring just to general efficiency. In my implementation, I need a structured list to hold approximately ~1000 or so nodes, each containing some numerical data, some string data, and sorted by a fairly random unsigned int field.

These nodes will be added and removed at a fairly low rate (maybe a call every minute or two) so I'm not too worried about that. I will be doing a -lot- of searching though, and I'm trying to figure out what structure would best fit my needs. I assumed that my two best choices were a binary tree or linked list, but I'm not limited to one or the other.

And I'm using gcc 4.0.0 on an x86 64 (2.6.14 kernel).

Big-Oh notation gives a general guide to the worst-case "large" answer, but simple algorithms and data structures are often quicker for small 'n'.

For example, you're changing the data by 1 node every minute, then even a simple array based answer sorted by bubble sort (which would only take 1 pass to sort an array which is only out of sort by 1 element). Then you could use the standard bsearch() function to search the array very efficiently.