Array Data Structure

Introduction

Arrays are a type of data structure in which elements of the same data type are sorted in contiguous memory locations. Arrays are among the most primitive and most important data structures in computer programming. We use arrays all the time in almost every program. They productively utilize the addressing logic of computers as in most modern computers and external storage devices, the memory is in the form of a one-dimensional array of words.

According to Wikipedia, In computer science, an array data structure, or simply an array, is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula.[1][2][3] The simplest type of data structure is a linear array, also called one-dimensional array.

For example, an array of 10 32-bit (4-byte) integer variables, with indices 0 through 9, may be stored as 10 words at memory addresses 2000, 2004, 2008, ..., 2036, (in hexadecimal: 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) so that the element with index i has the address 2000 + (i × 4).

The memory address of the first element of an array is called first address, foundation address, or base address. More theoretical info - click here

Basic Terms of An Array Data Structure

In arrays, an element refers to a particular item that is stored. Each element carries an index, a location with respect to a base value. The base value is the memory location of the first element of the array. We simply add offsets to this value which makes it easier for us to use the reference and identify items.

Array length – The number of elements an array can store is defined as the length of the array. It is the total space allocated in memory while declaring an array.

We can just write the items in order, separated by commas and enclosed by square brackets. Thus,

[1, 4, 17, 3, 90, 79, 4, 6, 81]
        

is an example of an array of integers. If we call this array a, we can write it as:

a = [1, 4, 17, 3, 90, 79, 4, 6, 81]
        

This array a has 9 items, and hence we say that its size is 9. In everyday life, we usually start counting from 1. When we work with arrays in computer science, however, we more often (though not always) start from 0. Thus, for our array a, its positions are 0, 1, 2, . . . , 7, 8. The element in the 8th position is 81, and we use the notation a[8] to denote this element. More generally, for any integer i denoting a position, we write a[i] to denote the element in the ith position. This position i is called an index (and the plural is indices). Then, in the above example, a[0] = 1, a[1] = 4, a[2] = 17, and so on.

It is worth noting at this point that the symbol = is quite overloaded. In mathematics, it stands for equality. In most modern programming languages, = denotes assignment, while equality is expressed by ==. We will typically use = in its mathematical meaning, unless it is written as part of code or pseudo code. We say that the individual items a[i] in the array a are accessed using their index i, and one can move sequentially through the array by incrementing or decrementing that index, or jump straight to a particular item given its index value. Algorithms that process data stored as arrays will typically need to visit systematically all the items in the array, and apply appropriate operations on them.

Types of Array Data Structure

One-dimensional array

It is a linear data structure in which elements are stored in adjacent memory locations. (For example, there are multiple coaches connected to each other in a train.)

The formula for finding the memory location of a particular element ‘n’ is:

Address(Array [n] = Base Address(Array)+ Wordlength*(Lowerbond – n)

Where;

• Address – memory location of the Nth element
• Wordlength – number of bytes required to store one element. It depends upon the data type – a character requires 1 byte and an integer value needs 2 bytes.
• Lowerbond – index of the first element of the array
• Base Address – Address of the first element of the array.

Declaring a 1D Array

Usually, an array is declared by mentioning the type name, followed by the variable name and the array’s size at the end.

type arrayName [ arraySize ];

//Array Declaration in C++

Int Numbers [10];        

Two-dimensional Array(Multi-Dimensional)

As the name suggests, a two-dimensional array is made up of rows and columns. The above-mentioned chessboard is a perfect example of 2D arrays.

We can calculate the size of a 2D array data structure by multiplying the number of rows and columns.

Similar to how we define a cell in Excel or address a seat in a multiplex, the position of elements in 2D arrays is defined by using two subscripts – the row number and the column number.

Declaring a 2D Array

We’ll follow the same process as a 1D array except we’ll add another dimension to the size of the array. So, declaring a 2D array with 10 rows and 8 columns will be as follows-

Int Numbers [10][8]        

Three-dimensional Array(Multi-Dimensional)

A 3D array is simply a collection of 2D arrays.

Just like we studied in mathematics, we add height or depth to the two-dimensional array to get a three-dimensional array. So, the maximum number of elements in a 3D array of dimensions – [5*4*3] = 60

Let’s understand this better. Suppose, you have 8 cards/bricks and you have to place them in 3 different setups

1. You can lay all 8 of them flat in a row (1D array)
2. You can divide them into groups of 4 each and make a new column right beside them.
3. Or you can place 4 at the bottom in 2 rows and 2 columns and then place the other 4 over them to add another dimension making it a 3D array.

3D arrays are recognized using three subscripts – row size, column size, and block size. 

      Masai School provides courses in web/software development and helps students get placed in high-end software jobs. 

      Check out the Full Stack Web Development course and master programming at no initial fees with Income Share Agreement.

Loops and Iteration

The standard approach in most programming languages for repeating a process a certain number of times, such as moving sequentially through an array to perform the same operations on each item, involves a loop. In pseudo code, this would typically take the general form

For i = 1,...,N

do something,        

and in programming languages like C, C++ and Java this would be written as the for-loop

for( i = 0 ; i < N ; i++ ) {

// do something

}        

in which a counter i keep tracks of doing “the something” N times. For example, we could compute the sum of all 20 items in an array a using

for( i = 0, sum = 0 ; i < 20 ; i++ ) {

sum += a[i];

}        

We say that there is iteration over the index i. The general for-loop structure is

for( INITIALIZATION ; CONDITION ; UPDATE ) {

REPEATED PROCESS

}        

in which any of the four parts are optional. One way to write this out explicitly is

INITIALIZATION

if ( not CONDITION ) go to LOOP FINISHED

LOOP START

REPEATED PROCESS

UPDATE

if ( CONDITION ) go to LOOP START

LOOP FINISHED        

In these notes, we will regularly make use of this basic loop structure when operating on data stored in arrays, but it is important to remember that different programming languages use different syntax, and there are numerous variations that check the condition to terminate the repetition at different points.

Invariants

An invariant, as the name suggests, is a condition that does not change during execution of a given program or algorithm. It may be a simple inequality, such as “i < 20”, or something more abstract, such as “the items in the array are sorted”. Invariants are important for data structures and algorithms because they enable correctness proofs and verification. In particular, a loop-invariant is a condition that is true at the beginning and end of every iteration of the given loop. Consider the standard simple example of a procedure that finds the minimum of n numbers stored in an array a:10

minimum(int n, float a[n]) 

float min = a[0];

// min equals the minimum item in a[0],...,a[0]

for(int i = 1 ; i != n ; i++) 
{

// min equals the minimum item in a[0],...,a[i-1]

        if (a[i] < min) min = a[i];

}

// min equals the minimum item in a[0],...,a[i-1], and i==n

 return min;

}        

At the beginning of each iteration, and end of any iterations before, the invariant “min equals the minimum item in a[0], ..., a[i − 1]” is true – it starts off true, and the repeated process and update clearly maintain its truth. Hence, when the loop terminates with “i == n”, we know that “min equals the minimum item in a[0], ..., a[n − 1]” and hence we can be sure that min can be returned as the required minimum value. This is a kind of proof by induction: the invariant is true at the start of the loop, and is preserved by each iteration of the loop, therefore it must be true at the end of the loop. As we noted earlier, formal proofs of correctness are beyond the scope of these notes, but identifying suitable loop invariants and their implications for algorithm correctness as we go along will certainly be a useful exercise.

Advantages of Arrays

• In arrays, we can store a large number of elements that can be defined by a single line of code rather than naming each variable separately. Thus, it helps in the readability and re usability of the code.
• We can access any random element in arrays by using the index number. Thus, the time complexity to access any element in an array is constant, unlike stacks where one has to start from the top to access the bottom elements.
• There’s no need for the allocation of extra memory as arrays distribute memory in contiguous memory locations. This prevents memory overflow. Moreover, we can also allocate memory dynamically in an array.
• We can easily create new sub-arrays within a given array.
• Since arrays are the most basic data structures, they can be used to implement other data structures such as stacks, queues, graphs, linked lists, etc.
• Functions such as finding maximum and minimum values or implementing searching and sorting algorithms are easier to perform in an array.

Limitations of Arrays

Shifting – Insertion and deletion processes are tricky in arrays. If we want to keep the elements ordered and insert a new element in its correct position or remove it, then we’ll need to move other elements (half of the elements on average).

Fixed Size – Arrays are static structures. Once the size of an array is declared, it cannot be increased or decreased.

We must know the correct number of elements in the correct order before allocating memory otherwise there would be either shortage or wastage of memory.

• Inability to store different data types

As we’ve discussed earlier, arrays can only contain homogeneous elements.

It’s fine as long as you keep all eggs in the carton, one of them hatches and it’s not an array anymore.

So, an integer array will only contain integers, similarly, a character array will only have characters.

Exception – An Array in Javascript can contain different types of elements including strings, integers, or even other arrays. So, we can store a number in the first position, a string in the second, and so on as shown in the table below.

References

To be added later