Arrays: Read, Insert Operations - Part One
Previous Read: Data Structures: Arrays
Reading from Array
To read an individual element from an array, we can choose the position we want to access via an index. In most programming languages, reading or accessing elements of an array involves retrieving the value at a specific index. An array (or list in Python) is an indexed data structure, so accessing any element by its index is usually an O(1) operation.
Because each index of arr is mapped to a RAM address, accessing a single element in an array is always instant. Despite the size of the input array, accessing a single element takes the same amount of time. This operation is considered O(1) in terms of time complexity.
As shown in the image below, an array of integers is represented in memory in the following manner. A specific memory address is assigned to each element of the array, and these addresses increase in multiples of 4 because integers occupy four bytes on average. Additionally, the image shows that each array element has a pointer to its memory address (ptr_), and the array is stored consecutively in memory. The visualization explains how arrays are stored in contiguous memory blocks, how memory addressing works, and how data type size affects memory allocation.
Insert at the end of the array
We can insert an element at the end of the array by placing it in the next available position at the index equal to the array's current length, where the size represents the total number of elements in the array. Inserting an element at the end of an array has a time complexity of O(1), assuming that the array has sufficient capacity. O(1) time complexity is because the insertion involves placing the new element at the following available index without shifting any existing elements.
Insert at a given index in an array
When you add an element to an array at a specific index, all the elements from that index onwards get shifted one position to the right. This shift is necessary to create space for the newly added element at the specified index. For example, if we insert index 2 in an array of 5 elements, the elements currently at indices 2, 3, 4, and 5 must all move one step right to indices 3, 4, 5, and 6, respectively.
Time Complexity
O(n), where n is the number of elements in the array.
In the worst-case scenario, inserting an element at the beginning of the array necessitates shifting all subsequent elements, leading to a time complexity proportional to the array's size.
On average, inserting an element anywhere other than at the end requires shifting a portion of the array. Therefore, the overall complexity remains O(n).