Linked Lists Vs Binary Search Tree

[peckitt99]

Hi im having a bit of trouble understanding some things

just wondering which is the best meathod to search with and what are the advantages of using either a linked list or binary search tree?

Thanks

[Loctan]

A binary search tree will provide logarithmic searching which is pretty good. Insertions or deletions will be more costly because they may require some tree rebalancing.

For your linked list, are you still going to keep the data in order or just stuff the nodes one after another? If you are putting them in no order, retrieval will be slow (linear) and insertions and deletions still won't be that fast. The problem with a linked list, if I remember correctly, is that you can't jump in the middle of a linked list. You start at the root and go to the next node then the next, etc. So you really can't perform a binary search or any kind of hashing on the data

Much more, and better than what I wrote, information can be obtained via wikipedia
http://en.wikipedia.org/wiki/Binary_search_tree
http://en.wikipedia.org/wiki/Linked_list

[MacNilly]

Hi im having a bit of trouble understanding some things

just wondering which is the best meathod to search with and what are the advantages of using either a linked list or binary search tree?

Thanks

A binary tree has a better time complexity for searching O(log N) but in the worst case can be the same as a linked list O(n). This means searching a binary tree will (in most cases) be faster than searching a linked list. Also, binary trees store values implicity sorted, so sorting operations are trivial.

Binary trees are great because they allow efficient sorting and searching. Their disadvantage is that in the worst case they can degenerate into a linked list in terms of efficiency. For example, inserting already-sorted data into a tree. Another disadvantage is coding complexity. Binary trees are much more complex than linked lists, especially for deletion and memory freeing. Also, to solve the problem of degeneration stated above, a self-balancing tree must be used which creates even more complexity.

Linked lists are simple to implement and have many practical applications, however, they have a lot of limitations. The best search algorithm that can be used on them is a linear search. The best sorting algorithms that can be used (probably Mergesort is the best for linked list) are not the best available. For example, any sort that requires random-access (ie. Quicksort) cannot be used on a linked list.

[peckitt99]

would it be possible for someone just to help me understand where i would choose to use a linked list structure rather than a binary tree and vica versa?

[Loctan]

would it be possible for someone just to help me understand where i would choose to use a linked list structure rather than a binary tree and vica versa?

I am not sure there are necessarily hard and fast rules for this, so this is more than opinion (to a large extent). Consider this hypothetical program. Suppose you have an address book and want to store People objects somehow so that you can retrieve information about the person (name, age, address, etc) Suppose the key is the person's name. Now, as you might imagine, people are going to want to get Sue Johnson, Albert Zudo, Michael Allan, etc. in any order. So, from the perspective of a program, the order you will be retrieving data will be random. IMO, a tree structure would be better here than a linked list. For a linked list to get to Albert Zudo you are going to have to retrieve the data by going through every entry before Albert Zudo (all A's, B's, etc) For a tree structure you can use a binary search (http://en.wikipedia.org/wiki/Binary_search). A binary search essentially lets you eliminate half of the possible choices on each comparison. A linked list only lets you eliminate one.

Similarly with insertions, to add someone to the address book you can simply do a binary search to find the insertion point for a tree. For a linked list you have to go through each item to find it's insertion points.

I am struggling to find a good example of where a linked list would be better than a tree structure so maybe someone else can hop in here and provide you one. I hope this helps.

[OnionKnight]

A binary search tree is pretty much always the best choice out of those two if you want fast selection of nodes.

If you wanted to know when a linked list is more suitable than a tree for other things then selecting, consider performing an operation on all, or just more than one, node. For a tree it would require O(log n) space (recursion) and for a list O(1) space.

EDIT: Oops, it shouldn't be O(n) for trees. Also, I'd like to point out that it doesn't have to apply to all forms of trees.

[laserlight]

I am struggling to find a good example of where a linked list would be better than a tree structure so maybe someone else can hop in here and provide you one.

Well, for one thing there are situations where a binary search tree simply does not work (unless it is a linked list). For example, a singly linked list that keeps track of its tail is a suitable candidate for implementing a queue.