Array Operations in Data Structures

Understanding Array Operations

Arrays are useful because they provide a structured way to store and process collections of elements. Once an array has been created, programs commonly perform operations such as accessing, traversing, inserting, deleting, updating, and searching.

The performance of these operations is important when choosing an array for a particular problem. Some operations, such as accessing an element by index, are typically very efficient, while inserting or deleting elements from the middle may require other elements to be shifted.

const numbers = [10, 20, 30, 40, 50];

console.log(numbers[2]); // Access
numbers[2] = 35;         // Update

numbers.push(60);        // Insert
numbers.pop();           // Delete

for (const number of numbers) {
  console.log(number);   // Traverse
}

1. Accessing an Array Element

Accessing means retrieving an element using its index. Because the index identifies the element's position, accessing an element in a typical array is an O(1) operation.

const languages = ['JavaScript', 'Python', 'Java', 'C#'];

console.log(languages[0]); // JavaScript
console.log(languages[2]); // Java

JavaScript arrays use zero-based indexing, so the first element is at index 0 and the last element is at index array.length - 1.

2. Traversing an Array

Traversal means visiting each element in an array, usually from the first element to the last. Traversal is commonly required when every element needs to be processed.

const scores = [85, 90, 78, 92];

for (let i = 0; i < scores.length; i++) {
  console.log(scores[i]);
}

If an array contains n elements, visiting every element takes O(n) time.

3. Inserting Elements

Insertion adds a new element to an array. The cost depends on where the new element is inserted. Adding an element at the end of a dynamic array is typically efficient, while inserting near the beginning or middle may require existing elements to move.

Insert at the End

const numbers = [10, 20, 30];

numbers.push(40);

console.log(numbers);
// [10, 20, 30, 40]

For a dynamic array, adding at the end is generally O(1) amortized. Occasionally, the underlying storage may need to grow, making an individual operation more expensive.

Insert at the Beginning

const numbers = [20, 30, 40];

numbers.unshift(10);

console.log(numbers);
// [10, 20, 30, 40]

Elements already in the array may need to be shifted to create space at the beginning. Therefore, this operation is typically O(n).

Insert in the Middle

const numbers = [10, 20, 40, 50];

numbers.splice(2, 0, 30);

console.log(numbers);
// [10, 20, 30, 40, 50]

Inserting into the middle can require shifting subsequent elements, so its typical complexity is O(n).

4. Deleting Elements

Deletion removes an element from an array. Similar to insertion, the cost depends on the element's position.

Delete from the End

const numbers = [10, 20, 30, 40];

const removed = numbers.pop();

console.log(removed); // 40
console.log(numbers); // [10, 20, 30]

Removing the last element is typically O(1).

Delete from the Beginning

const numbers = [10, 20, 30, 40];

const removed = numbers.shift();

console.log(removed); // 10
console.log(numbers); // [20, 30, 40]

Removing the first element requires the remaining elements to shift their positions, making the operation typically O(n).

Delete from the Middle

const numbers = [10, 20, 30, 40, 50];

numbers.splice(2, 1);

console.log(numbers);
// [10, 20, 40, 50]

Removing an element from the middle can require shifting later elements, so the typical complexity is O(n).

5. Updating an Element

Updating means replacing the value stored at a particular index. Since the index directly identifies the position, updating an element is typically an O(1) operation.

const scores = [80, 75, 90];

scores[1] = 85;

console.log(scores);
// [80, 85, 90]

6. Searching an Array

Searching is the process of finding whether a particular value exists in an array or determining its position.

If the array is not sorted and no additional indexing structure is available, a search may need to inspect each element. This is called linear search and has a typical complexity of O(n).

const numbers = [10, 25, 30, 45, 50];

const index = numbers.indexOf(30);

console.log(index); // 2

When an array is sorted, a binary search can reduce the search time to O(log n), provided the algorithm and data meet the requirements for binary search.

7. Finding the Length of an Array

The length property returns the number of elements in a JavaScript array.

const users = ['Alice', 'Bob', 'Charlie'];

console.log(users.length); // 3

The last valid index is always one less than the array length:

const users = ['Alice', 'Bob', 'Charlie'];

const lastIndex = users.length - 1;

console.log(lastIndex);      // 2
console.log(users[lastIndex]); // Charlie

8. Copying an Array

JavaScript provides several ways to create a new array containing the elements of another array. The spread operator is a common approach.

const original = [10, 20, 30];

const copy = [...original];

copy.push(40);

console.log(original); // [10, 20, 30]
console.log(copy);     // [10, 20, 30, 40]

This creates a shallow copy of the array. If the array contains objects or other nested structures, those referenced values are not deeply cloned.

9. Combining Arrays

Multiple arrays can be combined to create a larger collection. The spread operator provides a simple way to concatenate arrays.

const frontend = ['HTML', 'CSS', 'JavaScript'];
const backend = ['C#', 'Python'];

const technologies = [...frontend, ...backend];

console.log(technologies);
// ['HTML', 'CSS', 'JavaScript', 'C#', 'Python']

Array Operation Complexity

Understanding complexity helps determine whether an array is suitable for a particular workload.

Why Element Shifting Matters

The main reason insertion and deletion can be expensive is that an array maintains element positions. When an element is added or removed from the beginning or middle, later elements may need to move so that the indexes remain consistent.

Before:

[10, 20, 30, 40]

Insert 15 at index 1:

[10, 15, 20, 30, 40]

20, 30, and 40 move one position to the right.

This shifting behavior is why the location of an insertion or deletion is important when analyzing array performance.

Choosing the Right Array Operation

The appropriate operation depends on what the application needs to do most frequently. Arrays are particularly effective when indexed reads and updates are common.

• Use indexed access when you already know the element position.
• Use traversal when every element needs to be processed.
• Use push() when adding elements at the end.
• Use pop() when removing elements from the end.
• Use splice() when insertion or deletion at a particular index is required.
• Use searching algorithms based on whether the data is sorted and how often searches occur.

Common Mistakes

• Assuming every array operation is O(1).
• Forgetting that indexes start at zero.
• Using shift() or unshift() repeatedly for large arrays without considering their cost.
• Confusing an array's length with its last index.
• Using linear search when the data and problem allow a more suitable search strategy.
• Ignoring the cost of shifting elements during middle insertions and deletions.

Key Takeaways

• Array operations include access, traversal, insertion, deletion, updating, and searching.
• Indexed access and updates are typically O(1).
• Traversing an array requires O(n) time.
• Insertion and deletion at the beginning or middle typically require O(n) time because elements may need to shift.
• Adding to or removing from the end is generally efficient.
• Understanding operation complexity helps you choose the right data structure for a problem.