Data structure that inserts in constant time at endpoints and before/after an element?

Question

I am looking for a data structure that:

• Has an unbounded size.
• Maintains the insertion order of its elements.
• Inserts efficiently at the beginning and end of the list (ideally in constant time).
• Inserts efficiently before or after an existing element (ideally in constant time).

I ruled out ArrayList because it isn't efficient at inserting at the beginning of the list.

On the surface LinkedList should be a perfect match, but in practice the Java implementation isn't efficient at inserting before or after existing elements (i.e. it walks the entire list to find the insertion position).

(I don't personally need to store duplicate elements but others might)

---

Motivation: I am building an event queue that allows occasional cheating (inserting before or after an existing event).

Answer 1

Honestly I think a custom implementation of a LinkedList would be the way to go:

• Has an unbounded size.
  • Yes.
• Maintains the insertion order of its elements.
  • Yes.
• Inserts efficiently at the beginning and end of the list (ideally in constant time).
  • Yes, and O(1).
• Inserts efficiently before or after an existing element (ideally in constant time).
  • If you maintain a Map<?, Node> when inserting/removing elements, then you can access a Node (and its previous/next Nodes) in constant time and insert/remove that way.

Depending on the total amount of events (and how often events can cheat), linear time could be considered as well, allowing you to use the API's implementation of LinkedList.