Implement a doubly linked list with Python

Introduction

A singly linked list is a set of linked nodes. Different from a singly linked list, each node in a doubly linked list has an extra pointer points to its previous node. Today, I’ll talk about the implementation of a doubly linked list in python.

Implementation in Python

• Node class

A doubly linked list is composed of a set of nodes. A node has two pointers and a value. One pointer points to its previous node, another pointer points to its next node.

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

• Doubly linked list class

Besides the nodes, we also need two variables to specify the start and end of a linked list. We usually have two nodes to represent the head and tail of the doubly linked list.

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(float('inf')
        self.tail = Node(float('inf')
        self.head.next = self.tail
        self.tail.prev = self.head

• Implement methods

The basic functions of a doubly linked list are: insert, remove. Both functions are arranging a node. We can apply them to the Node class.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None
    def insert_after(self, node):
        next_node = self.next
        self.next = node
        node.prev = self
        node.next = next_node 
        next_node.prev = node
    def remove(self):
        self.next.prev = self.prev
        self.prev.next = self.next
        self.next, self.prev = None, None

Combine two classes together:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None
    def insert_after(self, node):
        next_node = self.next
        self.next = node
        node.prev = self
        node.next = next_node 
        next_node.prev = node
    def remove(self):
        self.next.prev = self.prev
        self.prev.next = self.next
        self.next, self.prev = None, None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(float('inf')
        self.tail = Node(float('inf')
        self.head.next = self.tail
        self.tail.prev = self.head
        //to map the val with the node
        self.mapping = {}  

Analyze

A doubly linked list performs well in inserting and deleting a node. Both functions only take O(1) running time. For the space complexity, it takes O(n), n is the length of the list since we create an extra dictionary to record the node position of the list.

Thanks for reading!