Array Patterns for DSA Mastery
Array Basics
What is an Array?
Think of an array as a row of connected boxes, each holding a single item. It's a fundamental way computers organize data. An array stores a collection of similar items, like a list of numbers, names, or temperatures, all under one name.
Each box in an array has a specific address, called an index. This index is a number that tells you the position of the box. In most programming languages, indexing starts at 0. So, the first item is at index 0, the second is at index 1, and so on. This zero-based indexing is a core concept you'll see everywhere in programming.
How Arrays Use Memory
The magic of an array comes from how it's stored in a computer's memory. All the elements of an array are placed in a single, unbroken block of memory. This is called contiguous memory allocation. It’s like having a row of houses on a street, where house #1 is right next to house #2, which is right next to house #3.
Because the items are stored together in a predictable way, the computer can find any element almost instantly. It doesn't need to search for it. If it knows where the array starts, it can calculate the exact memory address of any element just by using its index. This makes accessing elements by their index incredibly fast.
Basic Array Operations
Working with arrays usually involves a few common actions. Let's look at the three most fundamental operations: traversing, inserting, and deleting.
Traversal: Visiting every element in the array, one by one, from the beginning to the end.
Imagine you have a list of tasks for the day stored in an array, and you want to read through all of them. That's traversal. You start at index 0, look at the item, move to index 1, look at that item, and continue until you've seen every single one.
/* A simple loop to traverse an array */
for (int i = 0; i < array.length; i++) {
// Access the element at the current index
print(array[i]);
}
Insertion: Adding a new element to the array.
Adding an element to the end of an array is usually simple, assuming there's space. But what if you need to insert an element into the middle? Since all elements must be in a contiguous block, you first have to shift every element after the insertion point over by one spot to make room. This can be a slow process for large arrays.
Deletion: Removing an element from the array.
Deletion works in a similar but opposite way to insertion. When you remove an element from the middle of an array, you create a gap. To keep the memory contiguous, you must shift all the elements that came after it one position to the left to close that gap. Just like insertion, this can be inefficient for large arrays.
What is the primary characteristic of how data is stored in an array?
In a typical array with 10 items, what is the index of the very last item?
Arrays are a foundational data structure. Their simple, ordered nature makes them perfect for many tasks, but the cost of insertion and deletion is an important trade-off to remember.