Table of content:

1. What is a Data Structure?

A Data Structure is a way of organizing and storing data in a computer’s memory so that it can be used efficiently.

Why do we need Data Structures (DS)?

To store large amount of data efficiently

To access and modify data quickly

To implement algorithms efficiently

Many more exist (Hash Table, Heap, Trie, etc.) - each designed for specific needs.

Common Types of Data Structures

Type	What It Does	Example / Real-World Analogy
Linear	Stores items in a sequence	A list of songs in a playlist
Non-Linear	Organizes items in a hierarchy or network	A family tree or road map
Static	Has a fixed size	A fixed-size array of 10 elements
Dynamic	Can grow or shrink in size	A list of songs in a playlist

2. Abstract Data Types (ADTs) vs. Data Structures

Important: For simplicity and consistency throughout this website, we use the term Data Structure as a broad category that includes both concrete data structures and Abstract Data Types (ADTs).

	Abstract Data Type (ADT)	Data Structure
What it is	Defines a logical model: what operations are available and the rules or behavior those operations must follow.	A concrete way of organizing and storing data so that operations can be implemented efficiently.
Focus	Describes what the structure should do, without specifying how it is implemented.	Describes how the data is represented and how operations such as access, insert, search, and delete are performed.
Examples	Stack, Queue, List, Priority Queue	Array, Linked List, Binary Heap, Hash Table
Analogy	An interface or contract describing required behavior.	An implementation that fulfills that contract.

Topic	Technical Classification	What Students Learn
Array	Data Structure	Contiguous/indexed storage
Linked List	Data Structure	Nodes connected by references
List	ADT	Ordered collection behavior
Stack	ADT	LIFO behavior
Queue	ADT	FIFO behavior
Deque	ADT	Insert/remove from both ends
Hash Table	Data Structure	Hash-based key storage
Map / Dictionary	ADT	Key-value operations
Set	ADT	Collection of unique values
Binary Heap	Data Structure	Heap-ordered tree representation
Priority Queue	ADT	Remove highest/lowest-priority item
Binary Search Tree	Data Structure	Ordered hierarchical storage
Trie	Data Structure	Prefix-based tree storage
Graph representation	Data Structure / representation	Represents vertices and edges using structures such as adjacency lists or adjacency matrices

3. How Data Structures and Algorithms work together

An algorithm is a step-by-step procedure for solving a problem. It often needs a Data Structure to organize the data it works on, and the choice of Data Structure can strongly affect the algorithm’s efficiency.

Key Takeaway: The right data structure makes the algorithm faster and more efficient to run in solving a problem.

Example 1: to implement “undo” feature in a text editor

Use a Stack

Algorithm: Push each edit onto the stack and pop the most recent edit when undoing.

A Stack's Last In, First Out (LIFO) behavior makes undo operations natural and efficient.

Example 2: Finding a friend in your contacts list.

4. Big O Notation: Measuring Efficiency

Big O Notation describes how the running time (or memory usage) of an algorithm grows as the input size (n) increases. It tells us:

Best case, average case, or worst case growth

Helps compare algorithms

Ignores constants and lower order terms

How Does It Relate to Data Structures?

The choice of data structure can change the time complexity of operations used by an algorithm.

Problem	Data Structure Choice	Time Complexity
1. Search an element	Unsorted Array	`O(n)`
	Sorted Array	`O(log n)` with Binary Search
	Hash Table	`O(1)` O(1) average; O(n) worst case
2. Insert an element	Array, append at end	`O(1)` amortized
	Linked List, at head	`O(1)`
	Array, at beginning	`O(n)`
3. Find min / max	Unsorted Array	`O(n)`
	Sorted Array	`O(1)` for the first/last element
	Heap	`O(1)` for min in a min-heap, or `O(1)` for max in a max-heap

Common Big O Complexities

For a more detailed explanation of Big O Notation, see our Big O Notation description.

Big O	Name	Growth	Example
`O(1)`	Constant	Constant time	Access an array element by index
`O(log n)`	Logarithmic	Very slow growth	Binary Search
`O(n)`	Linear	Grows linearly	Traverse an array
`O(n log n)`	Linearithmic	Grows slightly faster than linear	Merge Sort, Heap Sort
`O(n²)`	Quadratic	Grows fast	Bubble Sort, checking all pairs
`O(2ⁿ)`	Exponential	Grows very fast	Subset generation
`O(n!)`	Factorial	Grows extremely fast	Generating all permutations, brute-force Traveling Salesman