4

The title is mostly self-explanatory: what are the advantages of linked lists over binary trees? The only case I can think of in which a linked list is more efficient is for iterating over every element, in which case it's still pretty close. It looks like binary trees are faster at both accessing data and inserting new elements. So why use a linked list at all?

5
  • 1
    What are the advantages of a binary tree over a 17-ary tree? If 2 is better than 1, then 17 is a whole lot better than 2, right? :-)
    – Ken
    Jan 10, 2010 at 5:58
  • 1
    @Ken: Only if you can make 17 comparisons in one operation.
    – P Daddy
    Jan 10, 2010 at 6:03
  • On top of everything mentioned already, linked lists are useful for implementing other data-structures, like stacks and queues. Jan 10, 2010 at 7:18
  • What are the advantages of apples over oranges?
    – starblue
    Jan 10, 2010 at 11:46
  • 5
    starblue: the lack of individual slices makes infix consumption O(1) rather than O(n), and the edible peel tends to lower the constant factor, too.
    – Ken
    Jan 10, 2010 at 17:27

7 Answers 7

7

If the tail of a linked list is stored, then insertion into a linked list is decidedly faster than insertion into a binary tree. Insertion into a binary tree is O(N) at worst case (O(log N) at best) if it's unbalanced. If it's balanced, then insertions are O(log N), but there is house keeping involved in keeping it balanced. Insertion into a linked list is O(1) if the tail is kept.

Also, as BillyONeal mentioned, a binary tree is usually an associative structure, whereas linked lists are not.

7
  • 2
    That's true for a binary search tree, but in the more general case of an (unsorted) binary tree, insertions are still O(1) -- a linked list is, after all, just a degenerate binary tree.
    – Ken
    Jan 10, 2010 at 6:12
  • @Ken: A tree is useless if some concept of sort isn't applied. This may not be a lexical order, perhaps, but some index. In any case, a path must be followed to find the correct node at which to add a new value, which still means O(log N) at best and O(N) at worst. An O(1) insertion can only apply if the node to which an item is added is unimportant, but in this case, lookups are O(N), and there is no organization to the data at all, so the overhead of a tree comes with no benefit.
    – P Daddy
    Jan 10, 2010 at 6:26
  • 3
    @P Daddy, Insertion is a confusing term when talking about linked lists. Append is the O(1) operation, insertion is O(n).
    – Ash
    Jan 10, 2010 at 6:30
  • 1
    P Daddy: My compiler here builds an AST. That's a tree which is not sorted by any key, yet still very useful. :-)
    – Ken
    Jan 10, 2010 at 7:06
  • 1
    Since the definition of "to sort" is "to place in order", I'd argue that yeah, it is, but it's a meaningless semantic argument. The point is that, given a ground state, a tree must be traversed to find the appropriate place at which to add a new item. It must have some concept of "follow this path to get to this node". This is the sole benefit of trees and their entire raison d'être. A tree with no concept of order is meaningless.
    – P Daddy
    Jan 10, 2010 at 20:53
4

It's easier/faster to delete items from a linked list compared to a binary tree which could require few operations to fix the tree.

2

A linked list is not generally used as an associative container (READ: Not to be used as a dictionary) -- only as a literal list of items, like an array. Binary trees' performance when such a simple data structure is desired is poor.

2

In linked list the objects are ordered by the container itself, so you don't need to have a comparison function for the objects.

0

A fair question. I like to use the container that most "tightly" fits my needs. For example, you can use a list when all you need is a queue with no real consequence either... but... queues are highly optimized for this one specific task of popping off the front, and inserting at the back, with no extra pointers, or anything. By using the most appropriate class, you can be sure you're not getting any extra fluff, even if it has the same Big-O. Sometimes those hidden constants do matter.

0

It mostly depends on scenario. If tail of linked list is maintained then insertion is fast in linked list. Deletion is quite fast in linked list but in case of searching it is better in trees( o(log(n) for height balance tree ) while o(n) in linked list.

0

I assume you're talking about actual binary search trees where the nodes are added using algorithms to maximize retrieval performance. As opposed to a simple tree where each node has a maximum of 2 child nodes.

A linked list is often unsorted and so addition of new nodes is simply an O(1) operation normally by appending to the tail of the list.

On the other hand a binary tree must store nodes in a specific ordering mechanism (and possibly enforce balancing) to provide for a more efficient searching/retrieval operation.

If your algorithm does NOT need to retrieve items very efficiently while also provide efficient sorting of the items, a linked list is probably all you need.

Queues and Stacks are examples of data structures that can be happily implemented using a linked list.

Note: Insertion to a linked list is a different (slower) operation than basic addition/append. Insertion often requires traversal along the list until the correct position is found, O(n) where n is the list length. An append is simply adding to the tail of the list (hence O(1))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.