DEV Community

Doubly Linked List

This is how it is different than singly linked list
Singly Linked List
Image description

Doubly Linked List
Image description

So, when creating a node in Singly Linked List, we had this:

Image description
We actually had

Image description
Which we wrote in class as this:

BImage description
But the doubly Linked List, we will have :

Image description

Now, lets create Doubly Linked List class
Image description
We will create the Doubly Linked List calling the class:

Image description
This makes a doubly Linked List:

Image description

the whole code:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

#Creating a doubly Linked List which has a node 7
my_doubly_linked_list = DoublyLinkedList(7)

#Printing the list
my_doubly_linked_list.print_list()

Enter fullscreen mode Exit fullscreen mode

Append
Case 1:
When there is no value and adding one

Image description

and make this to this

Image description
We will first check if head is point to None:

Image description
Will make it

Image description

Image description
Case 2:

Image description
Now we will code this to append a new node

Image description

Image description

Image description
So, the total code is:

Image description
The total code:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

#A linked list of a node 1
my_doubly_linked_list = DoublyLinkedList(1)
#Appending node 2
my_doubly_linked_list.append(2)

my_doubly_linked_list.print_list()


Enter fullscreen mode Exit fullscreen mode

Pop

Case 1:
If the List has 0 nodes

Image description
For this , we will have:
Because we won't return anything
Image description

Case 2: If we have more than 2 value

Image description
First we will create a temp variable

Image description
Then we will set tail to the previous node:

Image description
Then we will set the tail's next direction to None to break if from the last item:

Image description
same for the last node:

Image description

Case 3:
When we have just 1 value:
Image description

We will pop it and also set the head and tail to None:

Image description

The list will be something like this:

Image description

So, the code will look like this:
Image description

Also , we can change it to this format:
Image description
Total code:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        #For 0 items in list
        if self.length == 0:
            return None
        temp = self.tail
        #For 1 items in list
        if self.length == 1:
            self.head = None
            self.tail = None 
        #For more than 1 nodes in list
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

#Creates a list of Node 1 & Node 2

my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(2)


# (2) Items - Returns  Node 2
print(my_doubly_linked_list.pop())
# (1) Item -  Returns  Node 1
print(my_doubly_linked_list.pop())
# (0) Items - Returns  None
print(my_doubly_linked_list.pop())


Enter fullscreen mode Exit fullscreen mode

Prepend

Case: 1
When we have nothing in the list

Image description
So, we will set the head & tail to it:

Image description
Case 2:
if we have more than 1 values:

Image description
We will first do this:

Image description
then

Image description
then

Image description

Total code becomes:

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        # If we have no value in the list
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        #If we have more than 1 values
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

#Doubly list with Node 1 & Node 3
my_doubly_linked_list = DoublyLinkedList(2)
my_doubly_linked_list.append(3)

#Prepending Node 1
my_doubly_linked_list.prepend(1)

my_doubly_linked_list.print_list()
Enter fullscreen mode Exit fullscreen mode

Get
For the Singly Linked List we had this code right:
Image description

Image description

We will then turn this to this

Image description

Case 1:
Let's return something that is within the Doubly Linked List. Let's return index 1

Image description
If the index is in 1st half

Image description
if on 2nd half

SImage description
setting tail as temp and iterate backward

Image description
and return the temp when we get that

So, the total code will be

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        #Checking if the index is in 1st half
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        #Checking if the index is in 2nd half
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp #Will return the node . But for value, use temp.value

#Creating a doubly list of 0,5,9,3
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(5)
my_doubly_linked_list.append(9)
my_doubly_linked_list.append(3)


#Lokking for index 1 no node
print(my_doubly_linked_list.get(1))

#Looking for index 2 no node
print(my_doubly_linked_list.get(2))

Enter fullscreen mode Exit fullscreen mode

Set
Let's set this index 1 value from 3 to 4.

Image description

Image description
so,here we are going to check if the index is within range and if so, then we will change the value

Image description
else will return False

The whole code is

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        #if the index is within the range
        if temp:
            temp.value = value
            return True
        #if the index is not within range    
        return False

#Doubly linked list of 11,3,23,7  
my_doubly_linked_list = DoublyLinkedList(11)
my_doubly_linked_list.append(3)
my_doubly_linked_list.append(23)
my_doubly_linked_list.append(7)


#setting index value to 4

