Linked List

• Nodes stored in non contiguous memory
• Applications: Round robin, places where insert/delete at beginning should be O(1)

Single Linked List

Python

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

Circular Linked List

• the next of the last node points at head
• Advantage: whole list can be traversed from any node; implementation of round robin

Doubly Linked List

• Advantage: traverse in both dir, insert/delete before node, insert/delete form both ends in O(1) by maintaining tail
• Disadvantages: extra space, complex code

Python

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