Array is one of the basic data structures that almost exists in every programming language. I believe every developer knows how to use it, but rarely does someone understand how and why it is structured that way.
In most programming languages, the index of the array starts with 0. But do you ever wonder why doesn’t it start with 1?
Let’s try figuring it out starting from the basic definition of the Array.
Array is a linear list data structure that uses one set of continuous memory space to store one set of data with the same type.
Some key terms need to be addressed first.
Linear List
A linear list refers to a data structure where the data is aligned like a line. Data on a linear list has only two directions, forward and backward. Some other examples of the linear list include LinkedList, Queue, Stack.
On the contrary, a non-linear list is a data structure that has more than two directions, such as a Binary tree, a Graph.
Continuous Memory Space & Same Type of Data
These two aspects provide a powerful feature to the array: random access, including random read and random write. However, this powerful feature could dramatically slow the performance during some operations. For example, when trying to insert/delete an element, to maintain the continuous, a large amount of data movement needs to be performed.
Speaking of random access, do you know how that’s been done?
For example, I create an array of length 5 containing numbers.
let array = [1,2,3,4,5];Let’s assume the variable is not optimized out in memory space in Javascript and each number takes 4 bytes. The system will assign 4 * 5 memory storage to this array. Assuming the memory starts at 1000 , we have the following graph:
As we know, computer will allocate one address for every unit of memory space, and the computer will use the address to access the data stored in the corresponding memory space. When we need to ‘random access’ one element in the array, the computer will use the following equation to calculate the address we are looking for :
array[i]_address = base_address + i * data_type_size
Based on the above example, base_address is 1000. Then if we take a look at the memory space, index 0 means the data is sitting exactly at the base_address. Index 1 means sitting at one element behind, which means 1 offset. From this, we could say the index of an array is the offset of the address based on the base_address.
However, if we count the index starting from 1, the address finding equationwill become:
array[i]_address = base_address + (i -1) * data_type_size
As we can see, the equation will perform one extra minus calculation. Since the array is a really basic data structure, we need to make sure to keep it performing at the best efficiency.
Another possible reason why we start the array index with 0 is interesting. It might be a historical reason. The designer of C uses 0 to start the array index. Then the programming languages invented after that all use the same design, trying to lower the learning barrier for C developers. Some programming languages do not use 0 to start the array index, such as Matlab, and some languages such as python also allows negative array index.
