🛠️ User Defined Data Structures

1. Stack (LIFO - Last In, First Out)

Definition: A linear data structure that follows the LIFO (Last In, First Out) principle. The most recently added element is the first one to be removed. Think of a stack of plates: you add to the top and remove from the top.

Operations:

• push(item): Add item to the top.
• pop(): Remove item from the top.
• peek(): View the top item without removing it.

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        return self.stack.pop()

s = Stack()
s.push(1)
s.push(2)
print(s.pop())  # 2

---

2. Queue (FIFO - First In, First Out)

Definition: A linear data structure that follows the FIFO (First In, First Out) principle. The first item added is the first one removed. Like a line at a ticket counter.

Operations:

• enqueue(item): Add item to the rear.
• dequeue(): Remove item from the front.

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        return self.queue.popleft()

q = Queue()
q.enqueue(1)
q.enqueue(2)
print(q.dequeue())  # 1

---

3. Linked List

Definition: A linked list is a linear data structure consisting of nodes, where each node contains some data and a pointer (reference) linking it to the next node. Unlike arrays, linked lists allow dynamic memory allocation and efficient insertion and deletion operations.

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

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

    def insert(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def display(self):
        curr = self.head
        while curr:
            print(curr.data, end=' ')
            curr = curr.next

ll = LinkedList()
ll.insert(3)
ll.insert(2)
ll.insert(1)
ll.display()  # 1 2 3

Types of Linked Lists:

• Singly Linked List: Nodes point only to the next node.
• Doubly Linked List: Nodes point to both previous and next.
• Circular Linked List: Last node points to the first.

1. Singly Linked List

A singly linked list is a collection of nodes, where each node has data and a pointer that points to the next node in the sequence. The last node points to null.

Structure:

[Data | Next] → [Data | Next] → [Data | Next] → null

2. Doubly Linked List

A doubly linked list is similar to a singly linked list, but each node points to both its previous and next node. This enables traversal in both directions.

null ⇄ [Prev | Data | Next] ⇄ [Prev | Data | Next] ⇄ null

3. Circular Linked List

A circular linked list is one where the nodes form a circular chain. The last node points back to the first node, creating a loop.

[Data | Next] → [Data | Next] → [Data | Next]
   ↑                                  │
   └──────────────────────────────────┘

---

4. Tree (e.g., Binary Tree)

Definition: A hierarchical data structure with a root node and child nodes, forming a tree-like structure. Each node can have zero or more children. The most common type is the Binary Tree where each node has at most two children.

Variants:

• Binary Search Tree (BST): Left child < parent < right child
• Heap: Complete binary tree with a specific ordering
• Trie: Prefix tree used in text processing

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Sample tree:
#      1
#     / \
#    2   3

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

print(root.left.data)  # 2

---

5. Graph (Adjacency List Representation)

Definition: A non-linear data structure consisting of nodes (vertices) and edges connecting them. Edges can be directed or undirected, and graphs can be weighted or unweighted.

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        self.graph.setdefault(u, []).append(v)
        self.graph.setdefault(v, []).append(u)  # undirected

    def show(self):
        for node in self.graph:
            print(f"{node} -> {self.graph[node]}")

g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.show()

Output:

1 -> [2, 3]
2 -> [1]
3 -> [1]