 In this tutorial, you will learn about the doubly linke list and its implementation in Python, Java, C, and C++.

A doubly linked list is a type of linked list in which each node consists of 3 components:

• `*prev` - address of the previous node
• `data` - data item
• `*next` - address of next node

Note: Before you proceed further, make sure to learn about pointers and structs.

## Representation of Doubly Linked List

Let's see how we can represent a doubly linked list on an algorithm/code. Suppose we have a doubly linked list:

Here, the single node is represented as

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

Each struct node has a data item, a pointer to the previous struct node, and a pointer to the next struct node.

Now we will create a simple doubly linked list with three items to understand how this works.

``````/* Initialize nodes */
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Allocate memory */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;

/* Connect nodes */
one->next = two;
one->prev = NULL;

two->next = three;
two->prev = one;

three->next = NULL;
three->prev = two;

In the above code, `one`, `two`, and `three` are the nodes with data items 1, 2, and 3 respectively.

• For node one: `next` stores the address of `two` and `prev` stores `null` (there is no node before it)
• For node two: `next` stores the address of `three` and `prev` stores the address of `one`
• For node three: `next` stores `null` (there is no node after it) and `prev` stores the address of `two`.

Note: In the case of the head node, `prev` points to `null`, and in the case of the tail pointer, `next` points to null. Here, `one` is a head node and `three` is a tail node.

## Insertion on a Doubly Linked List

Pushing a node to a doubly-linked list is similar to pushing a node to a linked list, but extra work is required to handle the pointer to the previous node.

We can insert elements at 3 different positions of a doubly-linked list:

Suppose we have a double-linked list with elements 1, 2, and 3.

### 1. Insertion at the Beginning

Let's add a node with value 6 at the beginning of the doubly linked list we made above.

1. Create a new node

• allocate memory for `newNode`
• assign the data to `newNode`.

2. Set prev and next pointers of new node

• point `next` of `newNode` to the first node of the doubly linked list
• point `prev` to `null`

3. Make new node as head node

• Point `prev` of the first node to `newNode` (now the previous `head` is the second node)
• Point `head` to `newNode`

### Code for Insertion at the Beginning

``````// insert node at the front
void insertFront(struct Node** head, int data) {

// allocate memory for newNode
struct Node* newNode = new Node;

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

// point next of newNode to the first node of the doubly linked list

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

// point previous of the first node (now first node is the second node) to newNode

}``````

### 2. Insertion in between two nodes

Let's add a node with value 6 after node with value 1 in the doubly linked list.

1. Create a new node

• allocate memory for `newNode`
• assign the data to `newNode`.

2. Set the next pointer of new node and previous node

• assign the value of `next` from previous node to the `next` of `newNode`
• assign the address of `newNode` to the `next` of previous node

3. Set the prev pointer of new node and the next node

• assign the value of `prev` of next node to the `prev` of `newNode`
• assign the address of `newNode` to the `prev` of next node

The final doubly linked list is after this insertion is:

### Code for Insertion in between two Nodes

``````// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {

// check if previous node is NULL
if (prev_node == NULL) {
cout << "previous node cannot be NULL";
return;
}

// allocate memory for newNode
struct Node* newNode = new Node;

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

// set next of newNode to next of prev node
newNode->next = prev_node->next;

// set next of prev node to newNode
prev_node->next = newNode;

// set prev of newNode to the previous node
newNode->prev = prev_node;

// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}``````

### 3. Insertion at the End

Let's add a node with value 6 at the end of the doubly linked list.

1. Create a new node

2. Set prev and next pointers of new node and the previous node

If the linked list is empty, make the `newNode` as the head node. Otherwise, traverse to the end of the doubly linked list and

The final doubly linked list looks like this.

### Code for Insertion at the End

``````// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = new Node;

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

// assign NULL to next of newNode
newNode->next = NULL;

// store the head node temporarily (for later use)

// if the linked list is empty, make the newNode as head node
newNode->prev = NULL;
return;
}

// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;

// now, the last node of the linked list is temp

// point the next of the last node (temp) to newNode.
temp->next = newNode;

// assign prev of newNode to temp
newNode->prev = temp;
}``````

## Deletion from a Doubly Linked List

Similar to insertion, we can also delete a node from 3 different positions of a doubly linked list.

Suppose we have a double-linked list with elements 1, 2, and 3.

### 1. Delete the First Node of Doubly Linked List

If the node to be deleted (i.e. `del_node`) is at the beginning

Reset value node after the del_node (i.e. node two)

Finally, free the memory of `del_node`. And, the linked will look like this

Code for Deletion of the First Node

``````if (*head == del_node)

if (del_node->prev != NULL)
del_node->prev->next = del_node->next;

free(del);``````

### 2. Deletion of the Inner Node

