Doubly Linked Lists and Memory

A What?

To kill two birds with one stone, here’s what a singly linked list looks like:

Starting at the (optional) “head” element, it’s clear that each element has some data, and a reference to the element after it. With that information, we can move forward through the list, but with a singly linked list, there’s no way to refer to previous elements in the list without additional information.

That’s where a doubly linked list shines 🌞

A doubly linked list is a data structure made up of elements in the same way that a singly linked list is, but with an additional reference to the element before it.

Let’s Make One!

// linked.c
#include <stdlib.h>
#include <stdio.h>

// what a node look like internally
struct Node {
  int idx;
  struct Node *r_next;
  struct Node *r_prev;
};

...

The code above defines our Node struct. For those of you who don’t get your daily dose of vitamin C, the asterisk means that r_next and r_prev hold memory addresses to another Node struct. They call this a “pointer” because it points to another piece of memory.

...

int main() {
  // define 3 nodes
  struct Node n0, n1, n2;

  // initialize the nodes
  n0.idx = 0;         // the first node has an index of 0
  n0.r_next = &n1;    // with a reference to the second node
  n0.r_prev = NULL;   // and a reference to NULL b/c there's no previous node

  n1.idx = 1;
  n1.r_next = &n2;
  n1.r_prev = &n0;

  n2.idx = 2;
  n2.r_next = NULL;
  n2.r_prev = &n1;

  // create a new reference to n0 called r_first_element
  struct Node *r_first_element = &n0;
  printf("The first node lives @ %p\n", r_first_element);
  printf("The first node has idx: %d\n", r_first_element->idx);

  // print n1 info
  printf("The second node lives @ %p\n", r_first_element->r_next);
  printf("The second node has idx: %d\n", r_first_element->r_next->idx);

  // print n2 info
  printf("The third node lives @ %p\n", r_first_element->r_next->r_next);
  printf("The third node has idx: %d\n", r_first_element->r_next->r_next->idx);

  return 0;
}

When compiled and executed, the output looks something like:

$ gcc linked.c -o linked
$ ./linked

The first node lives @ 0x7ffee41de960
The first node has idx: 0
The second node lives @ 0x7ffee41de948
The second node has idx: 1
The third node lives @ 0x7ffee41de930
The third node has idx: 2

To recap: we started by creating a Node struct with an index, a reference to the next node, and a reference to the previous node. Then, a new reference to n0 is created, and we called that r_first_element.

The doubly linked list is now setup and we can traverse and retrieve information by using the -> operator in C to read members of the Node struct.

Memory Layout

One last thing I think is important to know about this example is the memory layout. I’ve included memory addresses in the output (above) so that this visual is more meaningful…

If you’ve dealt with lower-level code before, you know there’s a stack that grows from higher memory addresses to lower memory addresses. That’s why n0– even if defined first is located at the highest memory address.

On the left, I’ve labeled the distance each node is from n0. n1 is located 24 bytes before n0 and n2 is located 48 bytes before n0.

This makes since because our Node struct is 24 bytes. We can confirm that with the following snippet:

printf("sizeof(struct Node): %lu", sizeof(struct Node));

Output:

sizeof(struct Node): 24

Conclusion

I’ll be honest, I’ve never used this data structure in my work, but I think it’s important to recognize these data structures for when it might be a fit in the future.

A doubly linked list is usually interchangeable with an array, but is more efficient if your data is moving to neighboring values rather than iterating from start-to-finish.

Some real-world examples might include:

• A deck of cards
• Music playlists
• Undo and redo functions

Further reading:

Open Data Structures: 3.2 Doubly Linked List