“What sunshine is to flowers, arrays are to programmers. These are but trifles, to be sure; but scattered along programmer life’s pathway, the good they do is inconceivable.”
For a programmer, “array” is a loaded term. They are a way of life, the reason for many wars, and a beloved word that still hasn’t quite lost its power.
To a non-programmer, this is probably a little confusing.
Let’s start with its low-level array definition:
An array can be defined as the contiguous area of memory consisting of equal size elements indexed by contiguous integers.
Okay, this can’t be a non-programmer definition.
Don’t you worry. If you see the above definition, you’ll see I’ve written three terms in bold. I’ll explain each one individually in great detail.
A) Contiguous area of memory :
What purpose do index page in books serve?
If you can answer this question, you’ve covered first bolded term in above definition.
Mainly Two Purposes:
1) Each index title uniquely identifies book chapters
2) Makes accessing any chapter easily.
Similarly, our computer uses an abstraction called memory address which
- Uniquely identifies what information is stored in what byte.(If you’ve no idea about what bits/bytes are, I’ve covered all the nitty-gritty here.)
- Makes accessing data stored in the memory easier.
Thumb Rule: Each byte(made of 8 bits) is associated with a unique address.
Above diagram represents a designated memory address for each byte.
But have you met any person who randomly reads chapters from the book?
No, right, cuz it makes no sense. It has to be read sequentially(read: contiguous), just like how data is stored in the consecutive memory address in above diagram.
B) Equal size elements & Contiguous integers:
Data can be read easily based on memory address but programming languages prefer to associate their own identifier with the memory address.
Simple answer: For faster retrieval or storing of data.
A Dumb Vs Wise Move:
Problem Statement: I want to store each character of string called “SAMPLE”.
Dumb Move: You can define six different variables to store each character.
Wise Move: You can use a single group(read: array) and use identifiers(index numbers) to access individual characters.
Something like this.
Each character like S, A holds two bytes of memory individually and location which houses them are called a cell.
The integer index used in place of the memory address is known as zero-based indexing.(index starts with 0 so)
So, the cell of the array with index 4 has contents L and is stored in bytes 2154 and 2155 of memory.
What’s So Special About Arrays?
Random / Constant-Time Access
Constant time access to read and write to any particular element in an array.
Okay, whaaaat now?
Let me give you an example to simplify this. Arrays are stored in memory sequentially. So actually, when you access array you are telling the computer, “Get the memory address of the beginning of an array, then add 4 multiplied by the size of array elements to it, then access that spot.”
Let’s say we have to retrieve letter P from the above array.
We’ll use this formula to calculate the memory address where letter P lies.
Formulae : start_index + element_cell_size * index_of_element
For the above figure, we can see that start_index is 2146. Since each cell has unicode character, the element_cell_size is 2 bytes. Index of letter P is 3.
So address of letter P is 2146 + 2 * 3 = 2152
Since adding takes constant time so does array access!
Hence, arrays cost constant time, O(1), while accessing any element.
Of course, arithmetic calculations is handled for us. All we need to care about is this below high-level array abstraction i.e characters and their sequential indexes.
S A M P L E
0 1 2 3 4 5
- A group of related and equal sized variables can be stored one after another in a contiguous portion of the computer’s memory is known as an array.
- Reading and writing data in the array takes constant time i.e O(1)
- In a low-level array, each cell uses the same number of bytes.
Read All About Array On Steroids inspired by Comment on this blog post.