I'm currently trying to find the best data structure / algorithm that fits to my case:

I receive single unique random ids (uint32\_t), and I create an element associated to each new id.

1. I need to retrieve elements from the id.
2. I also need to access the next and the previous element from any element (or even id) in the order of creation. The order of creation mainly depends on the *current* element, which is always accessible aside, so the new element should be its next.

Here is an example:

```
(12) <-> (5) <-> (8) <-> (1)
 ^                        ^
 '------------------------'

```

If I suppose the current element to be (8) and a new element (3) is created, it should look like:

```
(12) <-> (5) <-> (8) <-> (3) <-> (1)
 ^                                ^
 '--------------------------------'

```

An important thing to consider is that insertion, deletion and search happen with almost the same (high) frequency. Not completely sure about how many elements will live at the same time, but I would say max ~1000.

Knowing all of this, I think about using an AVL with ids as the sorted keys, keeping the previous and the next element too.

In C language, something like this:

```
struct element {
  uint32_t id;
  /* some other fields */
  struct element *prev;
  struct element *next;      
}

struct node {
   struct element *elt;
   struct node *left;
   struct node *right;
};

static struct element* current;

```

Another idea may be to use a hash map, but then I would need to find the right hash function. Not completely sure it always beats the AVL in practice for this amount of elements though. It depends on the hash function anyway.

Is the AVL a good idea or should I consider something else for this case?

Thanks !

PS: I'm not a student trying to make you do my homework, I'm just trying to develop a simple window manager (just for fun).