Data Structures
1. What Is a Graph? Concept: From Trees to Graphs A graph can be understood as an extension and generalization of the tree structure. In fact, a tree is just a special kind of graph. A graph consists of a set of vertices and a set of edges. Each edge connects a pair of vertices in the graph. Graphs can model more complex real-world relationships, and are no longer restricted to the hierarchical relationships of a tree. Applications of Graphs Social networks: individuals or organizations are vertices; the social connections between them are edges. Maps and navigation: key locations (intersections, landmarks) are vertices; roads are edges. Computer networks: computers or routers are vertices; network connections are edges. 2. Key Terminology Undirected Graph Edges have no direction. If there is an edge between vertices A and B, we can travel from A to B and also from B to A.
Read note →Stack A Stack is a special linear data structure that only allows insertion and deletion operations at one end of the structure. This end is called the Top, and the other end is called the Bottom. Stack operations follow the Last-In, First-Out (LIFO) principle. Push Add a new element at the top of the stack.
Pop Remove and return the element at the top of the stack.
Top (Peek) Return the element at the top of the stack without removing it.
Read note →Queue A Queue is a special linear data structure that only allows insertion at one end of the structure and deletion at the other end. The end where insertion occurs is called the Rear, and the end where deletion occurs is called the Front. Queue operations follow the First-In, First-Out (FIFO) principle. Enqueue Add a new element at the rear of the queue.
Dequeue Remove and return the element at the front of the queue.
Read note →What is a Tree? Concept: A Non-Linear Hierarchical Structure Tree is an abstract data type used to simulate data with hierarchical relationships. It consists of n (n ≥ 0) finite nodes. It is a non-linear data structure, in contrast to the linear structures we studied earlier such as lists, stacks, and queues. In a tree structure, there is a special node called the Root. The remaining nodes can be divided into m (m ≥ 0) disjoint sets T₁, T₂, …, Tₘ, each of which is itself a tree, referred to as a Subtree of the root. Real-Life Examples Book table of contents: The book is the root node, chapters are intermediate nodes, and sections are leaf nodes. File system: The root directory is the root node, subdirectories at each level are intermediate nodes, and files are leaf nodes. Key Terminology (Based on the tree diagram with nodes A, B, C, D, E, F, G, H, I, K)
Read note →Union-Find (Disjoint Set Union) Problem Definition Given N mutually disjoint sets, we need to support two operations:
Merge: Union two sets together Query: Determine whether two elements belong to the same set Example Operation Sequence Elements: a, b, c, d, e, f
Operations: Merge(a,b), Merge(b,e), Merge(c,f), Merge(b,f)
Approach 1: Naive Label-Based Assign each element a set ID. To merge, update all elements of one set to the other’s ID.
Operation a b c d e f Init 1 2 3 4 5 6 Merge(a,b) 1 1 3 4 5 6 Merge(b,e) 1 1 3 4 1 6 Merge(c,f) 1 1 3 4 1 3 Merge(b,f) 1 1 1 4 1 1 Complexity: Query: O(1) | Merge: O(n)
Read note →What is a Linked List? Concept: A Dynamic Data Structure A Linked List is a linear data structure, but its elements are not stored contiguously in memory. It is composed of a series of Nodes, where each node contains two parts: Data field: stores the element’s data. Pointer field: stores the memory address of the next node. This structure — discrete memory blocks chained together via pointers — makes linked lists very efficient for insertion and deletion operations. Comparison with Arrays Array Linked List Memory Contiguous Non-contiguous Access Fast — O(1) Slow — O(n) Insert/Delete Slow — O(n) Fast — O(1) Structure: Nodes and Pointers Singly Linked List The simplest type of linked list. Each node has exactly one pointer pointing to its successor node.
Read note →Concept: A Special Kind of Queue A priority queue is an abstract data type that allows us to store elements and retrieve (usually remove) the minimum or maximum element at any time.
Unlike a regular queue’s “first-in, first-out” principle, a priority queue outputs the highest-priority element first. An element’s “priority” is typically determined by its value. Comparison with Stack and Queue Structure Order Policy Regular Queue First-In, First-Out (FIFO) — cares about insertion order Stack Last-In, First-Out (LIFO) — also cares about insertion order Priority Queue Highest priority out first — cares about the element’s own priority, regardless of insertion order 1. What Is a Heap? A heap is a special data structure based on a complete binary tree, commonly used to implement priority queues.
Read note →