Thread: Linked and binary lists

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    51

    Linked and binary lists

    I was wondering when you should actually use these lists? or when you should want to avoid them? Thanks for helping me try to sort out these concpets

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I take it you mean a binary tree, rather than a binary list.

    The question of what you use when is one of those interesting questions that one can spend a lot of time debating.

    First of all, many of the problems where linked lists are involved can be solved with the standard vector template class.

    Linked lists are useful when you want to keep large objects that are usually added/removed from one or the other end of the list, you don't often need to search the list to find something. It is particularly useful if the items stored are fairly large, rather than many small objects (say, a linked list of int's is a bad thing, whilst a linked list of 1KB data items may be a much better choice).

    Binary trees are useful if you need to store and find things in sorted order - although inserting in a linked list is easy, to search it is linear to the number of elements, whilst a binary tree takes log2(n) operations to search, so a 1000 entry binary tree should take 10 searches to find the right entry [1].

    Note on performance: If the code spends a lot of it's time actually traversing the data in the list/tree, then one of the concerns will be that the nodes will not be in consecutive memory, so the caching and processors prefetch mechanisms will not work very well. Vectors that are implemented using large chunks of contiguous memory will give better performance from that perspective.

    [1] This assumes that the tree is balanced. If you insert items that are already sorted into a binary tree, it will deteriorate to a linked list unless it's a "balanced binary tree".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I think he means skip lists.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by indigo0086 View Post
    I think he means skip lists.
    And someone else will think he means doubly-linked-list. He needs to clarify!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Dec 2006
    Posts
    51
    Heh sorry I meant binary trees. I never heard of skip lists though. So when do you know when an object is too big for a vector?

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    I don't think it works that way. I think the biggest concern with data structures is the number of elements in a data structure, how they are organized, the speed of performing operations on the ds and it's elements, and things of that sort. Big objects will have to be stored in memory some way or another.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    One of the reasons I mention "large objects" is that if you insert or delete things in the middle of a vector, the vector content will have to be shuffled. Naturally, large amounts of data will require a larger amount of time move the data in the vector around.

    In the linked list case, an insertion or removal is independent of the amount of data stored in the list in the sense that there's no movement of data when inserting - just two pointer writes.

    Yes, all the data needs to be stored somewhere, but if the data isn't shuffled around, then it's a benefit.

    The drawback of linked lists comes with traversing them - there's really no way to search them cleverly - you just have to start at one end and search until you find what you're looking for (or know it's not in the list, if that's the case - either end of the list or you know from the comparison that you've gone past the point of finding it if it's a sorted list).

    Binary trees, as long as they are in reasonable balance (not all the entries are in one long linked list on the left or right side of the tree), the searching is faster. Deleting out of binary trees can be a bit tricky too.

    Both binary trees and linked lists have a drawback when used for LARGE number of items, particularly if the items are small, since the overhead of looking at the link for the next item is notable. In these cases, a vector or similar is definitely the better case.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 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
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04: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. Array, Linked List, or Binary Tree?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 01-05-2002, 10:07 PM
  5. arrays, linear linked lists and binary trees
    By jasingle in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2001, 11:12 AM