Everything you Need to Know about Doubly Linked Lists

Like an array, a linked list is a linear data structure. This means that data elements are arranged in a way that one element is directly linked to its previous and next elements. There are different types of linked lists suited for different situations in software development; in this article we'll look at doubly-linked lists, their capabilites, and when you should use them.

What is a linked list?

A linked list is a linear data structure in which data is not stored in adjacent memory locations. A node in a linked list has a data segment and a pointer pointing to the memory location of the next element; this continues until we get to the end of the list.

You can learn more on the linked list here.

What is a doubly linked list?

A doubly linked list is a variation of a linked list where each node of the linked list contains three separate parts:

• A pointer to the previous node.
• The data on the current node.
• A pointer to the next node in the list.

Above is an example of a node in a doubly linked list.You can see how the differences in the nodes for a doubly linked list change the flow of data in the following diagram:

Pros and cons of using a doubly linked list

Here are some advantages of a doubly linked list:

• Allows us to traverse in both directions, moving data forward and backwards.
• It's easier to reverse a doubly linked list.
• Inserting a new node is quicker.
• Useful in implementing different data structures.

Here are some disadvantages of using a doubly linked list:

• Consumes extra memory due to the extra pointer.
• For actions like insertion, both the previous pointer and the next pointer must be modified.

Operations on doubly linked list

In this section, we'll be looking at operations that are used to manipulate doubly linked lists.

Creating

Before learning how to manipulate a doubly linked list, it’s important to first understand its creation. Below is the code for a creating the struct of a single node in a doubly linked list in C:

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

typedef struct node;

Here you can see that each node contains a variable to store an integer, a second variable to store the address of the next node, and a third variable to store the address of the previous node.

Now that the struct is declared, let's create our doubly linked list of nodes:

/* creating our nodes */
node *head;
node *first = NULL;
node *second = NULL;
node *third = NULL;

/* Allocate memory */
first = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));

/* store address of the first node in head */
head = first;

/* Assign data values */
first->data = 75;
second->data = 85;
third->data = 100;

/* linking our nodes */
first->next = two;
first->prev = NULL;
second->next = three;
second->prev = one;
third->next = NULL;
third->prev = two;

Save to Pieces

Inserting a node

Two of the advantages of using a linked list instead of an array is the list’s ability to change size and how easy it is to insert new nodes. In this section, we'll look at how to add a new node into our list. Since there are different locations where nodes can be inserted, we will look at each case individually to understand them all well.

Inserting a new node at the beginning

To insert a node at the beginning of our doubly linked list we'll first have to create it and give it some value to store as data:

/* creating new node*/
node *new_node = NULL;

/* Allocating memory for new node */
new_node = malloc(sizeof(struct node));

/* assigning data */
new_node->data = 105;

To insert our newly created node at the beginning, we'll have to set the prev pointer of the new node to null and then set the next pointer of the new node to the first node in the list.

new_node->prev = NULL;
new_node->next = first;

Now that there is a new node at the beginning of the list, set the prev pointer of the first node so that it points to the new node that was just created, and then set the head equal to the new node.

first->prev = new_node;
head = new_node;

The following function can be used to insert a new node at the beginning of a doubly linked list:

void insert_at_beginning(node** head, int data)
{
  // allocate memory for new_node
  node* new_node = NULL;
  new_node = malloc(sizeof(struct node));

  // assign data to newNode
  new_node->data = data;

  // point next of new_node to the first node of the doubly linked list
  new_node->next = (*head);

  // point prev to NULL
  new_node->prev = NULL;

  // point previous of the first node (now the first node is the second node) to new_node
  if ((*head) != NULL)
  (*head)->prev = new_node;

  // head points to newNode
  (*head) = new_node;
}

Save to Pieces

Inserting in between two nodes

To insert a node in between two nodes of our doubly linked list, we'll have to create the node before we place it:

node *new_node = NULL;

/* Allocating memory for new node */
new_node = malloc(sizeof(struct node));

/* assigning data */
new_node->data = 124;

We will then traverse through the list until we get to where we want to insert the new node. In the example below, we want to place our new node after the third node on the list.

node *temp;
temp = *head;

for (i = 0; i < 1; i++)
  {
    temp = temp->next;
    if(temp == NULL)
      return;
  }

After traversing down the list, the temp pointer refers to the second node with an index of one (1). Now we'll make the next pointer of the new node point to the third node. We can access the next node via temp->next.

new_node->next = temp->next;

We'll then set the prev pointer of our new node point to the second node, which is referenced by temp:

new_node->prev = temp;

Our new node now points to the third and fourth nodes. Now let's make the next pointer of our third node point to our new node and the prev pointer of our third node point to our new node.

temp->next = new_node;
temp->next->prev = new_node;

Temp refers to the second node while temp->next->prev refers to the prev pointer of the third node. With this done we have successfully inserted our new node in the second and third nodes of our list.

Here's the function for adding a new node at a specified position in a doubly linked list:

