Open In App

Doubly Linked List in Python

Last Updated : 03 Jun, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Doubly Linked List is a type of linked list in which each node contains a data element and two links pointing to the next and previous node in the sequence. This allows for more efficient operations such as traversals, insertions, and deletions because it can be done in both directions.

Doubly-Linked-List-in-Python

Table of Content

What is a Doubly Linked List?

Doubly Linked List (DLL) is a special type of linked list in which each node contains a pointer to the previous node as well as the next node of the linked list. In a Doubly Linked List, we can traverse in forward and backward direction using the next and previous pointer respectively.

Representation of Doubly Linked List in Python:

Here is the representation of the doubly linked list in python:

Python 
# Node of a doubly linked list
class Node:
    def __init__(self, next=None, prev=None, data=None):
        # reference to next node in DLL
        self.next = next
        # reference to previous node in DLL
        self.prev = prev
        self.data = data

Traversal of Doubly Linked List in Python:

To traverse a doubly linked list in Python, you can simply start from the head of the list and iterate through each node, printing its data.

Below is the implementation of the above idea:

Python 
# Python Program for traversal of a doubly linked list
class Node:
    def __init__(self, data):
        # Initialize a new node with data, previous, and next pointers
        self.data = data
        self.next = None
        self.prev = None


def traverse(head):
    # Traverse the doubly linked list and print its elements
    current = head
    while current:
      # Print current node's data
        print(current.data, end=" <-> ")
        # Move to the next node
        current = current.next
    print("None")


def insert_at_beginning(head, data):
    # Insert a new node at the beginning of the doubly linked list
    new_node = Node(data)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node


# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)

# To traverse and print the nodes:
traverse(head)

Output
1 <-> 2 <-> 3 <-> 4 <-> None

Insertion of Doubly Linked List in Python:

Inserting a new node in a doubly linked list is very similar to inserting new node in linked list. There is a little extra work required to maintain the link of the previous node. A node can be inserted in a Doubly Linked List in five ways:

  • At the front of the DLL.
  • After a given node.
  • Before a given node.
  • At the end of the DLL.

1. Insertion at the Beginning:

To insert a node at the beginning of a doubly linked list in Python, you need to follow these steps:

  • Create a new node with the given data.
  • Set the “next” pointer of the new node to point to the current head (if any).
  • Set the “previous” pointer of the new node to None (as it will become the new head).
  • If the list is not empty, update the “previous” pointer of the current head to point to the new node.
  • Update the head of the list to point to the new node.

Below is the implementation of the above idea:

Python 
# Python Program for a doubly linked list at the beginning of a node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

# Function to insert a node at the beginning of a doubly linked list
def insert_at_beginning(head, data):
    new_node = Node(data)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node

# Function to display the elements of the doubly linked list
def display(head):
    current = head
    while current:
        print(current.data, end=" <-> ")
        current = current.next
    print("None")


# Driver Code
head = None
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)

print("Doubly Linked List after insertion at the beginning:")
display(head)

Output
Doubly Linked List after insertion at the beginning:
1 <-> 2 <-> 3 <-> None

2. Insertion after a given node:

To insert a node after a given node in a doubly linked list in Python, you can follow these steps:

  • Create a new node with the given data.
  • Set the “next” pointer of the new node to point to the next node of the given node.
  • Set the “previous” pointer of the new node to point to the given node.
  • If the next node of the given node is not None, update the “previous” pointer of that node to point to the new node.
  • Update the “next” pointer of the given node to point to the new node.

Below is the implementation of the above idea:

Python 
# Python Program for Insertion after a given node 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

# Function to insert a node after a given node in a doubly linked list
def insert_after_node(node, data):
    if node is None:
        print("Error: The given node is None")
        return

    new_node = Node(data)
    new_node.prev = node
    new_node.next = node.next

    if node.next:
        node.next.prev = new_node

    node.next = new_node

# Function to display the elements of the doubly linked list
def display(head):
    current = head
    while current:
        print(current.data, end=" <-> ")
        current = current.next
    print("None")


