## Introduction to Doubly Linked Lists

Linked lists are one of the essential data structures in computer science. They are used to store collections of elements like a list of names or a list of scores in a game.

There are different types of linked lists, and one of the most useful is the doubly linked list. A doubly linked list is a type of linked list where each node has two references: one to the next node and one to the previous node.

The two references allow you to traverse the list in both directions, unlike a singly linked list, which only has a reference to the next node. The first node of a doubly linked list is called the head, and the last node is called the tail.

Doubly linked lists have numerous advantages over singly linked lists. They allow you to traverse the list in both directions, making it easier to navigate the list and perform operations like searching for a specific element.

Additionally, they allow you to delete a node from the list more efficiently than a singly linked list.

## Creating a Doubly Linked List Class

To illustrate the implementation of a doubly linked list, let’s look at the process of creating a DoublyLinkedList class in Python.

## Updating Node Creation Function

The first step in creating our doubly linked list class is to update the node creation function. We need to add a reference to the previous node to our createNode function.

## Here is how we can update the function:

“`

## class Node:

def __init__(self, value=None):

self.value = value

self.next = None

self.prev = None

def createNode(value):

newNode = Node(value)

return newNode

“`

## Creating DoublyLinkedList Class

Now that we have updated the Node class, we can create our DoublyLinkedList class. Here is how we can define the class:

“`

## class DoublyLinkedList:

def __init__(self):

self.head = None

self.tail = None

self.length = 0

“`

The constructor initializes three variables: head, tail, and length.

Head and tail are initialized to None, and length is set to 0.

Let’s look at some of the essential functions we can implement in our DoublyLinkedList class.

## Adding Elements to the List

To add an element to our doubly linked list, we need to create a new node and add it to the end of the list. Here is the code to add a node:

“`

def addNode(self, value):

newNode = createNode(value)

if self.head == None:

self.head = newNode

self.tail = newNode

else:

self.tail.next = newNode

newNode.prev = self.tail

self.tail = newNode

self.length += 1

“`

In this function, we first create a new node using the createNode function we defined earlier.

Next, we check if the head is None. If it is, we set the head and tail to the new node.

Otherwise, we make the next reference of the current tail node point to the new node. We also update the prev reference of the new node to point to the current tail node, and finally, we update the tail to point to the new node.

## Deleting Elements from the List

To delete an element from our list, we need to first search for the node with the value we want to delete and then remove it from the list. Here is the code to delete a node:

“`

def deleteNode(self, value):

currentNode = self.head

found = False

while currentNode != None and not found:

if currentNode.value == value:

found = True

else:

currentNode = currentNode.next

if not found:

return None

if currentNode.prev == None:

self.head = currentNode.next

else:

currentNode.prev.next = currentNode.next

if currentNode.next == None:

self.tail = currentNode.prev

else:

currentNode.next.prev = currentNode.prev

self.length -= 1

“`

In this function, we first traverse the list until we find the node with the specified value.

We then update the next and prev references of the neighboring nodes to bypass the node we want to delete. We also update the head and tail references if we delete the first or last node.

## Conclusion

In this article, we explored the basics of doubly linked lists and how to create a DoublyLinkedList class. We learned that doubly linked lists are a more versatile type of linked list than singly linked lists.

We also learned how to add and delete elements from a doubly linked list. By understanding these concepts, you can start using doubly linked lists in your projects to solve more complex problems.

## Adding Insert Method to the Doubly Linked List

The ability to insert a node at any position within the list is a crucial feature of a data structure, and doubly linked lists are no exception. In this section, we will add an insert method to our DoublyLinkedList class.

## Code for Insert Method

The insert method takes two arguments: the value to insert, and the position within the list where we want to insert it. Here is the code to add the insert method:

