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

It sounds like you want a priority queue, which would typically be implemented using a heap.

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.

Quote:

---

Originally Posted by laserlight

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?

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.

What you've described in your original post is called a "threaded tree".