Doubly Linked-List

This article assumes that you have already read Linked-List in C and does not provide much explanation.

Linked-List structure

A doubly linked-list is made up of a number of nodes, each node typically having two parts:

  • The data part that stores the actual data.
  • The link part that stores the address of the previous and next nodes in the linked-list.
struct Node {    int data;    struct Node *next;    struct Node *previous;};

In this example, our data is a normal C integer. However, your linked-list can store whatever type of data you want, depending on your implementation.

Now that we have our struct ready, let's initialize the head of the linked-list, a pointer that points to the first element in the linked-list.

struct Node *HEAD;

Cool. Now let's move on to the next part. That is, adding an item to our linked-list. Let us first try inserting an element in the linked-list.

Insertion

Insert At Beginning

void insert_at_beginning(int item) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item;    new_item->next = NULL;}

We have two cases when it comes to insertion at the beginning:

  1. The list is empty. In this case, we just place the element there and... the end.
if (HEAD == NULL) {    HEAD = new_item;}
  1. There is at least one element in the list. In this case, we are assigning our existing first item to a temporary variable and inserting our new item in that position instead.
if (HEAD == NULL) {    HEAD = new_item;} else {    struct Node *temp = HEAD;    HEAD = new_item;    HEAD->next = temp;    temp->previous = HEAD;}

The only change from our singly linked-list is the previous pointer to which we need to assign the previous element's pointer.

Our complete function looks like this:

void insert_at_beginning(int item_to_insert) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item_to_insert;    new_item->next = NULL;    // Assign `previous` as `NULL`    new_item->previous = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        HEAD = new_item;        HEAD->next = temp;        // Make former first node point to new node        temp->previous = HEAD;    }}

And that's it, for our insert_at_beginning().

Insert At End

Inserting at the end of a doubly linked-list has one extra step compared to the singly linked-list:

  • Assigning the predecessor's address to the previous field of our new node.

Our complete function looks like this:

void insert_at_end(int item_to_insert) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item_to_insert;    new_item->next = NULL;    new_item->previous = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        while (temp->next != NULL) {            temp = temp->next;        }        temp->next = new_item;        // Assign former last node as `previous`        new_item->previous = temp;    }}

Insert At Custom Position

Unlike the singly-linked list, we now have to consider both the node's successor and the predecessor. The predecessor should have its next pointer point to our new node. The successor should have its previous pointer point to our new node.

Our complete function looks like this:

void insert_at_custom(int item_to_insert, int position) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item_to_insert;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    }    struct Node *temp = HEAD;    int i = 0;     while (i < position && temp->next != NULL) {            temp = temp->next;            i += 1;    }    new_item->next = temp->next;    temp->next = new_item;        // New node's successor's `previous` should point to new node.    new_item->next->previous = new_item;    // New node's `previous` should point to predecessor.    new_item->previous = temp;}

Deletion

Let's go through different cases we could have for deletion.

Deletion From End

Deletion from the end in a doubly linked-list is no different from a singly linked-list because the previous pointer of the last node just does not matter.

void delete_from_end() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        while (temp->next->next != NULL) {            temp = temp->next;        }        struct Node *last = temp->next;        temp->next = NULL;        free(last);    }}

Deletion From Beginning

Deletion from the beginning has one small change compared to the singly linked-list.

HEAD = HEAD->next;// Make the `previous` pointer point to NULLHEAD->previous = NULL;

Our complete function looks like this:

void delete_from_beginning() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        HEAD = HEAD->next;        // Make the `previous` pointer point to NULL        HEAD->previous = NULL;        free(temp);    }}

Deletion From Custom Position

The only change from the singly linked-list version is that we need to make the deleted node's successor's previous pointer point to the deleted node's predecessor.

Our complete function looks like this:

void delete_from_custom(int position) {    if (HEAD == NULL)        return;    struct Node *temp = HEAD;    int i = 0;    while (i < position - 1 && temp->next->next != NULL) {        temp = temp->next;        i += 1;    }    struct Node *last = temp->next;    temp->next = last->next;    // Make the deleted node's successor point to its predecessor    temp->next->previous = temp;    free(last);}

The working is the same as delete_from_end() except that we modify the connections in a different way.

What We Have Now

#include <stdlib.h>struct Node {    int data;    struct Node *next;    struct Node *previous;};struct Node *HEAD;void insert_at_end(int item_to_insert) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item_to_insert;    new_item->next = NULL;    new_item->previous = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        while (temp->next != NULL) {            temp = temp->next;        }        temp->next = new_item;        new_item->previous = temp;    }}void insert_at_beginning(int item_to_insert) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item_to_insert;    new_item->next = NULL;    new_item->previous = NULL;    if (HEAD == NULL) {        HEAD = new_item;    } else {        struct Node *temp = HEAD;        HEAD = new_item;        HEAD->next = temp;        temp->previous = HEAD;    }}void insert_at_custom(int item_to_insert, int position) {    struct Node *new_item = (struct Node *)malloc(sizeof(struct Node));    new_item->data = item_to_insert;    new_item->next = NULL;    if (HEAD == NULL) {        HEAD = new_item;    }    struct Node *temp = HEAD;    int i = 0;     while (i < position && temp->next != NULL) {            temp = temp->next;            i += 1;    }    new_item->next = temp->next;    temp->next = new_item;    new_item->next->previous = new_item;    new_item->previous = temp;}void delete_from_end() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        while (temp->next->next != NULL) {            temp = temp->next;        }        struct Node *last = temp->next;        temp->next = NULL;        free(last);    }}void delete_beginning() {    if (HEAD == NULL)        return;    else {        struct Node *temp = HEAD;        HEAD = HEAD->next;        HEAD->previous = NULL;        free(temp);    }}void delete_custom(int position) {    if (HEAD == NULL)        return;    struct Node *temp = HEAD;    int i = 0;    while (i < position - 1 && temp->next->next != NULL) {        temp = temp->next;        i += 1;    }    struct Node *last = temp->next;    temp->next = last->next;    temp->next->previous = temp;    free(last);}

See Also

Table of Contents