Doubly Linked Lists in C, Java and Python

In a singly linked list, we can only move forward from any node. For example, if we are at node b, as shown in the picture given below, we can’t access the node previous to it.

con of singly linked list

This problem can easily be fixed by using one extra link for each node which will point to the previous node.

doubly linked list

This is called doubly linked list.

As you can see in the above picture, prev of the head and next of the tail point to null. So, let’s make the node for a doubly linked list.

C
Python
Java

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

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

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

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

public Node(int data) {
  this.data = data;
  next = null;
  prev = null;
}
}

You can see that we have used two pointers next and prev to make a node instead of just using next as we did in the singly linked list.

Let’s write the functions of inserting and deleting a node in a doubly linked list.

Inserting New Node

Similar to singly linked lists, we can have three cases:

Inserting a new node at the front of the doubly linked list.
Inserting a new node at the end of the doubly linked list.
Inserting a new node after any node in the doubly linked list.

Let’s start by writing the code to insert a new node at the front of the linked list.

Inserting a New Node at the Front

We will start with a function and pass the linked list and the node to be inserted to it - INSERT_AT_FRONT(L, n).

Our first task is to point next of the new node (n) to the head of the linked list i.e., n.next = L.head.

adding node at front of doubly linked list

Then, we will point prev of the head to the new node - L.head.prev = n.

adding node at front of doubly linked list

At last, we will just make the new node head of the linked list.

L.head = n

INSERT_AT_FRONT(L, n)
  n.next = L.head
  L.head.prev = n
  L.head = n

Inserting a New Node at the End

To insert a new node at the tail, we will first iterate to the last node.

INSERT_AT_TAIL(L, n)
  tmp = L.head
  while(tmp.next != null)
      tmp = tmp.next
  ...

iterating to the last of doubly linked list

Now, we will point next of tmp to n and prev of n to tmp.

adding node at end of doubly linked list

INSERT_AT_TAIL(L, n)
  tmp = L.head
  while(tmp.next != null)
      tmp = tmp.next
tmp.next = n
n.prev = tmp

Thus, we can insert a new node at the start and the end of a doubly linked list. Let’s learn to add a node after any given node.

Inserting a New Node After Any Node

Our function will take the node which we are going to insert (n) and the node after which we are going to insert it (a) - INSERT_AFTER(n, a).

Firstly, we will link the new node n and a.next.

adding node in middle of doubly linked list

n.next = a.next a.next.prev = n

After this, we will link a to n.

adding node in middle of doubly linked list

a.next = n n.prev = a

INSERT_AFTER(n, a)
  n.next = a.next
  a.next.prev = n
  a.next = n
  n.prev = a

Our next task is to delete a node from a given linked list.

Deleting a Node

Till now, you must have got an idea that deleting a node from a doubly linked list is also similar to a singly linked list. We link the node previous to the node to be deleted to the next of it.

deleting node in doubly linked list

So, let’s write the code to do it. We will start making a function and then pass the node to be deleted and the linked list- DELETE_NODE(L, a).

We will first check if the node a is head or not. We can do it easily by checking if the prev pointer of the node is null or not because prev of the head is always null. If the node is not head, then we will point next pointer of the node previous to a to the next of a.

adding middle node in doubly linked list

if a.prev != null // node is not head a.prev.next = a.next

If the node a is head, then we will mark the node next to a as the head of the linked list.

deleting head in doubly linked list

else // node a is head L.head = a.next

At last, we will point the prev pointer of the node next to a to the node previous of a.

deleting node in doubly linked list

We will do this if the node a is not the last node.

if a.next != null a.next.prev = a.prev

DELETE_NODE(L, a)
  if a.prev != null // node is not head
      a.prev.next = a.next
  else // node a is head
      L.head = a.next

  if a.next != null
      a.next.prev = a.prev

C
Python
Java

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

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

typedef struct linked_list {
struct node *head;
}linked_list;

//to make new node
node* new_node(int data) {
node *z;
z = malloc(sizeof(struct node));
z->data = data;
z->next = NULL;
z->prev = NULL;

return z;
}

//to make a new linked list
linked_list* new_linked_list(int data) {
node *a; //new node for head of linked list
a = new_node(data);

linked_list *l = malloc(sizeof(linked_list)); //linked list
l->head = a;

return l;
}

void traversal(linked_list *l) {
node *temp = l->head; //temporary pointer to point to head

while(temp != NULL) { //iterating over linked list
  printf("%d\t", temp->data);
  temp = temp->next;
}

printf("\n");
}

//new node before head
void insert_at_front(linked_list *l, node *n) {
n->next = l->head;
l->head->prev = n;
l->head = n;
}

//insert new node at last
void insert_at_tail(linked_list *l, node *n) {
node *temp = l->head;

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

temp->next = n;
n->prev = temp;
}

//function to insert a node after a node
void insert_after(node *n, node *a) {
n->next = a->next;
a->next->prev = n;
a->next = n;
n->prev = a;
}

//function to delete
void del(linked_list *l, node *a) {
if(a->prev != NULL) { //node is not head
  a->prev->next = a->next;
}
else { //node a is head
  l->head = a->next;
}

if(a->next != NULL) {
  a->next->prev = a->prev;
}
free(a);
}

