Photo by Oskar Yildiz on Unsplash

A Comprehensive Guide For Array Data Structure

Let’s Explore Array Data Structures.

An array can stores elements in contiguous memory locations in a ram. So, you are thinking now what do I mean by contiguous memory locations. But before that, let’s see how memory works.

When we run a program, our computer keeps the variables or data, and it stores it in RAM. Ram is more like a bookshelf, where each block holds a data of one byte(8 bits), and every block has a number. That number is the location of the memory. In actuality, the numbers are in the hexadecimal form.

RAM is connected to the processor with the help of a memory controller. Memory Controller has direct access to each block. That’s why our ram is fast. It can access any location instantly, that’s why it’s called Random Access Memory.

Memory Organization

So let’s talk about what do I mean by contiguous in an array. Variables in an Array are stored in contiguous memory locations. If we want to store five elements and each one has a size of 4 bytes then it will store 20 bytes data in continuous location, for example, if we have locations from 0 to 30 and locations from 0 to 19 are empty then it will store the data to from position 0 to 19.

If there is no space between the given location, then it will search for the next place where it can store that much amount of data continuously.

In Array, each position has an index, and it starts at 0. If we have ten elements in an array, then the index will start from the last index at 9. The index always ends at the n-1th position, where n is the length of the Array. See the below example for more information.

Pros and Cons Of Array Data Structure

Pros:

1. Reading Elements from an array is Fast and efficient.
2. Adding an element into an array is fast.
3. And Array is the foundation of many data structures.

Cons:

1. Linear Complexity at the time of insertion and deletion
2. The Array has a fixed size (not talking about Dynamic Array and Python and Javascript like languages)

Different Operations on Arrays and Their Time Complexity

Time Complexity Of Array Data Structure for Different Operations

Time Complexity of Array Data Structure For Different Operations

To learn more about time complexity check out our article on Time Complexity And Big O Notation

A Comprehensive Guide for Time Complexity and Big O Notation

So, let’s talk about how to perform different operations on an array.

Insertion

We can insert an element into an array based on the requirement. We can insert an item into the Array at the beginning, at the end, or a given index. The time complexity of adding data at the end is O(1). To add an element at the beginning of the given index, we have to move other items by one index.

Checkout example:

We are using python. You can use any programming language; the concepts are going to be the same.

lst = ['a', 'b', 'c', 'd', 'g', 'h', 'i', 'j']
lst.insert(4, 'e')
print(lst)

Output:

['a', 'b', 'c', 'd', 'e', 'g', 'h', 'i', 'j']

Insertion In An Array

Deletion

We can delete an element in an array from the beginning, from a given index or end of the Array. Removing from the end is the best case. Because deleting an element from the end, we have only one step, and its time complexity is O(1).

Deletion from the beginning is the worst case because we have to move all the elements towards the start after deleting an item from the beginning. Check the given an example for more information.

lst = ['a', 'b', 'c', 'd', 'e', 'g', 'h', 'i', 'j']
lst.remove('e')
# del lst[4]
print(lst)

Output

['a', 'b', 'c', 'd', 'g', 'h', 'i', 'j']

Searching:

In searching, if the element is available at the beginning, then time complexity will be O(1). It’s the best case for Searching Operation in an array. If data is available at the end of the range, then we can say it’s the worst case for the Array, and time complexity will be O(n).

In a sorted array, we can use binary searching to search the element.

Example:

lst = ['a', 'b', 'c', 'd', 'e', 'f']
elem_to_search = imput('Enter an element to search: ')
idx = 0
for elem in lst:
    if elem == elem_to_search:
        print(f'elem found at index: {idx}')
        break
    idx += 1

Output:

Enter an element to search: 'e'
elem found at index: 4

Pythonic way to search:

lst = ['a', 'b', 'c', 'd', 'e', 'f']
elem_to_search = imput('Enter an element to search: ')
idx = lst.index('e')
print(f'element found at index: {idx}')

Output:

Enter an element to search: 'e'
element found at index: 4

Explore searching algorithms in more depth:

Learning Search Algorithms

And If you want to learn about REST API then check out

Writing Your First REST API