If `del_node` is an inner node (second node), we must have to reset the value of `next` and `prev` of the nodes before and after the `del_node`.

For the node before the del_node (i.e. first node)

Assign the value of `next` of `del_node` to the `next` of the `first` node.

For the node after the del_node (i.e. third node)

Assign the value of `prev` of `del_node` to the `prev` of the `third` node.

Finally, we will free the memory of `del_node`. And, the final doubly linked list looks like this.

Code for Deletion of the Inner Node

``````if (del_node->next != NULL)
del_node->next->prev = del_node->prev;

if (del_node->prev != NULL)
del_node->prev->next = del_node->next;``````

### 3. Delete the Last Node of Doubly Linked List

In this case, we are deleting the last node with value 3 of the doubly linked list.

Here, we can simply delete the `del_node` and make the `next` of node before `del_node` point to `NULL`.

The final doubly linked list looks like this.

Code for Deletion of the Last Node

``````if (del_node->prev != NULL)
del_node->prev->next = del_node->next;``````

Here, `del_node ->next` is `NULL` so `del_node->prev->next = NULL`.

Note: We can also solve this using the first condition (for the node before `del_node`) of the second case (Delete the inner node).

## Doubly Linked List Code in Python, Java, C, and C++

``````import gc

# node creation

class Node:

def __init__(self, data):
self.data = data
self.next = None
self.prev = None

def __init__(self):

# insert node at the front
def insert_front(self, data):

# allocate memory for newNode and assign data to newNode
new_node = Node(data)

# make newNode as a head

# assign null to prev (prev is already none in the constructore)

# previous of head (now head is the second node) is newNode

# insert a node after a specific node
def insert_after(self, prev_node, data):

# check if previous node is null
if prev_node is None:
print("previous node cannot be null")
return

# allocate memory for newNode and assign data to newNode
new_node = Node(data)

# set next of newNode to next of prev node
new_node.next = prev_node.next

# set next of prev node to newNode
prev_node.next = new_node

# set prev of newNode to the previous node
new_node.prev = prev_node

# set prev of newNode's next to newNode
if new_node.next:
new_node.next.prev = new_node

# insert a newNode at the end of the list
def insert_end(self, data):

# allocate memory for newNode and assign data to newNode
new_node = Node(data)

# assign null to next of newNode (already done in constructor)

# if the linked list is empty, make the newNode as head node
return

# store the head node temporarily (for later use)

# if the linked list is not empty, traverse to the end of the linked list
while temp.next:
temp = temp.next

# now, the last node of the linked list is temp

# assign next of the last node (temp) to newNode
temp.next = new_node

# assign prev of newNode to temp
new_node.prev = temp

return

# delete a node from the doubly linked list
def deleteNode(self, dele):

# if head or del is null, deletion is not possible
if self.head is None or dele is None:
return

# if del_node is the head node, point the head pointer to the next of del_node

# if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if dele.next is not None:
dele.next.prev = dele.prev

# if del_node is not the first node, point the next of the previous node to the next node of del_node
if dele.prev is not None:
dele.prev.next = dele.next

# free the memory of del_node
gc.collect()

# print the doubly linked list
def display_list(self, node):

while node:
print(node.data, end="->")
last = node
node = node.next

# initialize an empty node

# insert 15 after the seond node

# delete the last node

print()
``````public class DoublyLinkedList {

// node creation

class Node {
int data;
Node prev;
Node next;

Node(int d) {
data = d;
}
}

// insert node at the front
public void insertFront(int data) {
// allocate memory for newNode and assign data to newNode
Node newNode = new Node(data);

// make newNode as a head

// assign null to prev of newNode
newNode.prev = null;

// previous of head (now head is the second node) is newNode

}

// insert a node after a specific node
public void insertAfter(Node prev_node, int data) {

// check if previous node is null
if (prev_node == null) {
System.out.println("previous node cannot be null");
return;
}

// allocate memory for newNode and assign data to newNode
Node new_node = new Node(data);

// set next of newNode to next of prev node
new_node.next = prev_node.next;

// set next of prev node to newNode
prev_node.next = new_node;

// set prev of newNode to the previous node
new_node.prev = prev_node;

// set prev of newNode's next to newNode
if (new_node.next != null)
new_node.next.prev = new_node;
}

// insert a newNode at the end of the list
void insertEnd(int data) {
// allocate memory for newNode and assign data to newNode
Node new_node = new Node(data);

// store the head node temporarily (for later use)

// assign null to next of newNode
new_node.next = null;

// if the linked list is empty, make the newNode as head node
new_node.prev = null;
return;
}

// if the linked list is not empty, traverse to the end of the linked list
while (temp.next != null)
temp = temp.next;

// assign next of the last node (temp) to newNode
temp.next = new_node;

// assign prev of newNode to temp
new_node.prev = temp;
}