“`

def insert(self, position, value):

if position < 0 or position > self.length:

raise IndexError(“Position out of range”)

newNode = createNode(value)

if self.length == 0:

self.head = newNode

self.tail = newNode

elif position == 0:

newNode.next = self.head

self.head.prev = newNode

self.head = newNode

elif position == self.length:

newNode.prev = self.tail

self.tail.next = newNode

self.tail = newNode

else:

currentNode = self.head

for i in range(position-1):

currentNode = currentNode.next

newNode.next = currentNode.next

newNode.prev = currentNode

currentNode.next.prev = newNode

currentNode.next = newNode

self.length += 1

“`

In this function, we first check whether the position argument is within the current range of the list.

If it is not, we raise an IndexError. We then create a new node using createNode function.

Next, we need to consider four cases:

1. The list is empty: In this case, we make the head and tail pointers point to the new node and then increase the length of the list.

2. The position is 0: In this case, we update the next reference of the new node to point to the current head node and update the prev reference of the current head node to point to the new node.

Finally, we update the head reference to point to the new node and increase the length of the list. 3.

The position is equal to the length of the list: In this case, we update the prev reference of the new node to point to the current tail node and update the next reference of the current tail node to point to the new node. Finally, we update the tail reference to point to the new node and increase the length of the list.

4. The position is somewhere in the middle of the list: In this case, we traverse the list until we find the node that is currently at the specified position, and then update the next and prev pointers of the neighboring nodes to include the new node.

## Inserting Nodes into the List

Now that we have our insert method, let’s see how we can use it to add nodes to our list. Here’s an example:

“`

dLinkedList = DoublyLinkedList()

dLinkedList.addNode(1)

dLinkedList.addNode(2)

dLinkedList.addNode(4)

dLinkedList.insert(2, 3)

print(dLinkedList.printList()) # Output: 1, 2, 3, 4

“`

In this example, we first create a new DoublyLinkedList object, and then add three nodes with values 1, 2, and 4 to the list using the addNode method.

We then insert a new node with a value of 3 at position 2 using the insert method, which shifts the node with a value of 4 to the next position. Finally, we print the contents of the list using the printList method, which we will define in the next section.

## Adding Print Method to the Doubly Linked List

To verify that our list is functioning correctly, we need to be able to print its contents. In this section, we will define a printList method that will print the values of each node in the list.

## Code for Print Method

Here’s the code for the printList method:

“`

def printList(self):

if self.head == None:

return “”

currentNode = self.head

lst = str(currentNode.value)

while currentNode.next != None:

currentNode = currentNode.next

lst += “, ” + str(currentNode.value)

return lst

“`

In this function, we first check if the head node is None. If it is, we return an empty string to indicate that the list is empty.

If the head is not None, we create a new currentNode variable that initially points to the head node. We then create a new string variable called lst that will hold the string representation of the list.

We start by adding the value of the current node to lst, and then traverse the list using the next reference of each node until we reach the end of the list. At each node, we append the value of the node to lst, separated by a comma and a space.

Finally, we return the list as a string.

## Testing the List Implementation

Now that we have our printList method, we can use it to verify that our list is functioning correctly. Here’s an example:

“`

dLinkedList = DoublyLinkedList()

dLinkedList.addNode(1)

dLinkedList.addNode(2)

dLinkedList.addNode(4)

dLinkedList.insert(2, 3)

print(dLinkedList.printList()) # Output: 1, 2, 3, 4

“`

In this example, we create a new DoublyLinkedList object and add four nodes with values 1, 2, 4, and 3 using the addNode and insert methods.

We then print the contents of the list using the printList method, which should output “1, 2, 3, 4”. This output confirms that our list is functioning correctly.

## Conclusion

In this article, we learned how to add an insert method and a printList method to our DoublyLinkedList class. We also saw how we could use these methods to add and print the contents of a doubly linked list.

These new features make our DoublyLinkedList class more flexible and easier to use.

## Adding Remove Method to the Doubly Linked List

In addition to inserting nodes, it’s essential to be able to remove nodes from a doubly linked list. In this section, we’ll add a remove method to our DoublyLinkedList class.

## Code for Remove Method

