arrays, linear linked lists and binary trees

This is a discussion on arrays, linear linked lists and binary trees within the C++ Programming forums, part of the General Programming Boards category; I know that arrays, linear linked lists and binary trees represent collections of items. I would like to get a ...

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    2

    arrays, linear linked lists and binary trees

    I know that arrays, linear linked lists and binary trees represent collections of items. I would like to get a better view of their implementation. Can anyone provide their opinions in so far as which one is better, and why? If you had to choose between them what would make you choose each one?

  2. #2
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    It depends what you want to do.

    Arrays are good if you want quick random access over a fixed number of elements, but not so good if there's a variable number of elements, or you want quick insertion deletion.

    Linear lists are good if you want sequential access to all elements with quick insertion/removal, but not so good if you need the elements sorted or need quick random access.

    Binary trees are good if you want fast access to sorted elements, with reasonably fast insertion/deletion, but not so good for random access.
    zen

  3. #3
    Registered User *pointer's Avatar
    Join Date
    Oct 2001
    Posts
    74
    It depends on what you plan to use them for. An array is best for a small amount of collected data of which you know how many there will be. Arrays are ideal for strings and tables.

    Linked lists are used when you do not know how many items there will be and you may want to place more than one item in an element and those items are of different types. Good for databases.

    Binary trees are best for if you want to find something in the tree FAST. I believe that the formula is log(n)2 for how many evaluations it will take. Also good for databases, probably better than linked lists but binary trees are difficult to set up. Though that difficulty is worth it when you can find an item in a tree of 20000 in around 30 evaluations.

    So the conclusion is that none of them is better than the other, just different. Each has it's own strength in an area. As for implementation...play with them and see which one works best for which application.
    pointer = NULL

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Saving linked lists to a binary file
    By kotoko in forum C Programming
    Replies: 1
    Last Post: 06-14-2008, 07:41 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 05:32 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Linked lists and Binary trees
    By Scotty in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 07-04-2002, 07:59 PM
  5. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 10:07 PM

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