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.
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.
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:
|Operation||Average Runtime Complexity||Worst-case Runtime Complexity|
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.
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 'Rowling' >>> authors 'King' >>> authors 'Brown' >>> authors '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:
|Appends element |
|Removes all elements from |
|Returns a copy of |
|Counts the number of occurrences of element |
|Adds all elements of an iterable |
|Returns the position (index) of the first occurrence of value |
|Inserts element |
|Removes and returns the final element of |
|Removes and returns the first occurrence of element |
|Reverses the order of elements in |
|Sorts the elements in |
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.
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.