The remove method takes one argument: the value of the node we want to remove. If the node isn’t found in the list, the method raises a ValueError.

Here’s the code for the remove method:

“`

def remove(self, value):

if self.length == 0:

raise ValueError(“List is empty”)

currentNode = self.head

while currentNode != None and currentNode.value != value:

currentNode = currentNode.next

if currentNode == None:

raise ValueError(“Node not found in list”)

if currentNode == self.head:

self.head = currentNode.next

if self.head != None:

self.head.prev = None

else:

self.tail = None

elif currentNode == self.tail:

self.tail = self.tail.prev

self.tail.next = None

else:

currentNode.prev.next = currentNode.next

currentNode.next.prev = currentNode.prev

self.length -= 1

“`

In this function, we first check if the list is empty. If it is, we raise a ValueError.

Otherwise, we start at the head and traverse the list until we find the node with the specified value. If the node we want to remove is the head of the list, we update the head reference to point to the next node, and update its prev pointer to be None.

If there is no next node after the former head node, then we have removed the node at the tail of the list and so we need to update our tail reference to reflect this change.

If the node we want to remove is the tail of the list, we update the tail reference to point to the previous node, and update its next pointer to be None.

If the node we want to remove is neither the head or tail, we update the next reference of the previous node to point to the next node and the prev reference of the next node to point to the previous node.

## Removing Nodes from the List

Here’s an example that shows how we can use the remove method to remove a node from our list:

“`

dLinkedList = DoublyLinkedList()

dLinkedList.addNode(1)

dLinkedList.addNode(2)

dLinkedList.addNode(3)

dLinkedList.remove(2)

print(dLinkedList.printList()) # Output: 1, 3

“`

In this example, we create a new DoublyLinkedList object and add three nodes with values 1, 2, and 3 using the addNode method. We then remove the node with a value of 2 using the remove method and print the contents of the list using the printList method, which should output “1, 3”.

This output confirms that our remove method is functioning correctly.

## Inserting and Removing a Node from the Head

In addition to adding and removing nodes from different positions in the list, it’s also helpful to have functions that add and remove nodes from the head of the list. In this section, we’ll add an insertHead method and a removeHead method to our DoublyLinkedList class.

## Code for InsertHead Method

Here’s the code for the insertHead method:

“`

def insertHead(self, value):

newNode = createNode(value)

if self.length == 0:

self.head = newNode

self.tail = newNode

else:

newNode.next = self.head

self.head.prev = newNode

self.head = newNode

self.length += 1

“`

In this function, we first create a new node using the createNode function. If the length of the list is 0, we update the head and tail references to point to the new node.

Otherwise, we update the next reference of the new node to point to the current head node, update the prev reference of the current head node to point to the new node, and update the head reference to point to the new node. Finally, we increase the length of the list.

## Code for RemoveHead Method

Here’s the code for the removeHead method:

“`

def removeHead(self):

if self.length == 0:

raise ValueError(“List is empty”)

removedHead = self.head

if self.length == 1:

self.head = None

self.tail = None

else:

self.head = self.head.next

self.head.prev = None

self.length -= 1

return removedHead.value

“`

In this function, we first check if the list is empty. If it is, we raise a ValueError.

Next, we create a removedHead variable that points to the current head of the list. If the length of the list is 1, we update both the head and tail references to None.

Otherwise, we update the head reference to point to the next node and update its prev pointer to None. We then decrease the length of the list and return the value of the removed node.

## Conclusion

In this article, we learned how to add a remove method that allowed us to remove nodes from our doubly linked list. We saw how the remove method needed to be implemented differently depending on whether the node was at the head or tail of the list.

We also added an insertHead method and a removeHead method, which allowed us to add and remove nodes from the head of the list. These new features make our DoublyLinkedList class even more flexible and efficient.

## Inserting and Removing a Node at a Specific Index

In addition to inserting nodes at the head or tail of the list, we may also need to insert or remove a node at a specific position in the list. In this section, we’ll add an insertIndex method and a