What is an Array in Computer Science?

by
Rate this post

In computer science, an array data structure consists of a collection of elements—usually of the same type such as integer or string. Each element is identified by an array index. Arrays are designed to allow extremely efficient access of individual elements by index: runtime complexity is constant with growing array size! The reason is that the element index is calculated from the element’s index tuple using a closed formula.

Array Video

Arrays in Computer Science -- A Conceptual NO-BS Intro

Array Definition

An array is an ordered collection of elements indexed by contiguous integers.

  • Ordered: The order of the elements is fixed and well-defined, unlike sets that are unordered.
  • Elements: An array consists of elements, in the vast majority of cases these elements are of the same type.
  • Contiguous indices: The indices start from 0 and increment by one for each subsequent element. All integers between 0 and n-1 point to exactly one element. There are no “holes” in the series of indices.

Array Applications

Arrays are widely used in all major programming languages such as C++, Java, and Python. For example, a search engine may store all URLs of crawled websites in an array. Subsequently, it can sort the URL alphabetically based on the array data structure. The array is often the data structure of choice to store data reliably and efficiently—allowing easy access of all data elements.

Here are some applications of arrays:

  • Arrays may implement mathematical vectors.
  • Arrays may implement multi-dimensional matrices.
  • Arrays are used to implement other data structures such as lists, sets, hash tables, stacks, and many more. These data structures, in turn, are used by every single non-trivial software program.
  • Arrays are used in adjacency lists and matrices to represent graph data structures. Here are some applications of graphs.
  • Arrays are used in CPU scheduling to create priority lists to determine which process to schedule next on the CPU.
  • Arrays are used by sorting algorithms such as Quicksort.

Array Runtime and Space Efficiency

Most programming languages store the array very efficiently in memory. For example, it places all elements into the same memory region, so that a large bunch of array values can be read at once from the memory.  

Here’s the runtime efficiency of an array for different operations:

OperationAverage Runtime ComplexityWorst-case Runtime Complexity
Access
O(1)O(1)
Search
O(n)O(n)
Insertion
O(n)O(n)
DeletionO(n)O(n)

As a rule of thumb: modifying the array is relatively expensive, while reading elements from the array is extremely cheap! The optimal usage pattern for arrays is to never change it and access individual elements frequently (“read-no-write”).

The space complexity of an array is O(n) for n elements: each element requires an explicit memory location. Thus, more array elements lead to more space requirements. However, the relationship grows proportionally, not faster, with increasing number of elements: double the elements require double the space.

Array Indexing

You can access each element in the array via indices.

  • The index of the first array element is 0.
  • The index of the second element is 1.
  • The index of the i-th element is i-1.  

As the first array index is usually the integer 0, most computer scientist refer to it as zero-based indexing.

Here’s a Python example of array indexing using an array of strings:

>>> authors = ['Rowling', 'King', 'Brown', 'Peterson']
>>> authors[0]
'Rowling'
>>> authors[1]
'King'
>>> authors[2]
'Brown'
>>> authors[3]
'Peterson'

Array Methods in Python

Note that Python only implements the list data type in the standard library. If you want to use arrays, you’ll need to import the NumPy library. However, the list data type is used very similar to the array data type in other programming languages, so we use it interchangeably here.

These are the most important array/list methods in Python:

MethodDescription
array.append(x)Appends element x to array.
array.clear()Removes all elements from array–which becomes empty.
array.copy()Returns a copy of array. Copies only the array, not its elements (shallow copy).
array.count(x)Counts the number of occurrences of element x in array.
array.extend(iter)Adds all elements of an iterable iter (e.g. a list) to array.
array.index(x)Returns the position (index) of the first occurrence of value x in array.
array.insert(i, x)Inserts element x at position (index) i in array.
array.pop()Removes and returns the final element of array.
array.remove(x)Removes and returns the first occurrence of element x in array.
array.reverse()Reverses the order of elements in array.
array.sort()Sorts the elements in array in ascending order.

When to Use Arrays?

In practice, you have to decide whether to use a linked list or an array to store a sequence of data values. Use arrays when you need fast access to elements and lists when you dynamically need to grow or shrink the sequence.  

Strengthen Your Coding Skills

References