my_doubly_linked_list.set_value(1,4)

my_doubly_linked_list.print_list()

Enter fullscreen mode Exit fullscreen mode

Insert

At a particular index, we are going to insert a node.
Firstly, we are going to check if the index is within the range

Image description

Case 1:
If needs to add it at the beginning

Image description

Case 2:
Adding it to the last of the list

Image description

case 3:
Adding in somewhere middle.
Assume that we want to make this
Image description

to that

Image description

so, trying to insert the node between 1 & 2.
So, we will set index 1 to before and index 2 to after

Image description

Image description

We are going to make this

Image description
to this

Image description

Image description

Image description

Image description

Image description

So, the code is

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def insert(self, index, value):
        #to check if the index is within range
        if index < 0 or index > self.length:
            return False
        #to add a node at the start
        if index == 0:
            return self.prepend(value)
        #to add a node at the end    
        if index == self.length:
            return self.append(value)
        #to add a node within the list
        new_node = Node(value)
        before = self.get(index - 1)
        after = before.next

        new_node.prev = before
        new_node.next = after
        before.next = new_node
        after.prev = new_node

        self.length += 1   
        return True  


#Doubly linked list of nodes 1 ,3
my_doubly_linked_list = DoublyLinkedList(1)
my_doubly_linked_list.append(3)



#at the index 1, adding node 2
my_doubly_linked_list.insert(1,2)

my_doubly_linked_list.print_list()

Enter fullscreen mode Exit fullscreen mode

Remove

Checking if the index is out of range

Image description
Case 1:
Returning the first item.

Image description
this to this

Image description
For this, we will just pop

Image description
Case 2:
To remove from last.

Image description
Case 3:
To remove something from middle

Image description
For example, we will remove the index 2 number value. Firstly, pointing a variable to it

Image description

Image description
Which can be something like this

Image description

Image description

Image description

Image description
using

Image description

Total code will be

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


class DoublyLinkedList:
    def __init__(self, value):
        new_node = Node(value)
        self.head = new_node
        self.tail = new_node
        self.length = 1

    def print_list(self):
        temp = self.head
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self.length += 1
        return True

    def pop(self):
        if self.length == 0:
            return None
        temp = self.tail
        if self.length == 1:
            self.head = None
            self.tail = None 
        else:       
            self.tail = self.tail.prev
            self.tail.next = None
            temp.prev = None
        self.length -= 1
        return temp

    def prepend(self, value):
        new_node = Node(value)
        if self.length == 0:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.length += 1
        return True

    def pop_first(self):
        if self.length == 0:
            return None
        temp = self.head
        if self.length == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            self.head.prev = None
            temp.next = None      
        self.length -= 1
        return temp

    def get(self, index):
        if index < 0 or index >= self.length:
            return None
        temp = self.head
        if index < self.length/2:
            for _ in range(index):
                temp = temp.next
        else:
            temp = self.tail
            for _ in range(self.length - 1, index, -1):
                temp = temp.prev  
        return temp

    def set_value(self, index, value):
        temp = self.get(index)
        if temp:
            temp.value = value
            return True
        return False

    def insert(self, index, value):
        if index < 0 or index > self.length:
            return False
        if index == 0:
            return self.prepend(value)
        if index == self.length:
            return self.append(value)

        new_node = Node(value)
        before = self.get(index - 1)
        after = before.next

        new_node.prev = before
        new_node.next = after
        before.next = new_node
        after.prev = new_node

        self.length += 1   
        return True  

    def remove(self, index):
        #Checking the range
        if index < 0 or index >= self.length:
            return None
        #to remove from the beginning    
        if index == 0:
            return self.pop_first()
        #to remove from the last    
        if index == self.length - 1:
            return self.pop()

        #to remove from the middle of the doubly linked list
        temp = self.get(index)

        temp.next.prev = temp.prev
        temp.prev.next = temp.next
        temp.next = None
        temp.prev = None

        self.length -= 1
        return temp

# a doubly linked list of 0,1 & 2 nodes
my_doubly_linked_list = DoublyLinkedList(0)
my_doubly_linked_list.append(1)
my_doubly_linked_list.append(2)


# removing index 1 out of the list
print(my_doubly_linked_list.remove(1), '\n')

my_doubly_linked_list.print_list()
Enter fullscreen mode Exit fullscreen mode

Done!

Discussion (0)