# Driver Code
head = Node(1)
node2 = Node(2)
node3 = Node(3)

head.next = node2
node2.prev = head
node2.next = node3
node3.prev = node2

print("Doubly Linked List before insertion:")
display(head)

insert_after_node(node2, 4)

print("Doubly Linked List after insertion:")
display(head)

Output
Doubly Linked List before insertion:
1 <-> 2 <-> 3 <-> None
Doubly Linked List after insertion:
1 <-> 2 <-> 4 <-> 3 <-> None

3. Insertion before a given node:

To insert a node before a given node in a doubly linked list in Python, you can follow these steps:

  • Create a new node with the given data.
  • Set the “next” pointer of the new node to point to the given node.
  • Set the “previous” pointer of the new node to point to the previous node of the given node.
  • If the previous node of the given node is not None, update the “next” pointer of that node to point to the new node.
  • Update the “previous” pointer of the given node to point to the new node.

Below is the implementation of the above idea:

Python 
# Python Program for Insertion before a given node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

# Function to insert a node before a given node in a doubly linked list
def insert_before_node(node, data):
    if node is None:
        print("Error: The given node is None")
        return

    new_node = Node(data)
    new_node.prev = node.prev
    new_node.next = node

    if node.prev:
        node.prev.next = new_node

    node.prev = new_node

# Function to display the elements of the doubly linked list
def display(head):
    current = head
    while current:
        print(current.data, end=" <-> ")
        current = current.next
    print("None")

# Driver Code
head = Node(1)
node2 = Node(2)
node3 = Node(3)

head.next = node2
node2.prev = head
node2.next = node3
node3.prev = node2

print("Doubly Linked List before insertion:")
display(head)

insert_before_node(node2, 4)

print("Doubly Linked List after insertion:")
display(head)

Output
Doubly Linked List before insertion:
1 <-> 2 <-> 3 <-> None
Doubly Linked List after insertion:
1 <-> 4 <-> 2 <-> 3 <-> None

4. Insertion at the end:

To insert a node at the end of a doubly linked list in Python, you need to follow these steps:

  • Create a new node with the given data.
  • If the list is empty (head is None), make the new node the head of the list.
  • Otherwise, traverse the list to find the last node.
  • Set the “next” pointer of the last node to point to the new node.
  • Set the “previous” pointer of the new node to point to the last node.
  • Optionally, update the head of the list to point to the new node if it’s the first node in the list.

Below is the implementation of the above idea:

Python 
# Python Program for Insertion at the end
class Node:
    def __init__(self, data):
        # Initialize a new node with data, previous, and next pointers
        self.data = data
        self.next = None
        self.prev = None


def insert_at_end(head, data):
    # Insert a new node at the end of the doubly linked list
    new_node = Node(data)
    if head is None:
        return new_node

    current = head
    while current.next:
        current = current.next

    current.next = new_node
    new_node.prev = current
    return head


def display(head):
    # Display the doubly linked list elements
    current = head
    while current:
      # Print current node's data
        print(current.data, end=" <-> ")
        # Move to the next node
        current = current.next
    print("None")


# Driver Code
head = None
head = insert_at_end(head, 1)
head = insert_at_end(head, 2)
head = insert_at_end(head, 3)

print("Doubly Linked List after insertion at the end:")
display(head)

Output
Doubly Linked List after insertion at the end:
1 <-> 2 <-> 3 <-> None

Deletion of Doubly Linked List in Python:

Deletion of a node in Doubly Linked List generally involves modifying the next and the previous pointers of nodes. Deletion can be done in 3 ways:

  • At the beginning of DLL
  • At the end of DLL
  • At a given position in DLL

1. Deletion at the beginning:

To delete a node from the beginning of a doubly linked list in Python, you need to follow these steps:

  • Check if the list is empty (head is None). If it is empty, there is nothing to delete.
  • If the list has only one node, set the head to None to delete the node.
  • Otherwise, update the head to point to the next node.
  • Set the “previous” pointer of the new head to None.
  • Optionally, free the memory allocated to the deleted node.

Below is the implementation of the above idea:

