Mastering Data Structures

A Comprehensive Computer Science Engineering Guide: Linear, Non-Linear & Decision

Frameworks

Core Concepts • Time & Space Complexity • Abstract Data Types • Implementation Trade-offs

1. Introduction to Data & Data Structures

In computer science, data represents raw observations, values, or symbols processed by a computer. However,
unstructured raw data is inefficient to process. A Data Structure is a specialized format for organizing, processing,
retrieving, and storing data in computer memory so that operations can be performed efficiently.

Key Distinction: ADT vs. Data Structure

An Abstract Data Type (ADT) defines what operations a data type can perform and its logical behavior, without
specifying how it is implemented (e.g., Stack ADT, Queue ADT). A Data Structure is the actual physical
implementation of an ADT in code using dynamic memory, arrays, pointers, or reference fields.

Classification of Data Structures

Data structures are broadly categorized based on how elements are arranged and allocated in memory:

Category Characteristics Examples

Primitive Basic system-level data types int , float , char , boolean , pointer
operated on directly by machine
instructions.

Linear Non-Primitive Data elements arranged Arrays, Singly/Doubly Linked Lists, Stacks, Queues
sequentially; each element has a
single predecessor and successor.

Non-Linear Non- Data elements connected Binary Trees, BSTs, Heaps, Graphs, Hash Tables, Tries
Primitive hierarchically or in complex multi-
dimensional networks.

2. Linear Data Structures

Linear data structures organize data elements in a sequential order. Memory can be contiguous (array-based) or
fragmented/pointer-based (linked list-based).

A. Arrays
An array is a collection of homogeneous data elements stored in contiguous memory locations. Indexing allows direct
element access.

• Static Arrays: Fixed size allocated at compile time.

• Dynamic Arrays: Automatically resize (usually doubling capacity) when full (e.g., std::vector in C++, ArrayList
in Java, Python list ).

Data Structures & Algorithms Reference Guide Page 1 of 4

 Array Index: [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]
Memory Addr: 0x100 0x104 0x108 0x10C 0x110
Values: | 15 | 42 | 07 | 89 | 33 |

B. Linked Lists
A linked list consists of nodes where each node contains data and a pointer/reference to the next node in memory, allowing
dynamic insertion and deletion without memory re-allocation.

• Singly Linked List: Navigation in forward direction only ( Data | Next ).

• Doubly Linked List: Bidirectional traversal with pointers to both next and previous nodes ( Prev | Data | Next ).
• Circular Linked List: Last node points back to the head node.

C. Stacks (LIFO - Last In, First Out)

A linear structure where insertion and removal occur strictly at one end called the Top.

• Key Operations: push(x) , pop() , peek() / top() .

• Primary Applications: Function execution stack (call stack), recursion handling, expression parsing (infix to postfix),
undo mechanisms in text editors, matching parentheses.

D. Queues (FIFO - First In, First Out)

A linear structure where elements are inserted at the Rear and removed from the Front.

• Standard Queue: Basic FIFO processing (e.g., printer queue).

• Circular Queue: The last position connects back to the first to prevent memory waste in array-based queues.
• Priority Queue: Each element has an assigned priority; elements with higher priority are dequeued first (often
implemented using a Min/Max Heap).
• Double-Ended Queue (Deque): Insertions and deletions allowed at both Front and Rear.

3. Non-Linear Data Structures

Non-linear structures arrange data non-sequentially, allowing complex relationship modeling such as hierarchies and
networks.

A. Trees
A hierarchical structure consisting of nodes connected by edges, starting from a single Root Node.

• Binary Tree: Every parent node has at most two children (Left and Right).
• Binary Search Tree (BST): A binary tree where the left subtree contains values strictly smaller than the parent node,
and the right subtree contains values strictly greater. Search time is O(log n) on average.
• Balanced BSTs (AVL, Red-Black Trees): Self-balancing trees that maintain height at O(log n) to prevent worst-case
linear degeneration O(n). Used in C++ std::map and Java TreeMap .
• Heap (Binary Heap): A complete binary tree satisfying the Heap Property (Min-Heap: Parent ≤ Children; Max-Heap:
Parent ≥ Children). Essential for Priority Queues and HeapSort.
• Trie (Prefix Tree): Tree-based dictionary optimized for fast string/prefix lookups (O(k) where k is string length). Used in
autocomplete engines.

