Linked Lists Vs Binary Search Tree

This is a discussion on Linked Lists Vs Binary Search Tree within the C++ Programming forums, part of the General Programming Boards category; Hi im having a bit of trouble understanding some things just wondering which is the best meathod to search with ...

  1. #1
    Is Trying to Learn
    Join Date
    Mar 2006
    Location
    Hutton, Preston
    Posts
    215

    Linked Lists Vs Binary Search Tree

    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

  2. #2
    System.out.println("");
    Join Date
    Jan 2005
    Posts
    84
    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
    Last edited by Loctan; 08-11-2007 at 08:06 AM. Reason: I don't htink what I originally had there was true.

  3. #3
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    311
    Quote Originally Posted by peckitt99 View Post
    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.

  4. #4
    Is Trying to Learn
    Join Date
    Mar 2006
    Location
    Hutton, Preston
    Posts
    215
    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?

  5. #5
    System.out.println("");
    Join Date
    Jan 2005
    Posts
    84
    Quote Originally Posted by peckitt99 View Post
    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.

  6. #6
    Mad OnionKnight's Avatar
    Join Date
    Jan 2005
    Location
    Umeň, Sweden
    Posts
    555
    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.
    Last edited by OnionKnight; 08-13-2007 at 11:28 PM.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,652
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21