Python 
# Python Program for the deletion at the beginning
class Node:
    def __init__(self, data):
        # Initialize a new node with data, previous, and next pointers
        self.data = data
        self.next = None
        self.prev = None

def delete_at_beginning(head):
    # Delete the first node from the beginning of the doubly linked list
    if head is None:
        print("Doubly linked list is empty")
        return None

    if head.next is None:
        return None

    new_head = head.next
    new_head.prev = None
    del head
    return new_head

def traverse(head):
    # Traverse the doubly linked list and print its elements
    current = head
    while current:
      # Print current node's data
        print(current.data, end=" <-> ")  
        # Move to the next node
        current = current.next  
    print("None")

def insert_at_beginning(head, data):
    # Insert a new node at the beginning of the doubly linked list
    new_node = Node(data)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node

# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
    
# Delete the first node (node with data 1) from the beginning:
head = delete_at_beginning(head)

# Traverse and print the nodes after deletion:
traverse(head)

Output
2 <-> 3 <-> 4 <-> None

2. Deletion at a given position:

To delete a node at a given position in a doubly linked list in Python, you need to follow these steps:

  • Check if the list is empty (head is None). If it is empty, there is nothing to delete.
  • If the position is less than 0, print an error message as it’s an invalid position.
  • If the position is 0, delete the node at the beginning of the list.
  • Traverse the list to find the node at the given position.
  • Update the “next” pointer of the previous node to skip the node to be deleted.
  • Update the “previous” pointer of the next node to point to the previous node of the node to be deleted.
  • Optionally, free the memory allocated to the deleted node.

Below is the implementation of the above idea:

Python 
# Python Program for Deletion of a given node
class Node:
    def __init__(self, data):
        # Initialize a new node with data, previous, and next pointers
        self.data = data
        self.next = None
        self.prev = None


def delete_at_position(head, position):
    # Delete the node at a given position from the doubly linked list
    if head is None:
        print("Doubly linked list is empty")
        return None

    if position < 0:
        print("Invalid position")
        return head

    if position == 0:
        if head.next:
            head.next.prev = None
        return head.next

    current = head
    count = 0
    while current and count < position:
        current = current.next
        count += 1

    if current is None:
        print("Position out of range")
        return head

    if current.next:
        current.next.prev = current.prev
    if current.prev:
        current.prev.next = current.next

    del current
    return head


def traverse(head):
    # Traverse the doubly linked list and print its elements
    current = head
    while current:
      # Print current node's data
        print(current.data, end=" <-> ")
        # Move to the next node
        current = current.next
    print("None")


def insert_at_beginning(head, data):
    # Insert a new node at the beginning of the doubly linked list
    new_node = Node(data)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node


# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)

# Delete the node at position 2 (node with data 3):
head = delete_at_position(head, 2)

# Traverse and print the nodes after deletion:
traverse(head)

Output
1 <-> 2 <-> 4 <-> None

3. Deletion at the end:

To delete a node at the end of a doubly linked list in Python, you need to follow these steps:

  • Check if the list is empty (head is None). If it is empty, there is nothing to delete.
  • If the list has only one node, set the head to None to delete the node.
  • Traverse the list to find the last node.
  • Set the “next” pointer of the second-to-last node to None.
  • Optionally, free the memory allocated to the deleted node.

Below is the implementation of the above idea:

Python 
# Python Program Deletion at the end
class Node:
    def __init__(self, data):
        # Initialize a new node with data, previous, and next pointers
        self.data = data
        self.next = None
        self.prev = None

def delete_at_end(head):
    # Delete the last node from the end of the doubly linked list
    if head is None:
        print("Doubly linked list is empty")
        return None

    if head.next is None:
        return None

    current = head
    while current.next.next:
        current = current.next

    del_node = current.next
    current.next = None
    del del_node
    return head

def traverse(head):
    # Traverse the doubly linked list and print its elements
    current = head
    while current:
      # Print current node's data
        print(current.data, end=" <-> ")  
        # Move to the next node
        current = current.next  
    print("None")

