Linked List

A linked list is a data structure representing a sequence of nodes. In a doubly linked list, each node has a pointer to the previous node and the next node. The only exceptions are the head and the tail.

Let’s first build a node.

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

Using the node, we can build a linked list with two attributes: insert and delete.

class LinkedList:
  def __init__(self):
    self.head = None
    self.tail = None

  def insert(self, value):
    node = Node(value)

    if(self.head == None):
      self.head = node
      self.tail = node
    else:
      node.prev = self.tail
      self.tail.next = node

      self.tail = node

  def delete(self, node):
    if(node.next):
      node.next.prev = node.prev
    if(node.prev):
      node.prev.next = node.next