Tue
25
May 2021

A doubly linked list is one of the most fundamental data structures. Each element contains, besides the value we want to store in this container, also a pointer to the previous and next element. This may not be the best choice for indexing i-th element or even traversing all elements quickly (as they are scattered in memory, performance may suffer because of poor cache utilization), but inserting an removing an element from any place in the list is quick.

Source: Doubly linked list at Wikipedia.

Inserting and removing elements is quick, but not necessarily very simple in terms of code complexity. We have to change pointers in the current element, previous and next one, as well as handle special cases when the current element is the first one (head/front) or the last one (tail/back) – a lot of special cases, which may be error-prone.

Therefore it is worth to encapsulate the logic inside some generic, container class. This authors of STL library did by defining List class inside #include <list>. It is a template, where each item of the list will contain our type T plus additional data needed – most likely pointer to the next and previous item.

struct MyStructure {
  int MyNumber;
};
std::list<MyStructure> list;
list.push_back(MyStructure{3});

In other words, our structure is contained inside one that is defined internally by STL. After resolving template, it may look somewhat like this:

struct STL_ListItem {
  STL_ListItem *Prev, *Next;
  MyStructure UserData;
};

What if we want to do the opposite – to contain “utility” pointers needed to implement the list inside our custom structure? Maybe we have a structure already defined and cannot change it or maybe we want each item to be a member of two different lists, e.g. sorted by different criteria, and so to contain two pairs of previous-next pointers? A definition of such structure is easy to imagine, but can we still implement some generic class of a list to hide all the complex logic of inserting and removing elements, which would work on our own structure?

struct MyStructure {
  int MyNumber = 0;
  MyStructure *Prev = nullptr, *Next = nullptr;
};

If we could do that, such data structure could be called an “intrusive linked list”, just like an “intrusive smart pointer” is a smart pointer which keeps reference counter inside the pointed object. Actually, all that our IntrusiveLinkedList class needs to work with our custom item structure, besides the type itself, is a way to access the pointer to the previous and next element. I came up with an idea to provide this access using a technique called “type traits” – a separate structure that exposes specific interface to deliver information on some other type. In our case, it is to read (for const pointer) or access by reference (for non-const pointer) the previous and next pointer.

The traits structure for MyStructure may look like this:

struct MyStructureTypeTraits {
  typedef MyStructure ItemType;
  static ItemType* GetPrev(const ItemType* item) { return item->Prev; }
  static ItemType* GetNext(const ItemType* item) { return item->Next; }
  static ItemType*& AccessPrev(ItemType* item) { return item->Prev; }
  static ItemType*& AccessNext(ItemType* item) { return item->Next; }
};

By having this, we can implement a class IntrusiveLinkedList<ItemTypeTraits> that will hold a pointer to the first and last item on the list and be able to insert, remove, and do other operations on the list, using a custom structure of an item, with custom pointers to previous and next item inside.

IntrusiveLinkedList<MyStructureTypeTraits> list;

list.PushBack(new MyStructure{1});
list.PushBack(new MyStructure{2});

for(MyStructure* i = list.Front(); i; i = list.GetNext(i))
  printf("%d\n", i->MyNumber); // prints 1, 2

while(!list.IsEmpty())
  delete list.PopBack();

I know this is nothing special, there are probably many such implementations on the Internet already, but I am happy with the result as it fulfilled my specific need elegantly.

To see the full implementation of my IntrusiveLinkedList class, go to D3D12MemAlloc.cpp file in D3D12 Memory Allocator library. One caveat is that the class doesn't allocate or free memory for the list items – this must be done by the user.

Comments | #algorithms #c++ Share

Comments