Doubly linked list vs vector for arbitrary delete/insert

I need to store an ordered list of items and do arbitrary insert/delete at arbitrary location.

The two choices seem to be vector vs doubly linked list.

In theory, vec is O(N) worst case, while DLL is O(1) worst case.

In practice, however, Vec probably has great memory/cache behaviour wyyhile DLL is pointer chasing all over the place.

Are tehre rules for thumb for how big the collection should be when deciding Vec vs DLL ?

The rule of thumb: use vector unless you know exactly you need doubly linked list. List has O(N) linear access unless cached. And moving chunks of vector is usually cheap - because vectors are usually small.

Otherwise please provide more detail on what you want to achieve. Are you sure you have such scenario that you need to be concerned with performance?

Since it's ordered, is there a reason a BTreeSet wouldn't work?

@target_san : I am implementing something like a "HTML DOMTree editor"

I need to be able to click on DOM elements andx

  1. delete it
  2. modify it
  3. add an element to the left or right of it

The question becomes: a DOM element has a bunch of children. Do I want to store the children as a Vec of DOM nodes, or a DLL of DOM Nodes ?

See this video from Stroustrup on how big N should be for which a linked list outperforms a vector: Bjarne Stroustrup: Why you should avoid Linked Lists - YouTube. TLDR: always go with a vector unless you know the linked list performs better because you've measured it.

2 Likes