Array Operations
Once you have an array, you need to perform operations like traversal, insertion, and deletion. Each operation has its own time complexity, which we must understand to write efficient code.
1. Traversal (iterate over elements)
Visiting every element – O(n) time.
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
// Enhanced for loop
for (int num : arr) {
System.out.println(num);
}
2. Insertion (at a given position)
Insertion at end: O(1) if space available. Insertion at arbitrary position requires shifting elements: O(n) in worst case.
// Insert at index pos (0-based)
public static void insert(int[] arr, int pos, int value) {
// Shift elements to the right
for (int i = arr.length - 1; i > pos; i--) {
arr[i] = arr[i-1];
}
arr[pos] = value;
}
3. Deletion
Deleting from the end: O(1). Deleting from arbitrary position requires shifting: O(n).
// Delete element at index pos
public static void delete(int[] arr, int pos) {
// Shift elements left
for (int i = pos; i < arr.length - 1; i++) {
arr[i] = arr[i+1];
}
// Last element is now duplicate; we can ignore it
}
Note: In Java, arrays have fixed size. The insert/delete operations shown assume we are using a logical size variable or we don't care about trailing elements.
Two Minute Drill
- Traversal: O(n).
- Insertion at end: O(1) (if space). Insertion at middle: O(n) due to shifting.
- Deletion from end: O(1). Deletion from middle: O(n).
- Understanding these complexities helps choose the right data structure.
Need more clarification?
Drop us an email at career@quipoinfotech.com