void insertMid(node **head, int data)
{
  // allocate memory for the new node
  node *new_node, *temp;
  int i;

  new_node = malloc(sizeof(node));
  new_node->data = data;

  // traversing through the list
  temp = *head;
  for (i = 0; i < 2; i++)
  {
    temp = temp->next;
    if(temp == NULL)
      return;
  }

  // inserting our new node
  new_node->next = temp->next;
  new_node->prev = temp;
  temp->next = new_node;
  temp->next->prev = new_node;
}

Save to Pieces

Inserting a new node at the end of the list

To insert our node at the end of our list, we'll first have to create it:

node *new_node = NULL;

/* Allocating memory for new node */
new_node = malloc(sizeof(struct node));

/* assigning data */
new_node->data = 136;

We'll then traverse down the list till we get to the end of the list:

node *temp;
temp = *head;

while (temp->next != NULL)
{
  temp = temp->next;
}

The temp variable now refers to the last node. Now let's make the next pointer of the last node point to our new_node instead of null:

temp->next = new_node;

Let's make the next pointer of our new node point to null and the prev pointer point to the last node:

new_node->prev = temp;
new_node->next = NULL;

With all of those steps completed, we have successfully added our new node to the end of our list. Here's what an entire function for adding a new node to the end of a doubly linked list would look like:

void insertAtEnd(node **head, int data)
{
  node *new_node, *temp, *buf;
  new_node = malloc(sizeof(node));
  new_node->data = data;
  temp = *head;
  while (temp->next != NULL)
  {
    temp = temp->next;
  }

  temp->next = new_node;
  new_node->prev = temp;
  new_node->next = NULL;
}

Save to Pieces

Updating a node

With our list created, let's look at how we update a specific node located inside of a doubly linked list. In the example below we'll be editing the 3rd node with an index of 2 in our list.

First, we'll traverse down the list to the third node that we would like to update:

node *temp;
temp = *head;
for (i = 0; i < 2; i++)
{
  temp = temp->next;
  if(temp == NULL)
     return;
}

Now, all we have to do is declare temp->data and set a specific value:

temp->next = 36;

Here's what the function for updating a node to the end of a doubly linked list would look like:

void updateNode(node **head, int data)
{
  node *temp, *buf;
  int i;
  temp = *head;

  for (i = 0; i < 2; i++)
  {
    temp = temp->next;
    if(temp == NULL)
      return;
  }

  temp->data = data;
}

Save to Pieces

Deleting a node

To delete a node after a specified node in our list, we'll first create a temp node for traversing down the list until we get to our node:

node *temp;
temp = *head;

Now we'll traverse down the list.

while(temp->data != val)
temp = temp->next;

This sets temp to the node before the node we intend to delete. Now we'll create a new pointer and point to the node we intend to delete:

node *ptr;
ptr = temp->next;

With this completed, the pointer now refers to the node that will be deleted. Now we'll make the next pointer of the specified node point to the node after the node we intend to delete:

temp->next = ptr->next;

To completely disconnect the node that we’re deleting from our list, we'll set the prev node of the pointer after the one we want to delete to the specified node:

ptr->next->prev = temp;

With everything completed, the ptr has been disconnected from our list and all we need to do is release the memory that was allocated to ptr.

free(ptr);

Here's the entire function for deleting a node to the end of a doubly linked list. It can be used regardless of the list’s length:

void deleteNode(node **head)
{
  node *ptr, *temp, *buf;

  int val;
  temp = *head;
  val = 75;

  while(temp -> data != val)
    temp = temp->next;
    ptr = temp->next;
    temp->next = ptr->next;
    ptr->next->prev = temp;

  free(ptr);
}

Save to Pieces

In the function above, we deleted the node directly after the node with a value of 75.

Reversing a doubly linked list

To reverse a doubly linked list, we'll start by taking the two pointers:

node *temp, *buf;

Now let buf point to NULL while temp points to our head pointer:

buf = NULL;
temp = *head;

In a loop using both pointers, swap the next and previous pointer for all nodes of the doubly linked list:

while (temp != NULL)
{
  buf = temp->prev;
  temp->prev = temp->next;
  temp->next = buf;
  temp = temp->prev;
}

Save to Pieces

With these done, our previous and next pointers has been swapped. Now we'll set the head pointer to the last node of the list.

With all these done, here's the output of all of our operations.

You can get the code for all our functions from the repo.

Time complexities for operations with doubly linked lists

• Operations without traversal has a time complexity of O(1). (Inserting at the beginning of the list.)
• Operations that involve traversal that requires traversal has a time complexity of O(n). (Deleting and updating nodes other than the first, reversing the list.)

Applications of doubly linked lists

• Redo and undo functionality in software.
• Implementation of stacks and queues.
• Forward and backward navigation in browsers.
• Navigation systems where forward and backward navigation is required.

Conclusion

In this article, we looked at doubly linked lists and the different operations we can carry out on a doubly linked list to modify, create, and remove nodes to efficiently work with the data moving through them. Happy coding!

Resources

Code repo

Linked list