Traversing Doubly-Linked Lists in C

Introduction

So we've taken a brief look at singly-linked lists and how to implement them, but there are a few downsides when it comes to the direction we can move through our list.

Doubly-linked lists allow us to keep track of both the next and the previous node, which can come in handy in deleting nodes from our list.

The obvious drawback is extra memory usage for storing that additional 'previous' pointer, so whether you should use them depends purely on the task.

Here's a rundown of doubly-linked lists in C.

Moving Backwards

As you can tell, our struct definition for a node looks nearly identical, except for that one extra pointer to the previous node.

typedef struct node
{
	int data;
	struct node *prev;
	struct node *next;
}

Really, doubly-linked lists operate almost identically to their single counter parts, except for a few operations including inserting and deleting singular nodes.

Inserting

Because insertion usually happens at the beginning of the list (since we know the header pointer), we have to readjust not only the header pointer, but also the previous pointer of the old header to point to the new header.

In the image below, we've malloc( )'ed space for the new node, but currently it's not connected to our list.

Keep in mind that the upper square is our previous node, the middle is our data, and the bottom is our next.

Just like with singly-linked lists, it was important that we filled the new node's fields with data and addresses before changing the header pointer to the new node, so as to not alienate the rest of the list.

*Also, the first node's previous field should point to NULL.

In code:

node *node1 = malloc(sizeof(node));
if (node1 == NULL)
	return 1;

// assume we header is a pointer to 
// the old first node

node1->data = 2;

node1->next = header;
node1->prev = NULL;

// assuming header doesn't point to NULL
header->prev = node1;
header = node1;

Deleting

Here's where doubly-linked lists shine.

With singly-linked lists, even though we had the address of the pointer we wanted to delete, we still had to traverse the list just to find the previous node (because we need to link its next field to the node after the one we're deleting).

This is obviously inefficient because it takes linear time.

With doubly-linked lists, we already have access to the previous node, so it's much more efficient.

This delete function, while taking away some of the complexity of corner cases, shows a simple way to delete any element from the middle of a doubly-linked lists.

void delete(node* target)
{
	// assuming target, header pointer aren't NULL 
	// assuming target is not header or last node
	target->prev->next = target->next;
	target->next->prev = target->prev;
	
	free(target);
}

Final Thoughts

So, the moral of the story is, if you need to delete lots of elements, doubly-linked lists are probably your best bet. Thanks for reading!