Design a Doubly Linked List

Here we are opt to design a Doubly Linked List, basically designing a Data Structure. Unlike the Singly Linked List, the nodes in a Doubly Linked List has next and prev pointer. By using next pointer, Nodes are connected with it's Next Node and by using prev pointer Nodes are connected with it's Previous Node. In a Doubly Linked List, one can move forward from Head to Tail and also can move backward from Tail to Head.

A Doubly Linked List is ore like an Optimized version of Singly Linked List, we will see the usage of a Doubly Linked List in LRU Cache implementation shortly. Without further do, let's design a Doubly Linked List

Intuition

Imagine we already have a Doubly Linked List formed like this

The Head is connected to the Tail using next pointer and the Tail is connected to the Head using prev pointer like this bellow

Let's write the code for this above template.

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

class DoublyLinkedList:
	def __init__(self):
		self.size = 0
		# Dummy Head and Tail initialization
		self.head = Node(-1)
		self.tail = Node(-1)
		# Linking Dummy Head and Tail
		self.head.next = self.tail
		self.tail.prev = self.head

Now we are going to implement the features of the Linked List

Add at Head

This function will take an Integer number as create a new node with that value. Then it will add the new node after the Head

Suppose the new node is created with value 2 and linked with the Next and Previous nodes

def addAtHead(self, value: int):
	node = Node(val=value, prev=self.head, next=self.head.next)

Now the Head and Next Node of the Head needs to be linked with the newly created Node

def addAtHead(self, value: int):
	prevNode = self.head
	nextNode = self.head.next
	# connecting the new node with Head and it's Next Node
	node = Node(val=value, prev=prevNode, next=nextNode)
	# back connecting the Head and it's Next with the New Node
	prevNode.next = node
	nextNode.prev = node
	# increment the total count of nodes by one
	self.size += 1

Add at Tail

Now let's Add At Tail

def addAtTail(self, value: int):
	prevNode = self.tail.prev
	nextNode = self.tail
	# connecting the new node with Tail and it's Prev Node
	node = Node(val=value, prev=prevNode, next=nextNode)
	# back connecting the Tail and it's Prev node with the New Node
	prevNode.next = node
	nextNode.prev = node
	# increment the total count of nodes by one
	self.size += 1

If you look carefully, this code is similar to addAtHade function we have wrote earlier. The only change in prevNode and nextNode selection.
For addAtHead, the prevNode is the Head itself because we need to add a new node after the Head. On the other hand, for addAtTail, the nextNode is the Tail itself because the new node will be added before the Tail.

Insert into Linked List

So Let's write a common function for insertion

def insert(self, value: int, prevNode: Node, nextNode: Node):
	# connecting the new node with Tail and it's Prev Node
	node = Node(val=value, prev=prevNode, next=nextNode)
	# back connecting the Tail and it's Prev node with the New Node
	prevNode.next = node
	nextNode.prev = node
	# increment the total count of nodes by one
	self.size += 1

def addAtHead(self, value: int):
	self.insert(value=value, prevNode=self.head, nextNode=self.head.next)

def addAtTail(self, value: int):
	self.insert(value=value, prevNode=self.tail.prev, nextNode=self.tail)

Add at Index

This function takes Two Integer Parameters, one indicates the Index and another one is the integer value we have already seen. In this function we need to treat the Linked List like an Array where the First Node is at Index [0] and the last is at Index [size-1]. So if the given index=0 it means we need to add a new node after the Head by using addAtHead function and if the index=size that means we need to add a new node before the Tail by using addAtTail function.

def addAtIndex(self, index: int, value: int):
	# validating index
	if index > self.size:
		return
	if index == 0:
		self.addAtHead(value)
	elif index == size:
		self.addAtTail(value)
	else:
		# need to find the node before the given index

But when the index is in between 1 ... size-1 we need to Pick the previous node of that Index and Insert the new node using our insert function. Let's visualize and add a new node at index 1

To add a new node at Index 1, we need to use the node at Index 0 basically node before the given index. Let's write a helper function to find the node before the given index

def getNthNode(self, curr: Node, index: int) -> Optional[Node]:
	while curr and index > 0:
		curr = curr.next
		index -= 1
	return curr

Let's visualize the outcome of this function

