Category: Data Structures
-
Overview A Trie (derived from “retrieval”), also known as a prefix tree, is a specialized tree-based data structure used to store a dynamic set of strings. Unlike a binary search tree, no node in the trie stores the key associated with that node; instead, its position in the tree defines the key it is associated…
-
Overview A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. The last element added to the stack is the first one to be removed. Think of it like a stack of physical plates. Core Concepts Push: Adding an element to the top of the stack. Pop: Removing the top element…
-
Overview A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The first element added to the queue is the first one to be removed. Think of it like a line of people waiting for a bus. Core Concepts Enqueue: Adding an element to the end (rear) of the queue. Dequeue:…
-
Overview A Linked List is a linear collection of data elements called nodes, where each node contains a data field and a reference (link) to the next node in the sequence. Unlike arrays, linked lists are not stored in contiguous memory locations. Core Concepts Node: The basic building block. Contains data and a next pointer.…
-
Overview A Heap is a specialized tree-based data structure that satisfies the heap property. It is most commonly implemented as a binary heap, which is a complete binary tree. Heaps are primarily used to implement priority queues and the heapsort algorithm. Core Concepts Heap Property: Max-Heap: The value of the root node must be the…
-
Overview A Hash Table (or Hash Map/Dictionary) is a data structure that maps keys to values using a hash function. It allows for extremely fast data retrieval by converting a key into an index in an underlying array. Core Concepts Hash Function: An algorithm that takes an input (key) and returns a fixed-size integer (hash),…
-
Overview A Graph is a non-linear data structure consisting of a finite set of vertices (or nodes) and a set of edges that connect pairs of vertices. Graphs are used to represent networks of interconnected objects. Core Concepts Directed vs. Undirected: Directed (Digraph): Edges have a direction (e.g., a Twitter follow). Undirected: Edges have no…
-
Overview A Binary Search Tree (BST) is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key. Core Concepts Root: The topmost node of…
-
Overview An array is a linear data structure that collects multiple elements of the same type (usually) stored in contiguous memory locations. Elements are accessed using a numerical index. Core Concepts Indexing: Most languages use zero-based indexing, where the first element is at index 0. Contiguous Memory: Elements are stored side-by-side in memory, allowing for…
-
Overview AVL and Red-Black Trees are types of self-balancing Binary Search Trees (BSTs). In a standard BST, if elements are inserted in sorted order, the tree becomes a linked list (degenerate), leading to $O(n)$ time complexity for operations. Self-balancing trees use rotations and recoloring to maintain a height of $O(\log n)$, ensuring efficient search, insertion,…