## DEV Community is a community of 702,115 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Doubly Linked Lists and Memory

Zane Helton

## 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 is composed of 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 as*terisk means that `r_next` and `r_prev` hold memory addresses to another `Node` struct.

``````...

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:

``````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

One last thing I think is important to note about this example is the memory layout of this particular doubly linked list. I've included memory addresses in the output (above) so that this visual is more meaningful...

If you've dealt with lower-level memory 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
``````

## Great!

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 side-to-side rather than start-to-finish.

Some real-world examples:

• Music queues
• Undo and redo functions
• Blockchains (singly linked lists in reverse)

Thanks for following me through my first dev.to post!