Doubly Linked Lists

5 mins read1.1K Views Comment

Updated on Mar 23, 2022 10:57 IST

The Doubly Linked Lists, as the name suggests, are two-way linked lists containing pointers to the previous and the next node in the sequence. It is one of the most complex types of Linked Lists used by most crowds. In this article, let us understand the depths of Doubly Linked Lists in the following order:

What is Doubly Linked List
Representation of a Doubly Linked List
Doubly Linked List Operations
Doubly Linked List in C
Doubly Liked List in Python
Doubly Linked List Complexity

What is Doubly Linked List

The Doubly Linked Lists are one of the most complex data structures that offer two-way traversal. These linked lists contain pointers to the previous and the next node in the sequence.

A few of the most popular applications of Doubly Linked Lists are:

All navigation applications and systems which have forward/backward navigation
Undo/Redo functionality software
Categorize least used/most used cache
Thread schedulers in many operating systems
Represent the card decks in games

Representation of Doubly Linked Lists

A linked list is a chain of nodes, and each node has the following parts:

Data Item
Address to the previous node
Address to the next node

Node is represented in the C programming language as follows:

struct node

{

int d;

struct node *n;

struct node *p;

};

Node is represented in Python programming language as follows:

class Node:

def __init__(self, d):

self.d = d

self.n = None

self.p = None

Doubly Linked List Operations

Traversal

Traversal refers to accessing elements in the list and displaying them as output.

To traverse through the list, you have to keep moving the temp node to the next node until the temp is NULL. As soon as temp = NULL, it implies that you have reached the end of the list

Insertion

There are three ways to insert elements in Doubly Linked Lists.

Note: For all the types of insertion, you have to allocate memory and store data for new node

Insert at the beginning
- Initially, point the next of new node to the 1st node and point the previous to NULL
- Now, point the previous of the 1st node to new node. Here, you will observe that the previous head is the 2nd node.
- Finally, point the head to the new node

Insert after a node
- Give the value of next from the previous node to the next of new node
- Point the address of the new node to the next of previous node
- Give the value of previous of the next node to the previous of new node
- Point the address of the new node to the previous of next node

Insert at the end
- If the list is empty, make the new node as HEAD.
- Else traverse to the end of the list and insert the element.

Deletion

There are 3 ways to delete elements in Doubly Linked Lists. To delete from the beginning, you have to point the head to the second element

To delete

Delete at Beginning

Before an element, you have to assign the value of the key element to the next of 1st node.

Delete after a node

After a key element, you have to assign the value of the previous of key element to the previous of the next element. Then, free the memory of key element

Delete the last node

To delete the last node you have to go to the last value and delete it. Post which, mark the next of the last but one node point to NULL.

Doubly Linked Lists in C

Refer to the following code to understand how to create a Doubly Linked Lists and perform various operations in C.

#include <stdio.h>
#include <stdlib.h>

struct node {
  int d;
  struct node* n;
  struct node* p;
};

//Insert at Beginning
void InserBeg(struct node** head, int d) {
  struct node* newnode = (struct node*)malloc(sizeof(struct node));

  newnode->d = d;
  newnode->n = (*head);
  newnode->p = NULL;
  if ((*head) != NULL)
    (*head)->p = newnode;
  (*head) = newnode;
}

// Insert after a node
void InserAf(struct node* p_node, int d) {
  if (p_node == NULL) {
    printf("The previous node must not be NULL");
    return;
  }
  struct node* newnode = (struct node*)malloc(sizeof(struct node));
  
  newnode->d = d;
  newnode->n = p_node->n;
  p_node->n = newnode;
  newnode->p = p_node;
  if (newnode->n != NULL)
    newnode->n->p = newnode;
}

// Insert at the end
void InserEnd(struct node** head, int d) {
  struct node* newnode = (struct node*)malloc(sizeof(struct node));
  
  newnode->d = d;

  // assign null to n of newnode
  newnode->n = NULL;
  struct node* temp = *head;
  if (*head == NULL) {
    newnode->p = NULL;
    *head = newnode;
    return;
  }
  while (temp->n != NULL)
    temp = temp->n;
  temp->n = newnode;
  newnode->p = temp;
}

//Delete Node
void DelNode(struct node** head, struct node* key) {
  if (*head == NULL || key == NULL)
    return;
  if (*head == key)
    *head = key->n;
  if (key->n != NULL)
    key->n->p = key->p;
  if (key->p != NULL)
    key->p->n = key->n;

  // free the memory of key
  free(key);
}

// print the doubly linked list
void DisplayList(struct node* node) {
  struct node* last;

  while (node != NULL) {
    printf("%d ", node->d);
    last = node;
    node = node->n;
  }
  if (node == NULL)
    printf("NULL\n");
}

