Thread: List Tree - New data structure

  1. #1
    Registered User
    Join Date
    Aug 2008
    Posts
    2

    Thumbs up List Tree - New data structure

    What is a List Tree?
    It is a data structure that combinds the beauty of a Linked List and Binary Tree.

    Why?
    The linked-list and binary-tree components of List Tree complement eachother perfectly:
    *Iterate through items in a sorted manner. (linked list)
    *Search & add new items at logarithmic speed. (binary tree)

    What does it look like?
    Code:
    struct ListTreeItem {
        ListTreeItem *prev, *next; // linked list part
        ListTreeItem *parent, *leftchild, *rightchild; // binary tree part
        void* userdata; // placeholder
    };

    Background:
    I need to implement a TimerManager for a preformance-critical project. My requierments are:
    *Keep timers sorted by nearest-in-time -> Solution: linked list
    *Add new timers without comparing from-begin-to-end -> Solution: binary tree

    I appreciate any feedback. Is this implemented already or is there a better solution?

    Cheers
    /sincoder

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    It sounds like you want a priority queue, which would typically be implemented using a heap.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Also, linear iteration through a tree is amortized linear time, so the linked list part is unnecessary. More importantly, you don't need the iteration for your use case, so managing the linked list part only adds overhead.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    Registered User
    Join Date
    Aug 2008
    Posts
    2
    Quote Originally Posted by laserlight View Post
    It sounds like you want a priority queue, which would typically be implemented using a heap.
    Great stuff man. priority_queue is almost exactly what I was looking for. But one thing that's missing, which I didn't mention above. I need to remove any timer (not just the one at the top). Is there any priority_queue with erase() or a good binary heap implementation?
    Last edited by sincoder; 08-12-2008 at 06:45 AM.

  5. #5
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    It's not hard to create yourself using the std::heap_* algorithms. Note, however, that the search for a specific element other than the top in a max-heap is linear.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    What you've described in your original post is called a "threaded tree".
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about a working linked list
    By cold_dog in forum C++ Programming
    Replies: 23
    Last Post: 09-13-2006, 01:00 AM
  2. HUGE fps jump
    By DavidP in forum Game Programming
    Replies: 23
    Last Post: 07-01-2004, 10:36 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

Tags for this Thread