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

Representation of a node in Doubly Linked list

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

Representation 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!!!

Lectures

Lecture 1: https://medium.com/@saifmdco/data-structures-with-python-introduction-4dadeffa2215

Lecture 2: https://medium.com/@saifmdco/data-structures-with-python-arrays-c498518bf7fd

Lecture 3: https://medium.com/@saifmdco/data-structures-in-python-lists-653a3ad103ab

Lecture 4: https://medium.com/@saifmdco/data-structures-in-python-tuples-3c350640cd9a

Lecture 5: https://medium.com/@saifmdco/data-structures-in-python-dictionary-fad27ffdda8b

Lecture 6: https://medium.com/@saifmdco/data-structures-in-python-2d-array-6bc0154aa717

Lecture 7: https://medium.com/@saifmdco/data-structures-in-python-matrix-22adba5aa597

Lecture 8: https://medium.com/@saifmdco/data-structures-in-python-sets-92d5445e97e8

Lecture 9: https://medium.com/@saifmdco/data-structures-in-python-chainmap-fca2a9d47249

Lecture 10: https://medium.com/@saifmdco/data-structures-in-python-linkedlist-50f2118c659e

Lecture 11: https://medium.com/@saifmdco/data-structures-in-python-stack-6bf182d63581

Lecture 12: https://medium.com/@saifmdco/data-structures-in-python-queue-6361d3dcff0

Lecture 13: https://medium.com/@saifmdco/data-structures-in-python-dequeue-1a585e269a55

Lecture 14: https://medium.com/@saifmdco/data-structures-in-python-custom-stack-b7b9173b4eae

Lecture 15: https://medium.com/@saifmdco/data-structures-in-python-hash-table-39be784eefc1

Lecture 16: https://medium.com/@saifmdco/data-structures-in-python-doubly-linked-list-fe698d74756c

Lecture 17: https://medium.com/@saifmdco/data-structures-in-python-tree-410255b87107

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store