int main() {
  struct node* head = NULL;
  //Insert elements
  InserEnd(&head, 42);
  InserBeg(&head, 31);
  InserBeg(&head, 62);
  InserEnd(&head, 12);
  InserEnd(&head, 85);
  InserAf(head, 10);
  
  printf("Linked List after inserting elements :\n");
  DisplayList(head);

  //Delete Elements
  DelNode(&head, head->n->n);
  printf("\nLinked List after deleting the 3rd element :\n ");
  DisplayList(head);
}
[/code]
Output:
IMAGE
Doubly Linked List in Python
Refer to the following code to understand how to create a Doubly Linked Lists and perform various operations in Python.
[/code]
import gc

class Node:

    def __init__(self, d):
        self.d = d
        self.n = None
        self.p = None


class DoublyLL:

    def __init__(self):
        self.head = None
        
        # print the doubly linked list
    def DisplayList(self, node):

        while node:
            print(node.d, end=" ")
            last = node
            node = node.n

    # insert node at the front
    def InserBeg(self, d):

        node1 = Node(d)
        node1.n = self.head

        if self.head is not None:
            self.head.p = node1

        self.head = node1

    # insert a node after a particular node
    def InserAf(self, p_node, d):

        if p_node is None:
            print("pious node cannot be null")
            return
        
        node1 = Node(d)
        node1.n = p_node.n
        p_node.n = node1
        node1.p = p_node

        if node1.n:
            node1.n.p = node1

    # insert a newNode at the end of the list
    def InserEnd(self, d):

        node1 = Node(d)
        if self.head is None:
            self.head = node1
            return

        temp = self.head
        while temp.n:
            temp = temp.n
        temp.n = node1
        node1.p = temp

        return

    #Deletion 
    def DelNode(self, key):

        if self.head is None or key is None:
            return

       # Delete first node
        if self.head == key:
            self.head = key.n
        if key.n is not None:
            key.n.p = key.p
        if key.p is not None:
            key.p.n = key.n

# free the memory
        gc.collect()

# initialize an empty node
D_ll = DoublyLL()
    #Insert elements
D_ll.InserEnd(42)
D_ll.InserBeg(31)
D_ll.InserBeg(62)
D_ll.InserEnd(12)
D_ll.InserEnd(85)
D_ll.InserAf(D_ll.head, 10)

print('Linked List after inserting elements :')

D_ll.DisplayList(D_ll.head)

#Delete elements
D_ll.DelNode(D_ll.head)
D_ll.DelNode(D_ll.head.n)
print()
print("\nLinked List after deleting elements : ")
D_ll.DisplayList(D_ll.head)
Copy code

Output:

Doubly Linked List in Python

Refer to the following code to understand how to create a Doubly Linked Lists and perform various operations in Python.

import gc

class Node:

    def __init__(self, d):
        self.d = d
        self.n = None
        self.p = None


class DoublyLL:

    def __init__(self):
        self.head = None
        
        # print the doubly linked list
    def DisplayList(self, node):

        while node:
            print(node.d, end=" ")
            last = node
            node = node.n

    # insert node at the front
    def InserBeg(self, d):

        node1 = Node(d)
        node1.n = self.head

        if self.head is not None:
            self.head.p = node1

        self.head = node1

    # insert a node after a particular node
    def InserAf(self, p_node, d):

        if p_node is None:
            print("pious node cannot be null")
            return
        
        node1 = Node(d)
        node1.n = p_node.n
        p_node.n = node1
        node1.p = p_node

        if node1.n:
            node1.n.p = node1

    # insert a newNode at the end of the list
    def InserEnd(self, d):

        node1 = Node(d)
        if self.head is None:
            self.head = node1
            return

        temp = self.head
        while temp.n:
            temp = temp.n
        temp.n = node1
        node1.p = temp

        return

    #Deletion 
    def DelNode(self, key):

        if self.head is None or key is None:
            return

       # Delete first node
        if self.head == key:
            self.head = key.n
        if key.n is not None:
            key.n.p = key.p
        if key.p is not None:
            key.p.n = key.n

# free the memory
        gc.collect()

# initialize an empty node
D_ll = DoublyLL()
    #Insert elements
D_ll.InserEnd(42)
D_ll.InserBeg(31)
D_ll.InserBeg(62)
D_ll.InserEnd(12)
D_ll.InserEnd(85)
D_ll.InserAf(D_ll.head, 10)

print('Linked List after inserting elements :')

D_ll.DisplayList(D_ll.head)

#Delete elements
D_ll.DelNode(D_ll.head)
D_ll.DelNode(D_ll.head.n)
print()
print("\nLinked List after deleting elements : ")
D_ll.DisplayList(D_ll.head)
Copy code

Output:

Doubly Linked List Complexity

Operation	Time Complexity	Space Complexity
Insertion with Traversal	O(n)	O(1)
Insertion without Traversal	O(1)	O(1)
Deletion	O(1)	O(1)

With this, we end this article on Doubly Linked Lists and how to implement it. We hope you found it informative.

Recently completed any professional course/certification from the market? Tell us what liked or disliked in the course for more curated content.
Click here to submit its review with Shiksha Online.

Download this article as PDF to read offline

Download as PDF

About the Author

Shiksha Online

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio