Just a quick note regarding a linked list classification that I have converged to after several years of embedded C programming.

This is not a rocket science by any means. It is more of a curious observation resulting from a constant need to count every byte of memory spent at run-time.

Well, go on already...

A linked list is assumed to consist of a list header and an arbitrary number of list items. The classification works by looking at the number of pointers used in the header and items.

Both the header and the item may have either 1 or 2 pointers each, and this translates to four list types:

• 1 and 1 - the s-list
• 2 and 1 - the q-list
• 1 and 2 - the h-list
• 2 and 2 - the d-list

The s-list

• 1 pointer in the header, 1 pointer in the item
• O(1) insertion at the head
• O(1) removal at the head

The s-list usage: stack, last in, first out.

The q-list

• 2 pointers in the header, 1 pointer in the item
• O(1) insertion at the head and at the tail
• O(1) removal at the head

The q-list usage: queue, first in, first out.

The h-list

• 1 pointer in the header, 2 pointers in the item
• O(1) insertion at the head
• O(1) removal at any position

The h-list usage: a bucket container in a hash table.

It is a common practice to resolve hash table collisions by storing same-key items in a linked list. In this case the memory usage of a sparsely populated hash table greatly depends on the size of an empty table cell. The hlist can be used to minimize this per-cell size.

The hlist is extensively used in the Linux kernel.

The d-list

• 2 pointers in the header, 2 pointers in the item
• O(1) insertion at the head and at the tail
• O(1) removal at any position

The d-list usage: the general purpose double-linked list.

So there you have it

A simple way of looking at linked lists, but quite useful nonetheless. It really helps selecting the right tool for the right job... that's assuming one is in the habit or in the need of writing memory-conscious code.

Addendum

As per a comment received on HN here is an interesting variation - the XOR list. Not exactly practical, but still very interesting because it is a singly-linked list that allows for bidirectional traversal.