def insert_at_beginning(head, data):
    # Insert a new node at the beginning of the doubly linked list
    new_node = Node(data)
    new_node.next = head
    if head:
        head.prev = new_node
    return new_node

# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)

# Delete the last node (node with data 4) from the end:
head = delete_at_end(head)

# Traverse and print the nodes after deletion:
traverse(head)

Output
1 <-> 2 <-> 3 <-> None

Article

Link

Design a data structure for LRU Cache

Link

Reverse a Doubly Linked List

Link

Delete a node in a Doubly Linked List

Link

Insertion in a Doubly Linked List

Link

Insert value in sorted way in a sorted doubly linked list

Link

Find pairs with given sum in doubly linked list

Link

Merge Sort for Doubly Linked List

Link

QuickSort on Doubly Linked List

Link

XOR Linked List – A Memory Efficient Doubly Linked List | Set 2

Link



A
alphacozeop
Improve
Next Article
Circular Linked List in Python

Similar Reads

Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields 'data' and 'link'. The 'data' field stores actual piece of information and 'link' field is used to point to next node. Basically the 'link' field stores the address of the next node. Introduction to Doubly linked list : A Doubly Linked List (D
2 min read
When is Doubly Linked List more Efficient than Singly Linked List?
Did you know there are some cases where a Doubly Linked List is more efficient than a Singly Linked List, even though it takes more memory compared to a Singly Linked List? What are those Cases? Well, we will discuss that in the following article, But first, let's talk about Singly and linked lists: What is a Singly Linked List?A singly linked list
4 min read
Is two way linked list and doubly linked list same?
Yes, a two-way linked list and a doubly linked list are the same. Both terms refer to a type of linked list where each node contains a reference to the next node as well as the previous node in the sequence. The term “two-way” emphasizes the ability to move in both directions through the list, while “doubly” highlights that there are two links per
3 min read
XOR Linked List – A Memory Efficient Doubly Linked List | Set 2
In the previous post, we discussed how a Doubly Linked can be created using only one space for the address field with every node. In this post, we will discuss the implementation of a memory-efficient doubly linked list. We will mainly discuss the following two simple functions. A function to insert a new node at the beginning.A function to travers
10 min read
XOR Linked List - A Memory Efficient Doubly Linked List | Set 1
In this post, we're going to talk about how XOR linked lists are used to reduce the memory requirements of doubly-linked lists. We know that each node in a doubly-linked list has two pointer fields which contain the addresses of the previous and next node. On the other hand, each node of the XOR linked list requires only a single pointer field, whi
15+ min read
Construct a Doubly linked linked list from 2D Matrix
Given a 2D matrix, the task is to convert it into a doubly-linked list with four pointers that are next, previous, up, and down, each node of this list should be connected to its next, previous, up, and down nodes.Examples: Input: 2D matrix 1 2 3 4 5 6 7 8 9 Output: Approach: The main idea is to construct a new node for every element of the matrix
15+ min read
Python | Queue using Doubly Linked List
A Queue is a collection of objects that are inserted and removed using First in First out Principle(FIFO). Insertion is done at the back(Rear) of the Queue and elements are accessed and deleted from first(Front) location in the queue. Queue Operations:1. enqueue() : Adds element to the back of Queue. 2. dequeue() : Removes and returns the first ele
3 min read
Python | Stack using Doubly Linked List
A stack is a collection of objects that are inserted and removed using Last in First out Principle(LIFO). User can insert elements into the stack, and can only access or remove the recently inserted object on top of the stack. The main advantage of using LinkedList over array for implementing stack is the dynamic allocation of data whereas in the a
4 min read
Python Program For Merge Sort For Doubly Linked List
Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.For example, the following doubly linked list should be changed to 24810 Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Merge sort for singly linked list is already discussed. The important change her
3 min read
Python Program For Deleting A Node In A Doubly Linked List
Pre-requisite: Doubly Link List Set 1| Introduction and Insertion Write a function to delete a given node in a doubly-linked list. Original Doubly Linked List  Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. Approach: The deletion of a node in a doubly-linked list can be divided into three main categories:  After
4 min read
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox