Data Structures

A Data Structure is a mathematical or logical model of organizing data items in memory, coupled with a set of operations that can be performed upon them. An Abstract Data Type (ADT) formalizes this concept by specifying what operations can be performed on the data without dictating how those operations must be implemented in hardware or software.

Data structures are taxonomically classified into two principal dimensions:

• Primitive vs. Non-Primitive: Primitive data structures (e.g., int, float, char, bool) are directly manipulated by underlying machine-level processor instructions. Non-primitive data structures are composite arrangements constructed from primitive types (e.g., arrays, structures, classes).
• Linear vs. Non-Linear: In a Linear Data Structure, data elements form a sequential or one-to-one relationship where every element (except the first and last) has a unique predecessor and successor. In a Non-Linear Data Structure, elements exhibit hierarchical, one-to-many, or many-to-many multi-level relationships.
• Static vs. Dynamic: Static data structures allocate a fixed block of contiguous memory at compilation time (e.g., static arrays), while dynamic structures allocate and free memory nodes on-demand during runtime on the system heap (e.g., linked lists, trees).

Every comprehensive data structure supports a canonical suite of primitive operations:

• Traversal: Processing every data node exactly once to read, print, or evaluate its contents.
• Insertion: Incorporating a new data record into the structure at a designated position.
• Deletion: Removing an existing data record from the structure and reclaiming its memory.
• Searching: Locating the memory address or index of a target record possessing a specified search key.
• Sorting: Rearranging data elements into a strictly monotonic ascending or descending sequence.
• Merging: Combining two distinct sorted structures into a single unified sorted structure.

An Array is a homogeneous collection of data elements stored at contiguous memory locations. Because memory addresses advance uniformly by element size $W$ (in bytes), any element can be accessed in constant time $O(1)$ via simple pointer arithmetic:

• 1D Array Address Formula: Given base address $B$, element size $W$, lower bound $LB$: $$\text{Address}(A[k]) = B + W \times (k - LB)$$
• 2D Array Row-Major Order (RMO): Elements are stored row-by-row consecutively. For array $A[R][C]$ with row lower bound $LBR$ and column lower bound $LBC$: $$\text{Address}(A[i][j]) = B + W \times [C \times (i - LBR) + (j - LBC)]$$
• 2D Array Column-Major Order (CMO): Elements are stored column-by-column consecutively: $$\text{Address}(A[i][j]) = B + W \times [(i - LBR) + R \times (j - LBC)]$$

Searching is the algorithmic procedure of determining the location of a target key within a dataset:

# Rigorous Binary Search Implementation in Python
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        # Calculate mid with overflow prevention:
        mid = low + (high - low) // 2
        
        if arr[mid] == target:
            return mid  # Key found at index mid
        elif arr[mid] < target:
            low = mid + 1  # Target lies in right half
        else:
            high = mid - 1  # Target lies in left half
            
    return -1  # Key not present in array

A Stack is a constrained linear data structure adhering strictly to the Last-In, First-Out (LIFO) discipline. All insertions (push) and deletions (pop) occur exclusively at a single designated terminus known as the Top of Stack (TOS).

• Stack Pointer (top): An integer tracking the index of the most recently inserted item. For an empty stack, top = -1.
• Stack Overflow: Occurs when an insertion (push) is attempted on a statically sized stack that has already reached its maximum capacity (top == MAX - 1).
• Stack Underflow: Occurs when a deletion (pop) or inspection (peek) is attempted on an empty stack (top == -1 or len(stack) == 0).

# Robust Class-Based Stack Implementation in Python
class Stack:
    def init(self, capacity=100):
        self.items = []
        self.capacity = capacity
        
    def is_empty(self):
        return len(self.items) == 0
        
    def is_full(self):
        return len(self.items) >= self.capacity
        
    def push(self, item):
        if self.is_full():
            raise OverflowError("Stack Overflow: Cannot push to a full stack.")
        self.items.append(item)
        
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot pop from an empty stack.")
        return self.items.pop()
        
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack Underflow: Cannot peek into an empty stack.")
        return self.items[-1]

Arithmetic expressions can be formatted in three standard notation topologies:

• Infix Notation: Operators reside between operands (e.g., A + B * C). Requires parentheses and precedence rules to resolve ambiguity.
• Prefix Notation (Polish): Operators precede their operands (e.g., + A * B C). Parenthesis-free.
• Postfix Notation (Reverse Polish - RPN): Operators immediately succeed their operands (e.g., A B C * +). Highly optimal for stack-based execution machines.

A Queue is a linear data structure governed by the First-In, First-Out (FIFO) discipline. It possesses two independent pointers:

• Front Pointer (front): Points to the element ready for removal (dequeue).
• Rear Pointer (rear): Points to the location where new elements enter (enqueue).
• The False Overflow Flaw of Linear Queues: In an array-based linear queue, after repeatedly enqueuing and dequeuing, rear reaches the end of the array (rear == MAX - 1). Even though empty slots exist before front, the queue erroneously reports an Overflow state unless elements are costlier shifted or indices wrap around.

A Circular Queue solves linear memory drift by treating the sequential buffer as a continuous ring via modulo arithmetic:

• Circular Advancement: rear = (rear + 1) % MAX and front = (front + 1) % MAX.
• Full Condition: (rear + 1) % MAX == front.
• Empty Condition: front == -1.

While arrays require contiguous chunks of physical memory and incur heavy $O(n)$ element-shifting costs during middle insertions or deletions, a Linked List allocates discrete heap nodes dynamically as needed. Each node houses:

• Data Field: Stores the actual payload (primitive value, object, record).
• Link / Next Field: Holds the reference pointer storing the exact memory address of the succeeding node. The terminal node's pointer is assigned None (or NULL).
• Head Pointer: A dedicated pointer referencing the very first node of the list. If head is None, the linked list is empty.

Linked lists present three primary structural variations:

• Singly Linked List (SLL): Unidirectional forward navigation. Each node points only to next. Inserting at the head is a blazing $O(1)$ operation: new_node.next = head; head = new_node.
• Doubly Linked List (DLL): Bidirectional navigation. Each node contains two pointers: prev and next. Enables backward traversal and allows deletion of a given node in $O(1)$ without searching for its predecessor.
• Circular Linked List (CLL): The terminal node's next pointer points back to the head node instead of None, forming an endless loop suitable for round-robin schedulers.

A Tree is a non-linear, hierarchical data structure comprising nodes connected by directed edges. It contains exactly one designated Root Node and zero or more disjoint subtrees.

• Degree of a Node: Total number of subtrees or direct children possessed by the node.
• Leaf / Terminal Node: A node possessing degree $0$ (no children).
• Height / Depth: The length of the longest path from the root node to any leaf. For a tree with height $h$, maximum possible nodes in a binary tree is $N_{\max} = 2^{h+1} - 1$.
• Binary Tree: A tree in which every node has at most two children, customarily termed the Left Child and Right Child.

A Binary Search Tree (BST) is an ordered binary tree governed by the strict invariant:

Traversing a binary tree means visiting every node systematically. Depth-First Traversals include: