GOTO All What In The Hell Articles
Arrays are one of the two fundamental data structures in computer science (the other is the tree). An array is a contiguous (uninterrupted or sequential) block of memory that stores a set of elements.
Elements in an array can be accessed by their index. An array’s index usually starts at 0 and stops at the number of elements in the array minus 1. The diagram below shows an array of the characters in the string “HELLO”.
In the array above the element at index 0 is the character “H”, the element at index 1 is the character “E” and so on.
Arrays have constant time access to the elements stored within. This means that it takes the same amount of time to access any element. For example, it would take the same amount of time to access the last element of an array as it would the first, or even an element in the middle.
A multi-dimensional array is simply an array of arrays. A spreadsheet is a form of multi-dimensional array. The diagram above shows a 3 element array where each element is also a 3 element array. Multi-dimensional arrays can be used for a variety of tasks from tracking pieces on a chess board to drawing graphics on the screen.
A “true” multi-dimensional array is implemented as a contiguous block of memory, just like the regular array. However it is also common practice to implement multi-dimensional arrays as trees.
Code
C
An array in C can contain elements of only one type/size and is not resizable.
/* Create an array */
int a[3] = {5, 10, 15};
/* Access an array element */
a[1] /*==> 10 */
Python
An array in Python is called a list. It can contain elements of any type/size and is resizable.
# Create an array a = [5, 10, 15] # Access an array element a[1] #==> 10
Scheme
An array in Scheme is called a vector. It can contain elements of any type/size and may be resizable.
;; Create an array (define a (vector 5 10 15)) (define b #(5 10 15)) ;; Access an array element (vector-ref a 1) ;;==> 10
What is the index?
An index is a way of labeling elements in an array. The first element is usually located at index 0, the second at index 1, the third at 2 and so on. The index is used to calculate the address of the element.
To understand this we have to remember that an array is just a reserved block of memory. Let’s look at a simple diagram of how the memory in your computer is organized.
Each block of memory can hold one value (usually equal to an integer in a language like C). To create an array we reserve a block of memory big enough to hold all our elements. If we had 4 elements it would look like the diagram below.
To access our array we only need to keep around the address of the beginning of our reserved space or 102 in this example. This address is equal to the index 0. But our index values still don’t point us at the right addresses yet. To do that we multiply the index by the size of an element then add that value to the start of our array. Let’s see how that maps out on our array.
Sometimes elements in an array are larger than just one block of memory. Here is what an array looks like when each element is two blocks of memory large.
An array can only contain elements of one size. This is because we need to multiply the index by the size of the elements in the array. How then do some languages let you put elements in an array that are different sizes? One simple way to do that is to use the size of the largest element in the array for indexing. This leads to some wasted space when storing smaller elements but allows the array to work just like before.
How do we know when we’re at the end of the array? One way is to store the length of the array with the address to the first element. In that case we just check if the index is <= the length. Another way to signal the end of an array is a sentinel node. A sentinel node is a value that can only occur at the end of an array and signals the end.
Performance
Indexing: O(1)
Insertion/Removal: O(n)
Search: O(n)
Arrays are either static or dynamic. A static array is set at a fixed size, elements can be inserted and removed but the array cannot grow or shrink. A dynamic array, on the other hand, can grow or shrink. Dynamic arrays are often initialized to be larger than the set of elements it contains. When enough elements are added to the array, such that the number of elements is greater than the array size, the array must be resized. Resizing an array could be a costly operation if the array is large or the act of copying is slow.
Pointless Programming 