Array
Arrays are fundamental data structures that store elements in contiguous memory locations. They are essential for organizing data and enabling efficient access.
In this section, we will explore two types of arrays:
- Static arrays
- Dynamic arrays.
1. Static Arrays
Static arrays have a fixed size, determined when the array is created. The size cannot be changed during the program's execution.
Key Characteristics:
- Memory Allocation: Allocated in contiguous memory blocks.
- Fixed Size: The size is set during initialization and cannot be modified.
public class Solution {
public static void main(String[] args) {
int[] staticArray = new int[5]; // Fixed size array (Static Array)
// Initializing elements
staticArray[0] = 10;
staticArray[1] = 20;
staticArray[2] = 30;
staticArray[3] = 40;
staticArray[4] = 50;
// Accessing an element (O(1))
System.out.println("Element at index 2: " + staticArray[2]); // O(1)
// Updating an element (O(1))
staticArray[2] = 35; // O(1)
System.out.println("Updated element at index 2: " + staticArray[2]);
// Linear search (O(n))
int target = 40;
boolean found = false;
for (int i = 0; i < staticArray.length; i++) {
if (staticArray[i] == target) {
System.out.println("Element found at index " + i); // O(n)
found = true;
break;
}
}
if (!found) {
System.out.println("Element not found.");
}
}
}
Time Complexity Analysis
- Access:
, as we can access array elements using its index. - Linear Search:
– Each element may need to be checked to find a value. - Binary Search:
– For sorted arrays, halves the search space each step. - Sorting:
– Efficient sorting algorithms (like merge sort) take time.
Space Complexity Analysis
- Space Complexity:
, where nis the number of elements in the array. - Auxiliary Space:
since no additional space is used other than the array itself.
2. Dynamic Arrays
Dynamic arrays, unlike static arrays, grow in size as new elements are added. They start with an initial capacity, and when this capacity is exceeded, the array resizes—typically doubling its size. This resizing process involves copying all existing elements into a new, larger array.
Creating Dynamic Arrays in Different Languages
Dynamic arrays are handled differently across programming languages. Here’s how to create them in popular languages:
| Language | Dynamic Array Type | Initialization |
|---|---|---|
| Python | list | arr = [] |
| Java | ArrayList | ArrayList<Integer> arr = new ArrayList<>(); |
| JavaScript | Array | let arr = []; |
| C++ | std::vector | std::vector<int> arr; |
| C# | List<T> | List<int> arr = new List<int>(); |
| Go | slice | arr := []int{} |
Key Characteristics
- Resizable: Automatically resizes when the capacity is reached.
- Amortized Time Complexity:
- Append Operation:
on average, but during resizing.
- Append Operation:
- Memory Allocation:
- When resizing occurs, a new array double the size of the original is created, and existing elements are copied over.
import java.util.ArrayList;
public class Solution {
public static void main(String[] args) {
ArrayList<Integer> dynamicArray = new ArrayList<>(); // Dynamic Array
// Adding elements to the end (Append operation) (O(1) amortized)
dynamicArray.add(10); // O(1) amortized
dynamicArray.add(20);
dynamicArray.add(30);
// Accessing an element by index (O(1))
System.out.println("Element at index 1: " + dynamicArray.get(1)); // O(1)
// Insertion at the start (O(n))
dynamicArray.add(0, 5); // O(n) due to shifting
System.out.println("Array after inserting 5 at start: " + dynamicArray);
// Insertion at the end (O(1) amortized)
dynamicArray.add(40); // O(1) amortized
System.out.println("Array after appending 40: " + dynamicArray);
// Deletion from the start (O(n))
dynamicArray.remove(0); // O(n) due to shifting
System.out.println(
"Array after deleting element from start: " + dynamicArray
);
// Deletion from the end (O(1))
dynamicArray.remove(dynamicArray.size() - 1); // O(1)
System.out.println(
"Array after deleting element from end: " + dynamicArray
);
// Linear search (O(n))
int target = 30;
boolean found = false;
for (int i = 0; i < dynamicArray.size(); i++) {
if (dynamicArray.get(i) == target) {
System.out.println("Element found at index " + i); // O(n)
found = true;
break;
}
}
if (!found) {
System.out.println("Element not found.");
}
}
}
Time Complexity Analysis
- Access by Index:
– Direct access to elements by index is constant time. - Insertion at the End: Average
, Worst – Appending is usually quick, but resizing may require . - Insertion at the Beginning or Middle:
– Elements need shifting to make space. - Deletion at the End:
– Removing the last element doesn’t require shifting. - Deletion at the Beginning or Middle:
– Elements shift to fill the gap after deletion. - Linear Search:
– Each element may need to be checked to find a value. - Binary Search:
– For sorted arrays, halves the search space each step. - Sorting:
– Efficient sorting algorithms (like merge sort) take time.
Space Complexity Analysis
- Auxiliary Space for Resizing:
- When a dynamic array reaches its capacity, it doubles in size, leading to a temporary overhead of
during the copy operation.
- When a dynamic array reaches its capacity, it doubles in size, leading to a temporary overhead of
Arrays are efficient for accessing elements by index but can be costly for insertions and deletions in the middle. Dynamic arrays add flexibility by resizing automatically, but resizing operations are more memory-intensive. Different programming languages provide built-in data structures to handle dynamic arrays efficiently, allowing developers to manage growing data seamlessly.
🤖 Don't fully get this? Learn it with Claude
Stuck on Array? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Array** (DSA) and want to truly understand it. Explain Array from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Array** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Array** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Array** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.