// delete a node from the doubly linked list
void deleteNode(Node del_node) {

// if head or del is null, deletion is not possible
if (head == null || del_node == null) {
return;
}

// if del_node is the head node, point the head pointer to the next of del_node
}

// if del_node is not at the last node, point the prev of node next to del_node
// to the previous of del_node
if (del_node.next != null) {
del_node.next.prev = del_node.prev;
}

// if del_node is not the first node, point the next of the previous node to the
// next node of del_node
if (del_node.prev != null) {
del_node.prev.next = del_node.next;
}

}

// print the doubly linked list
public void printlist(Node node) {
Node last = null;
while (node != null) {
System.out.print(node.data + "->");
last = node;
node = node.next;
}
System.out.println();
}

public static void main(String[] args) {

doubly_ll.insertEnd(5);
doubly_ll.insertFront(1);
doubly_ll.insertFront(6);
doubly_ll.insertEnd(9);

// insert 15 after the seond node

// delete the last node

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

// node creation
struct Node {
int data;
struct Node* next;
struct Node* prev;
};

// insert node at the front
void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

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

// make newNode as a head

// assign null to prev
newNode->prev = NULL;

// previous of head (now head is the second node) is newNode

}

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
// check if previous node is null
if (prev_node == NULL) {
printf("previous node cannot be null");
return;
}

// allocate memory for newNode
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

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

// set next of newNode to next of prev node
newNode->next = prev_node->next;

// set next of prev node to newNode
prev_node->next = newNode;

// set prev of newNode to the previous node
newNode->prev = prev_node;

// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}

// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

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

// assign null to next of newNode
newNode->next = NULL;

// store the head node temporarily (for later use)

// if the linked list is empty, make the newNode as head node
newNode->prev = NULL;
return;
}

// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;

// now, the last node of the linked list is temp

// assign next of the last node (temp) to newNode
temp->next = newNode;

// assign prev of newNode to temp
newNode->prev = temp;
}

// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
// if head or del is null, deletion is not possible
if (*head == NULL || del_node == NULL)
return;

// if del_node is the head node, point the head pointer to the next of del_node

// if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;

// if del_node is not the first node, point the next of the previous node to the next node of del_node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;

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

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

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

int main() {
// initialize an empty node

// insert 15 after the seond node

// delete the last node

}``````
``````#include <iostream>
using namespace std;

// node creation
struct Node {
int data;
struct Node* next;
struct Node* prev;
};

// insert node at the front
void insertFront(struct Node** head, int data) {
// allocate memory for newNode
struct Node* newNode = new Node;

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

// make newNode as a head

// assign null to prev
newNode->prev = NULL;

// previous of head (now head is the second node) is newNode

}

// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data) {
// check if previous node is null
if (prev_node == NULL) {
cout << "previous node cannot be null";
return;
}

// allocate memory for newNode
struct Node* newNode = new Node;

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

// set next of newNode to next of prev node
newNode->next = prev_node->next;

// set next of prev node to newNode
prev_node->next = newNode;

// set prev of newNode to the previous node
newNode->prev = prev_node;

// set prev of newNode's next to newNode
if (newNode->next != NULL)
newNode->next->prev = newNode;
}

// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
// allocate memory for node
struct Node* newNode = new Node;

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

// assign null to next of newNode
newNode->next = NULL;

// store the head node temporarily (for later use)

// if the linked list is empty, make the newNode as head node
newNode->prev = NULL;
return;
}

// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;

// now, the last node of the linked list is temp

// assign next of the last node (temp) to newNode
temp->next = newNode;

// assign prev of newNode to temp
newNode->prev = temp;
}

// delete a node from the doubly linked list
void deleteNode(struct Node** head, struct Node* del_node) {
// if head or del is null, deletion is not possible
if (*head == NULL || del_node == NULL)
return;

// if del_node is the head node, point the head pointer to the next of del_node

// if del_node is not at the last node, point the prev of node next to del_node to the previous of del_node
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;

// if del_node is not the first node, point the next of the previous node to the next node of del_node
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;

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

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

while (node != NULL) {
cout << node->data << "->";
last = node;
node = node->next;
}
if (node == NULL)
cout << "NULL\n";
}

int main() {
// initialize an empty node

// insert 15 after the seond node

// delete the last node

}``````

 Doubly Linked List Complexity Time Complexity Space Complexity Insertion Operation O(1) or O(n) O(1) Deletion Operation O(1) O(1)

1. Complexity of Insertion Operation

• The insertion operations that do not require traversal have the time complexity of `O(1)`.
• And, insertion that requires traversal has time complexity of `O(n)`.
• The space complexity is `O(1)`.

2. Complexity of Deletion Operation

• All deletion operations run with time complexity of `O(1)`.
• And, the space complexity is `O(1)`.