Introduction to Data Structures
dsa.fetehadin.com1.1 What Is a Data Structure?
A data structure is a way of organising data in memory so the operations you need are fast. Learn how they are classified and what makes a good one.
| Array: read item i | O(1) |
| Array: insert at the front | O(n): shift everything |
| Linked list: insert at the front | O(1) |
| Linked list: read item i | O(n): walk from the head |
- ✗Calling a stack "non-linear". Stacks and queues are linear; only trees and graphs are non-linear here.
- ✗Saying an array is dynamic. A C++ array has a fixed size;
vectorand linked lists are dynamic. - ✗Confusing a data structure (how data is stored) with an algorithm (the steps that use it).
1.2 ADTs & Abstraction
An Abstract Data Type says WHAT operations exist; a data structure says HOW they are built. Separating the two is the key idea of this course.
| push / pop / top (array implementation) | O(1) |
| push / pop / top (linked implementation) | O(1) |
| Maximum size | array: fixed · linked list: limited only by memory |
- ✗Saying an ADT "is" an array. An ADT has no storage details at all; an array can only implement one.
- ✗Listing implementation details (like
topindex) as part of the ADT's definition. - ✗Forgetting error conditions. "pop on an empty stack is an error" IS part of the ADT.
1.3 Arrays & 2-D Arrays (Review)
Arrays store items side by side in memory, which is why reading any index is instant. 2-D arrays are stored row by row.
| Access a[i] | O(1) |
| Search (unsorted) | O(n) |
| Insert / delete at position i | O(n): shift items |
| Insert / delete at the end | O(1) if there is space |
| Traverse an R × C matrix | O(R·C) |
| Space | O(n) for n items |
- ✗Using 1-based indexes. C++ arrays start at 0, so the last valid index is n − 1.
- ✗Writing
a[n](out of bounds). C++ does not check, so it silently corrupts memory. - ✗Using
sizeof(a)/sizeof(a[0])inside a function. There,ais a pointer, so the trick gives the wrong size. Passninstead.
- Data structure:
- A way of organising data in memory so that the operations you need are efficient.
- Primitive data structure:
- Built-in types operated on directly by the machine: int, char, float, bool, pointers.
- Linear data structure:
- Items form a sequence, each with at most one predecessor and one successor: arrays, linked lists, stacks, queues.
- Non-linear data structure:
- Items branch or connect freely: trees and graphs.
- Static vs dynamic:
- Static structures have a size fixed when they are created (arrays); dynamic ones grow and shrink at run time (linked lists).
- ADT (Abstract Data Type):
- A description of data plus the operations on it, saying what they do but not how they are implemented.
- Abstraction:
- Hiding implementation details behind an interface so users only see what they need.
- Row-major order:
- How C++ stores a 2-D array: row 0 first, then row 1. Address of a[i][j] = base + (i·cols + j)·size.