Data Structures

Summary

• Linear Structures: Stack (LIFO), Queue (FIFO), Linked List.
• Hierarchical Structures: Trees, AVL Trees, Binary Search Trees.
• Graph Representation: Adjacency Matrix, Adjacency List.
• Search Structures: Heap (Max/Min), Hash Table.

Linear Data Structures

Linear data structures organize elements sequentially, where each element has a unique predecessor and successor (except the first and last elements).

Examples:

Arrays:

A collection of elements stored in contiguous memory locations.

Operations:

Access: O(1)

Search: O(n)

Insertion/Deletion: O(n) (in the worst case, due to shifting).

Example

arr = [1, 2, 3, 4]
print(arr[2])  # Access element at index 2: Output is 3

Linked Lists:

A sequence of nodes where each node contains data and a reference to the next node.

Types:

Singly Linked List

Doubly Linked List

Operations:

Insertion/Deletion: O(1) at the head, O(n) elsewhere.

Search: O(n).

Example

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

Stacks:

A Last-In-First-Out (LIFO) structure.

Operations:

Push: O(1)

Pop: O(1)

Peek: O(1)

Applications: Expression evaluation, recursion.

Example

stack = []
stack.append(1)  # Push
stack.pop()      # Pop

Queues:

A First-In-First-Out (FIFO) structure.

Operations:

Enqueue: O(1)

Dequeue: O(1)

Example:

from collections import deque
queue = deque()
queue.append(1)  # Enqueue
queue.popleft()  # Dequeue