- Published on
Doubly Linked Lists and Memory
- Authors
- Name
- Zane Helton
- @ZaneHelton
A What?
To kill two birds with one stone, here's what a singly linked list looks like:
![Singly Linked List](/_next/image?url=%2Fstatic%2Fimages%2Fsingly-linked-list.png&w=1200&q=75)
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.
![Doubly Linked List](/_next/image?url=%2Fstatic%2Fimages%2Fdoubly-linked-list.png&w=1200&q=75)
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...
![Memory Layout](/_next/image?url=%2Fstatic%2Fimages%2Fdoubly-linked-list-memory-layout.png&w=1920&q=75)
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