NodeList Container: Fast Insertion, Fast Removal, No Memory Allocation

The (doubly) linked-list container allows for constant-time insertion and removal. However, the list implementation in the C++ standard library must dynamically allocate each new list node upon insertion; and dynamic memory allocation incurs additional runtime costs. A linked-list implementation where users can preallocate and supply the list nodes themselves can speed up insertion and removal time by avoiding the cost of dynamic memory allocations. To that purpose, I have implemented an alternate version of linked-list called NodeList (see github repository).

With NodeList, users are responsible for pre-allocating the nodes in the list. The users can then attach (insert) or detach (remove) those nodes from the node list. NodeList allows for fast insertion (and removal), as new nodes in the list are attached/detached instead of being dynamically allocated. Thus, Nodelist avoids the overhead of dynamically allocation. Reasonably fast iteration is also possible when the user allocates nodes next to each other in memory to get the benefits of cache locality. Other containers, such as plf::colony and plf::list also promise  fast insertion, fast removal and reasonably fast iteration speed, but may still spend time on memory allocation to adjust to a growing number of stored elements.

A straight-forward strategy for creating linked-lists is to add two fields to a class: a pointer to the next element and a pointer to a previous element. Then the linked-list is constructed by setting these pointers to the next and previous elements of the list. For example, let's say we are making a game and the game world contains a collection of game objects. A linked-list of game objects can be stored in the game world like so:

A programmer will then add the methods needed to insert and remove objects from the list, as well as iterate over the objects. NodeList generalizes this implementation and provides the user with insert (attach) and remove (detach) methods as well as  iterators and other convenience methods. The resulting code might then look like this:

The NodeList example above is not exactly equivalent to the linked-list example. The DataNode actually end up being comprised of 3 (instead of 2) pointers (next, previous, and data/GameObject*).  And the node list itself also have a bit of extra data for the iterators to use.

The NodeList is not a general-use container. Like with the  straight-forward linked-list implementation, one major downside with NodeList is that a node can only be attached to at most one list at a time. This is restriction shouldn't be a problem for many projects that follow a structure similar to entity-component-system; as typically, a component (GameObject) is either in, or not in, the associated system (GameWorld); and there is only one list of components  that needs to be managed per system. If the programmer wants to maintain a separate list of components, they can do so with a separate data node associated with each object, or use another container instead of NodeList).

The NodeList is a convenient and efficient implementation of the doubly-linked list. By giving the programmer control over the allocation and initialization of the nodes inside the list, the NodeList avoids the need for memory allocation during insertion. As an extra convenience, I wrote the NodeList so that nodes are automatically removed from the list when they are destructed. The NodeList may not be a general-use container, as nodes can only exist in one list at a time, but  I plan to use the NodeList where applicable in future projects going forward.

Categorized as C++

⌂ ⇦ ⇨