# Data Structures in Python: Doubly Linked list

First of all, if you haven’t read my linked list tutorial you must and then read this.

From our linked list tutorial you know a linked list is a collection of nodes and each node contains data and the address of the next node. But in a doubly-linked list, each node contains the address of the previous node also instead of just storing the address of the next node.

# Overview of Node

In the above figure, you can see node of doubly linked list in which we have prev, data and next and prev pointing towards previous node and next pointing towards next node.

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

# Overview of Doubly Linked list

In the above figure, you can see a pictorial representation of a doubly linked list where each node is connected to the previous and next node through the prev and the next link.

Prev of the head node is None as no node exists before the head node and next of the last node is none.

`class LinkedList:    def __init__(self):        self.head = None`

# Traversing

We already did traversing in the singly linked list tutorial but in a doubly-linked list instead of just traversing forward, we can also traverse backward as we have links to previous nodes.

Forward traversing as done in our singly linked list tutorial in the __repr__ method

`class LinkedList:    def __init__(self):        self.head = None    def __repr__(self):        if self.head is None:            return "Empty Linked List"        itr = self.head        listr = ''        while itr:            if itr.next == None:                listr += str(itr.data)                break            listr += str(itr.data) + '->'            itr = itr.next            return listr`

For reverse traversing, we will first create the get_last_node method to search for the last node

`class LinkedList:    def __init__(self):        self.head = None    def __repr__(self):        if self.head is None:            return "Empty Linked List"        itr = self.head        listr = ''        while itr:            if itr.next == None:                listr += str(itr.data)                break            listr += str(itr.data) + '->'            itr = itr.next            return listr    def get_last_node(self):        itr = self.head        while itr:            if itr.next == None:                return itr            itr = itr.next`

Now we will traverse backward using the last node

`class LinkedList:    def __init__(self):        self.head = None    def __repr__(self):        if self.head is None:            return "Empty Linked List"        itr = self.head        listr = ''        while itr:            if itr.next == None:                listr += str(itr.data)                break            listr += str(itr.data) + '->'            itr = itr.next            return listr    def get_last_node(self):            itr = self.head        while itr:            if itr.next == None:                return itr            itr = itr.next    def traverse_backward(self):        if self.head is None:            return "Empty Linked List"        itr = self.get_last_node()        listr = ''        while itr:            if itr.prev == None:                listr += str(itr.data)                break            listr += str(itr.data) + '->'            itr = itr.prev        return listr`

In the traverse_backward method, we fetched the last node and then using the prev link we iterated until the prev is none.

You must have understood these codes easily if you have read the linked list tutorial. Implementation is almost the same as before.

Now I want you to implement the insertion and deletion methods of the doubly linked list and add the comment with your solution. You can take the help of our singly linked list tutorial where I showed how to implement these in a singly linked list.

All the very best!!!

--

--