Array. Data Structures.

Array is one of popular data structures. Array is a fixed size structure that can hold same data type elements, e.g. integers in specific order. If you are a PHP engineer this definition might be a bit weird for you as php have a bit another (believe me more weird) understanding of arrays.

Elements in array are indexed which means you can easily access random element by using its index. So, array looks like:

[1, 3, 4, 2, 9]

The size of array is number of elements. Here we have 5 elements, so the size is 5

Elements indexing goes from 0 and each element can be accessed by its index. So 0 element in this example is 1, 1st is 3, 4th is 9.

Why do we need arrays?

Obvious question. Why do we need them if we have other structures? What benefits? Let’s take a look

• They allow us to process multiple values easily and quickly
• Searching value and sorting is easier in arrays
• Good for storing multiple values in one variable
• Use to build other data structures

Searching and sorting is one of main benefits in arrays.

Array operations and complexity

• Update – updates element by its index
• Traversal – go through the elements and print them
• Search – find an element in array using its index or value

There are also operation like Insert, Delete, but we assume arrays are fixed size. For this operations you need to create another array with another size in order to add or remove element. There is option to create big arrays and replace unused elements with some placeholder, but it’s really not efficient.

Complexity of each operation:

• Access – O(1)
• Insert – O(n)
• Update – O(n)
• Search – O(n)

There are some different variations of arrays as 2-dimensional matrix or 3-dimensional. So, in 2-d every element is array. As you understand you are not limited in dimensions except some memory restrictions.

See also: Stack data structure