Arrays and Strings are the most fundamental data structures in computer science. They are the starting point for almost every technical interview and competitive programming journey.
Arrays: Contiguous Memory
An Array is a collection of elements stored in contiguous memory locations. This proximity allows for constant time O(1) access to any element via its index.
Key Characteristics
- Fast Access: accessing
arr[i]is instantaneous. - Fixed Size: traditional arrays have a fixed length determined at creation.
- Deletion/Insertion Cache: inserting or deleting from the middle requires shifting elements, resulting in O(n) time.
Strings: Arrays of Characters
In most languages, a String is essentially an array of characters. However, their immutability (in languages like Java or Python) means that every "modification" creates a new string object.
The Standard Library Advantage
Mastering string manipulation often involves knowing your language's standard library:
- Reverse / Substring
- Splitting / Joining
- Character encoding awareness
Complexity Analysis
| Operation | Time Complexity |
|---|---|
| Access | O(1) |
| Search (Unsorted) | O(n) |
| Insertion (at end) | O(1) / O(n) amortized |
| Deletion (at index) | O(n) |
"Memory is a sandbox; arrays are the grid."