Data Structures and Algorithms - Class Notes
Lecture 1: Introduction to Data Structures
What are Data Structures?
Data structures are ways of organizing and storing data in a computer so that it can be
accessed and modified efficiently. They provide a means to manage large amounts of data for
uses such as large databases and internet indexing services.
Types of Data Structures
Linear Data Structures
Arrays: Fixed-size sequential collection of elements
Linked Lists: Dynamic collection where elements point to the next element
Stacks: Last In First Out (LIFO) structure
Queues: First In First Out (FIFO) structure
Non-Linear Data Structures
Trees: Hierarchical structure with nodes
Graphs: Collection of vertices connected by edges
Hash Tables: Key-value pair storage with hash function
Big O Notation
Understanding algorithm efficiency:
O(1) - Constant time
O(log n) - Logarithmic time
O(n) - Linear time
O(n²) - Quadratic time
Arrays Deep Dive
Advantages:
Fast access to elements by index
Memory efficient
Cache friendly due to locality
Disadvantages:
Fixed size in most languages
Insertion/deletion can be expensive
Practical Examples
# Array implementation
arr = [1, 2, 3, 4, 5]
print(arr[2]) # Access: O(1)
# Dynamic array (Python list)
dynamic_arr = []
dynamic_arr.append(10) # Insertion: O(1) amortized
Assignment for Next Class
1. Implement a basic array class
2. Compare time complexities of different operations
3. Research real-world applications of arrays
Next Lecture: Linked Lists and Memory Management
