From linked list to doubly linked list to circular doubly linked list.
Intro
In the following article, we will introduce a powerful data-structure and provide implementations in C for the most common cases.
Linked List
Linked lists are structures with pointers from link to link (often in a field of the structure called next (for obvious reason)). The list is implemented by having a pointer to the first link, then each link keeps a reference to the next link. The last link typically has a NULL pointer as reference to the next, indicating the end has been reached. Insertion at the front of the list only cost 2 pointer manipulations. They can be useful but have a major limitation: removing a link requires to look for the link and maintain a reference to the previous link while doing so. This can prove very inefficient for long lists. The basic solution to this pitfall would be to have a reference to the previous link inside the link itself.
Doubly Linked List (aka DLL not to be confused with DLL or DLL).
As explained above, the linked list deletion operation (among other) can be made more efficient by keeping a reference to the previous link inside the link itself. In fact, its cost become O(1) instead of O(n). Each link now gets a prev field pointing to the previous link. The first link has a NULL pointer in prev because no link exists before it. Like before, the last link has a NULL in next. Now insertion typically costs 4 pointer manipulations, and removing a link only 2 (and has the side effect of being reversible with the same cost if you are backtracking or something equivalent), if the link is known (else it still needs to be looked for). While this is already a great improvement, the cases of empty list and first element removal / insertion still require special attention. This is both costly in term of pointer manipulation and prone to implementation errors. The solution to those issues is to avoid the empty list situation and more or less remove the 'first link' situation in the process. And the way to achieve this is rather simple.
Circular Doubly Linked List
Remember how we previously had a variable pointing to the first element in the list, with the other links keeping reference of one other. This requires special attention when the first element is involved or when the list is or becomes empty. To eliminate those requirements, we change the way the list is referenced: instead of using a pointer to the first link, we use a link as a reference. More specifically, we only use the next and prev fields of this link. This has the following positive side effects:
- the list if never empty (it always contains at least one link)
- no element is at any specific place in the chain
- insertion between already existing link is the way to go and costs 4 pointer operations
- removing a known link only costs 2 pointer operations
- the list can be searched in both direct and reverse order at the same cost
- a reference to the last item is always available
- full search can start at any link
Yet, to have all of this auto-magically working, some care needs to be taken:
- the new link referencing the rest of the list must be properly initialized
- the 'empty list' test must be changed (to list->next == list)
- a search is complete when next points to the start element of the search (remember searches don't have to begin at the start of the list any more (but be sure to have a special value in the fake list link))
Multidimensional Circular Doubly Linked List
The power of the CDLL can be extended to more than one dimension, by the virtue of insertion between links and removal of a known link being reversible (if carefully done, though). For example, a 3-dimension structure can be devised with next and prev being transformed to left/right, up/down and front/back. For a real use case of a 2-D CDLL, see Knuth Dancing Links paper https://arxiv.org/pdf/cs/0011047.pdf, or any Youtube video on the subject (for example the one-and-a-half hour https://www.youtube.com/watch?v=_cR9zDlvP88). You can even search for "dancing links Sudoku" for application to Sudoku solving.
So, how to do it ?
The structure for a CDLL is the same as for a "regular" DLL, excepts we use a link to keep reference to the list (specifically to the first and last element of the list). Let's first declare our link structure. Self pointing type declaration has already been the source of numerous religion wars, so it won't be discussed here (anyway, even simply linked list requires this). In the following examples, the term "node" will be used because not all links are born equal.
typedef struct node {
struct node *prev;
struct node *next;
const char *tag;
} node_s;
static void cdll_init(node_s *node){
node->prev = node;
node->next = node;
}
For example, declaring and initializing a CDLL (i.e. creating an empty list) is done like this:
node_s list;
cdll_init(&list);
Not that complicated. OK, time to test if the list is empty. No NULL-pointer here, simply test if the node points to itself.
int cdll_is_empty(node_s *node){
return(node->next == node);
}
Not much more complicated than a NULL-pointer test. An empty list is not very useful, so let's add elements. Remember, the only actual insertion operation is "insert between". So we need to provide both the previous and next element to be able to do any insertion. This seems overly complicated, but isn't ! Let looks at the common insertions in a list and how to translate them to CDLL "between" insertion. We start with the basic insertion at head of list, so after the list node itself and the currently "first" element.
void cdll_insert_head(node_s *list, node_s *to_add){
cdll_insert_between(list, to_add, list->next);
}
Pretty elegant. But what if the list was empty ? Well, in that case, list->next points to itself so we add between list and list. And that's as simple as that. Want to insert an element at the tail ? Just as simple.
void cdll_insert_tail(node_s *list, node_s *to_add){
cdll_insert_between(list->prev, to_add, list);
}
Inserting before or after a known element is just as easy ! In fact it's the same as before with the provided node instead of the fake list node.
void cdll_insert_after(node_s *known, node_s *to_add){
cdll_insert_between(known, to_add, know->next);
}
void cdll_insert_before(node_s *known, node_s *to_add){
cdll_insert_between(known->prev, to_add, know);
}
And now, the actual implementation of insert_between().
void cdll_insert_between(node_s *before, node_s *to_add, node_s *after){
to_add->next = before->next;
to_add->prev = after->prev;
before->next = to_add;
after->prev = to_add;
}
Removing a node is even simpler.
void cdll_remove(node_s *to_remove){
to_remove->next->prev = to_remove->prev;
to_remove->prev->next = to_remove->next;
}
Notice how we didn't initialize prev and next inside to_remove. That's the trick that allows to re-insert the node at the exact same place in the list.
void cdll_insert_back(node_s *to_insert){
to_insert->prev->next = to_insert;
to_insert->next->prev = to_insert;
}
