Data Structures
What is a Data Structure?
A data structure is a method of organizing and storing data in a computer so that it can be accessed and
modified efficiently. The choice of data structure affects the performance of algorithms and applications.
List of Common Data Structures
Category Data Structures Included
Linear Structures Array, Linked List, Stack, Queue, Deque
Non-Linear Structures Tree, Graph
Hash-based Hash Table, Hash Map, Hash Set
Advanced/Abstract Heap, Trie, Segment Tree, Disjoint Set (Union-Find)
This note will focus on the core foundational data structures:
● Array
● Linked List
● Stack
● Queue
● Tree
1. Arrays
An array is a fixed-size collection of elements of the same type, stored in contiguous memory locations.
Key Characteristics:
● Elements are
accessed using
index (starting at 0).
● Size must be known
at the time of
creation (in most
languages like C,
Java).
● Random access is
allowed (constant-time lookup).
Use Cases:
● Efficient read/write at known positions
● Storing data in fixed order
● Implementing other data structures like matrices, heaps
2. Linked Lists
A linked list is a linear data structure in which elements (called nodes) are connected using pointers.
Types:
● Singly Linked List: Each node points to the next
● Doubly Linked List: Each node points to the next and previous
● Circular Linked List: The last node points back to the first
Key Characteristics:
● Dynamic size (can grow/shrink easily)
● No random access (must traverse from head)
● Efficient insertions and deletions (if position is known)
Use Cases:
● Implementing stacks, queues
● Handling large/unknown data sizes
● Efficient insert/delete in middle of list
Singly Linked List
Doubly Linked List
Circular Linked List
3. Stack
A stack is a linear data structure that follows the
Last In, First Out (LIFO) principle.
Key Operations:
● push(x): Add element x to the top
● pop(): Remove and return the top element
● peek() / top(): View the top element without
removing it
● isEmpty(): Check if the stack is empty
Implementation:
● Using arrays or linked lists
Use Cases:
● Function call management (call stack)
● Expression evaluation and syntax parsing
● Undo mechanisms in editors
● DFS (Depth-First Search)
4. Queue
A queue is a linear data structure that follows the First In, First Out (FIFO) principle.
Key Operations:
● enqueue(x): Add element x to the rear
● dequeue(): Remove and return the front element
● peek() / front(): View front element
● isEmpty(): Check if queue is empty
Variants:
● Circular Queue
● Priority Queue
● Deque (Double-Ended Queue)
Implementation:
● Arrays or linked lists
Use Cases:
● Scheduling (e.g., CPU jobs, printer
tasks)
● Breadth-First Search (BFS) in graphs
● Asynchronous data processing (e.g., message queues)
5. Trees
A tree is a non-linear hierarchical data structure consisting of nodes, where each node has a value and links to
child nodes.
Key Terms:
● Root: Topmost node
● Leaf: Node with no children
● Parent/Child: Direct
relationships
● Height: Length of longest
path to a leaf
● Depth: Distance from root
Types of Trees:
● Binary Tree: Each node
has ≤ 2 children
● Binary Search Tree (BST):
Left < Root < Right
● AVL Tree, Red-Black Tree:
Balanced BSTs
● Trie: Tree used for string/prefix searching
● Heap: Complete binary tree with ordering rules
Use Cases:
● Hierarchical data (file systems, XML/HTML)
● Fast searching and sorting (BST, Trie)
● Priority scheduling (Heap)
● Decision trees, AI, compilers