If we start iterating from the Head we will find the node before the given index. Then we can insert the new node using the same insert function.

Let's code it up

def addAtIndex(self, index: int, value: int):
	# validating index
	if index > self.size:
		return
	if index == 0:
		self.addAtHead(value)
	elif index == size:
		self.addAtTail(value)
	else:
		# need to find the node before the given index
		beforeNthNode = self.getNthNode(self.head, index)
		self.insert(value, beforeNthNode, beforeNthNode.next)

The final outcome is

The new node [4] inserted at index 1. Now let's implement the get function.

Get Value by Index

This function takes index as parameter and return the node value. If there is no node found, return -1.
This function is pretty simple, we don't actually need to write much code for it, we will use getNthNode function for it. But instead of starting from the HEAD, we will place the curr pointer at the First Node which is next to HEAD. Let's find the value at index 2

Let's implement the get function

def get(self, index: int):
	firstNode = self.head.next
	node = self.getNthNode(firstNode, index)
	return node.val if node else -1

Delete Node at Index

This takes index as parameter and and Unlink the Nth Node. We will use getNthNode to find out the node to be deleted and unlink the node from the Linked List.
Let's Delete Node 4 which is at Index 1. To find it we need to call getNthNode(firstNode, index=1).

def deleteAtindex(index: int):
	if index > self.size - 1:
		return
	firstNode = self.head.next
	# find the Nth Node string from the firstNode
	nthNode = self.getNthNode(firstNode, index)
	# delete the nthNode

Now let's delete the node

Let's write a helper function for this

def deleteNode(nthNode: Node):
	prevNode = nthNode.prev
	nextNode = nthNode.next
	# Unlink the Nth Node
	prevNode.next = nextNode
	nextNode.prev = prevNode
	# decrement number of nodes by one
	size =- 1

def deleteAtindex(index: int):
	if index > self.size - 1:
		return
	firstNode = self.head.next
	# find the Nth Node string from the firstNode
	nthNode = self.getNthNode(firstNode, index)
	# delete the nthNode
	self.deleteNode(nthNode)

The outcome of this code is

That's it, Let's complete the whole code.

Complete Code Snippet

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

class DoublyLinkedList:
	def __init__(self):
		self.size = 0
		# Dummy Head and Tail initialization
		self.head = Node(-1)
		self.tail = Node(-1)
		# Linking Dummy Head and Tail
		self.head.next = self.tail
		self.tail.prev = self.head

	
	# Helper Function
	def getNthNode(self, curr: Node, index: int) -> Optional[Node]:
		while curr and index > 0:
			curr = curr.next
			index -= 1
		return curr
		

	def get(self, index: int) -> int:
		firstNode = self.head.next
		nthNode = self.getNthNode(firstNode, index)
		return nthNode.val if nthNode else -1

  
	# Helper Function
	def insertNode(self, value: int, prevNode: Node, nextNode: Node):
		newNode = Node(val=value, prev=prevNode, next=nextNode)
		prevNode.next = newNode
		nextNode.prev = newNode
		# increment node count by 1
		self.size += 1
		

	def addAtHead(self, value: int):
		# add node after the head node
		self.insertNode(value, prevNode=self.head, nextNode=self.head.next)

  
	def addAtTail(self, value: int):
		# add node before tail node	
		self.insertNode(value, prevNode=self.tail.prev, nextNode=self.tail)

  
	def addAtIndex(self, index: int, value: int):
		if index > self.size:
			return
		
		if index == 0:
			self.addAtHead(value)
		elif index == self.size:
			self.addAtTail(value)
		else:
			beforeNthNode = self.getNthNode(self.head, index)
			self.insertNode(
				value,
				prevNode=beforeNthNode,
				nextNode=beforeNthNode.next
			)

  
	# helper function
	def deleteNode(self, nthNode: Node):
		prevNode = nthNode.prev
		nextNode = nthNode.next
		# unlink the nth node from linked list
		prevNode.next = nextNode
		nextNode.prev = prevNode
		# decrement node count by 1
		self.size -= 1

  
	def deleteAtIndex(self, index: int):
		if index > self.size - 1:
			return
		nthNode = self.getNthNode(self.head.next, index)
		self.deleteNode(nthNode)

Thanks for Stopping by! Happy Leet coding

Connect with me on