Data Structures & Algorithms Reference Guide Page 2 of 4

 Binary Search Tree Example:
[ 50 ]
/ \
[ 30 ] [ 70 ]
/ \ / \
[ 20 ] [ 40 ] [ 60 ] [ 80 ]

B. Graphs
A network of nodes called Vertices (V) connected by links called Edges (E). Graphs model arbitrary relational networks.

• Types: Directed vs. Undirected, Weighted vs. Unweighted, Cyclic vs. Acyclic (DAG).
• Representations:
◦ Adjacency Matrix: A V × V 2D array. Fast edge lookup O(1), high space complexity O(V²).
◦ Adjacency List: An array of linked lists/vectors. Space efficient O(V + E), slower edge lookup O(degree).

• Core Traversals: Breadth-First Search (BFS - uses Queue) and Depth-First Search (DFS - uses Stack/Recursion).

C. Hash Tables (Hash Maps)

A data structure that maps key-value pairs using a Hash Function that converts a key into an array index. Offers average-
case constant time search, insertion, and deletion O(1).

• Collision Resolution Strategies:

◦ Separate Chaining: Each array slot holds a linked list or BST of collided elements.
◦ Open Addressing: Probing adjacent slots upon collision (Linear Probing, Quadratic Probing, Double Hashing).

4. Big O Complexity Comparison Matrix

Average and Worst-case time and space complexities for core operations across data structures:

Time Complexity (Average) Worst Time

Space
Data Structure
Insertion / Search / Complexity
Access Search
Deletion Insert

Array / Dynamic Array O(1) O(n) O(n) O(n) O(n)

Singly / Doubly Linked List O(n) O(n) O(1)* O(n) O(n)

Stack / Queue O(n) O(n) O(1) O(1) O(n)

Hash Table N/A O(1) O(1) O(n) O(n)

Binary Search Tree O(log n) O(log n) O(log n) O(n) O(n)

(Unbalanced)

AVL / Red-Black Tree O(log n) O(log n) O(log n) O(log n) O(n)

Binary Heap N/A O(n) O(log n) O(log n) O(n)

* Insertion/Deletion in Linked Lists is O(1) once the target node pointer is known/positioned.

Data Structures & Algorithms Reference Guide Page 3 of 4

5. How to Choose the Right Data Structure

Selecting the optimal data structure requires evaluating primary access patterns, write frequency, memory overhead
constraints, and operational complexity.

4-Step Decision Framework

1. Analyze Access vs. Modification: Do you need frequent random lookups (O(1) via Index/Key) or frequent
insertions/deletions at dynamic positions?
2. Evaluate Data Relationships: Is the data sequential (Linear), dynamic hierarchical (Tree), or heavily
interconnected (Graph)?
3. Identify Ordering & Priority Constraints: Does data require strict sorted order (BST/AVL), strict FIFO/LIFO
execution, or priority-based retrieval (Heap)?
4. Assess Memory Overhead: Can you afford pointer overhead (Linked lists, Trees) or do you require dense
memory packing (Arrays)?

Scenario-Based Decision Matrix

Recommended Data
Requirement / Real-World Scenario Engineering Justification
Structure

Fast random access by index with Array / Dynamic Array Direct memory pointer math yields instant O(1)
known buffer size access with high CPU cache locality.

Instant key-value lookup without explicit Hash Table / Hash Map Average O(1) search and insertion. Ideal for
ordering caching, session stores, and database indexing.

Maintaining dynamic items in sorted Balanced BST (Red-Black / Guarantees O(log n) search, insertion, and
order with range queries Self-Balancing Tree) deletion while allowing ordered sequential
iteration.

Processing tasks by explicit emergency Priority Queue (Binary Fast O(1) peek at max/min item, and efficient
level or priority score Heap) O(log n) insertion and extraction.

Modeling social networks, router Graph (Adjacency List) Represents arbitrary complex connections.
topology, or GPS routing Supports Dijkstra, A*, BFS, and DFS pathfinding.

Undo/Redo history or recursive call Stack LIFO property strictly tracks last performed
stack management operations in O(1) time.

Buffering network data packets or Circular Queue FIFO property processes items in arrival order
handling print jobs with zero memory leakage or dynamic reallocation
lag.

Prefix searching, search engine auto- Trie (Prefix Tree) Search time depends purely on key length O(k),
complete independent of dataset total size N.

Data Structures & Algorithms Reference Guide Page 4 of 4