int main() {
linked_list *l = new_linked_list(10);

node *a, *b, *c; //new nodes to insert in linekd list
a = new_node(20);
b = new_node(50);
c = new_node(60);

//connecting to linked list
/*
   ----     ----     ----     ----
  |head|-->| a  |-->|  b |-->|  c |-->NULL
  |____|   |____|   |____|   |____|
*/
l->head->next = a;
a->next = b;
b->next = c;

traversal(l);

node *z;

z = new_node(0);
insert_at_front(l, z);
z = new_node(-10);
insert_at_front(l, z);

z = new_node(100);
insert_at_tail(l, z);

z = new_node(30);
insert_after(z, a);
z = new_node(40);
insert_after(z, a->next);
z = new_node(500);
insert_after(z, a->next->next);

traversal(l);

del(l, l->head);
del(l, z);
traversal(l);

return 0;
}

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

class LinkedList():
def __init__(self, data):
  a = Node(data)
  self.head = a

def traversal(l):
temp = l.head #temporary pointer to point to head

a = ''
while temp != None: #iterating over linked list
  a = a+str(temp.data)+'\t'
  temp = temp.next

print(a)

def insert_at_front(l, n):
n.next = l.head
l.head.prev = n
l.head = n

def insert_at_tail(l, n):
temp = l.head

while temp.next != None:
  temp = temp.next

temp.next = n
n.prev = temp

def insert_after(n, a):
n.next = a.next
a.next.prev = n
a.next = n
n.prev = a

def delete(l, a):
if a.prev != None: #node is not head
  a.prev.next = a.next
else: #node a is head
  l.head = a.next

if a.next != None:
  a.next.prev = a.prev
del a

if __name__ == '__main__':
l = LinkedList(10)

a = Node(20)
b = Node(50)
c = Node(60)

#connecting to linked list
'''
   ----     ----     ----     ----
  |head|-->| a  |-->|  b |-->|  c |-->NULL
  |____|   |____|   |____|   |____|
'''

l.head.next = a
a.next = b
b.next = c

traversal(l)

z = Node(0)
insert_at_front(l, z)
z = Node(-10)
insert_at_front(l, z)

z = Node(100)
insert_at_tail(l, z)

z = Node(30)
insert_after(z, a)
z = Node(40)
insert_after(z, a.next)
z = Node(500)
insert_after(z, a.next.next)

traversal(l)

delete(l, l.head)
delete(l, z)

traversal(l)

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

public Node(int data) {
  this.data = data;
  next = null;
  prev = null;
}
}

class LinkedList {
public Node head;

public LinkedList(int data) {
  Node a = new Node(data);
  head = a;
}

public void traversal() {
  Node temp = head; //temporary pointer to point to head

  while(temp != null) { //iterating over linked list
    System.out.print(temp.data+"\t");
    temp = temp.next;
  }

  System.out.println("");
}

//new node before head
public void insertAtFront(Node n) {
  n.next = head;
  head.prev = n;
  head = n;
}

//insert new node at last
public void insertAtTail(Node n) {
  Node temp = head;

  while(temp.next != null) {
    temp = temp.next;
  }

  temp.next = n;
  n.prev = temp;
}

//function to insert a node after a node
public void insertAfter(Node n, Node a) {
  n.next = a.next;
  a.next.prev = n;
  a.next = n;
  n.prev = a;
}

//function to delete
public void del(Node a) {
  if(a.prev != null) { //node is not head
    a.prev.next = a.next;
  }
  else { //node a is head
    head = a.next;
  }

  if(a.next != null) {
    a.next.prev = a.prev;
  }
}
}

class ListMain {
public static void main(String[] args) {
  LinkedList l = new LinkedList(10);

  Node a,b,c;
  a = new Node(20);
  b = new Node(50);
  c = new Node(60);

  //connecting to linked list
  /*
     ----     ----     ----     ----
    |head|-->| a  |-->|  b |-->|  c |-->NULL
    |____|   |____|   |____|   |____|
  */

  l.head.next = a;
  a.next = b;
  b.next = c;

  l.traversal();

  Node z;

  z = new Node(0);
  l.insertAtFront(z);
  z = new Node(-10);
  l.insertAtFront(z);

  z = new Node(100);
  l.insertAtTail(z);

  z = new Node(30);
  l.insertAfter(z, a);
  z = new Node(40);
  l.insertAfter(z, a.next);
  z = new Node(500);
  l.insertAfter(z, a.next.next);

  l.traversal();

  l.del(l.head);
  l.del(z);

  l.traversal();
}
}

So, we have discussed both singly and doubly linked lists. There must be one question in your mind i.e., what are the pros and cons of both linked lists? So, let’s compare both and find out.

Singly Linked List v/s Doubly Linked List

Doubly Linked List requires extra space as compared to Singly Linked List because it stores one extra pointer i.e., the previous node of each node.
We don’t need to store the head pointer in a doubly linked list because we can access each node if we have access to any node of the doubly linked list.
Doubly Linked List requires more memory but searching for an element in a doubly linked list is comparatively efficient than a singly linked list because we can iterate in both directions.
Deletion and Insertion tasks are relatively complex in a doubly linked list and more efficient in a singly linked list.

In conclusion, we should use a singly linked list when we have limited memory and searching for elements is not our priority. However, when the limitation of memory is not a problem and insertion and deletion task doesn’t happen frequently, we should move with the doubly linked list.

In the next chapter, we are going to discuss another linked list which is circular linked list. So, let’s move ahead and learn about it.

Science is a beautiful gift to humanity; we should not distort it.

- A. P. J. Abdul Kalam