Data Structures: Arrays
a guide into data structures and the most known related algorithms
In this article, I am explaining one of the most basic data structures, and I will be writing about other popular data structures in upcoming articles.
These articles assume our readers are familiar with the concept of data structures and why they are used in software development, and it will dive into the definition, the different types, implementations, and complexity of each data structure we are studying.
Definition
An array is typically a series of contiguous slots in memory used to store a group of elements. Typically those elements are of the same type such as strings, integers, or user-defined objects.
Arrays are usually used to provide easy access to data in runtime, and it allows the developer to sort and search this data easily.
Usage
1- Storing and accessing data
2- Temporarily storing objects
3- Buffers
4- lookup tables and inverse lookup tables
5- Return values when a function needs to return more than one value
6- Dynamic Programming to save the results in runtime and use them
Types
Arrays can be static or dynamic.
Static Array: follows the definition we gave above, it is a container of length n fix, containing elements indexed [0, n-1].
Dynamic Array: Can grow and shrink in size in runtime, which means we can add and remove elements. An easy way to implement a dynamic array is by using a static array of size N and every time the number of elements exceeds N we create a new array of size 2N (double the size), copy all the elements from the old array into the new array and repeat. To be successful, our algorithm needs to keep track of the size of the array and the number of elements.
Time Complexity
Different operations in an array have different time complexities. the table below shows the big O notation for the different possible operations in both static and dynamic arrays.
Arrays in different programming languages
Different languages use arrays with different syntax and have different properties/variables and helper methods.
Below I will show examples from different popular programming languages.
Some languages like Ruby, Python and Javascript offer functional to pop, shift, unshift… making their arrays more dynamic.
JAVA
In Java, the type of the elements inside the array is declared when creating an array.
String [] arrayOfStrings;
String [] arrayOfStrings = {“String1”, “String2”, “String3”};
Singular elements can be accessed by their respective index.
String firstStringFromArray = arrayOfStrings[0];
To know what is the size of the array Java offers the property length
int arraySize = arrayOfStrings.length;
For traversing the array elements, JAVA allows us to use loops with incrementing index or “for” that reads in the following example as for each element s of type string in arrayOfStrings do what is in the following block.
for( String s: arrayOfStrings){
//Do Something with s which is a different single element from the array //everytime.
}
C#
In C#, like in Java, you need to specify the type of elements to be stored in your array when declaring a new one.
int[] arrayOfIntegers;
int[] arrayOfIntegers = {100, 200, 300};
Singular elements are accessed by their indices, and the whole array can be traversed by using loops with an incrementing or decrementing index
foreach( int num: arrayOfIntegers){
//Do Something with num which is a different single element from the array //everytime.
}
For the size of an array, C# offers the property Length
int arraySize = arrayOfIntegers.Length;
Python
Python uses Lists for the same purpose as arrays, and we should note that it also allows us to store elements with different types in the same list.
arr1 = []
arr = [“String1”, “String2”, “String3”, 100, 200, 0.5]
Singular elements can be accessed by their respective index.
firstElementFromArray = arr[0]
To know what is the size of the array Python offers the function len()
arraySize = len(arr)
For traversing the array elements, Python offers its own version of foreach.
for item in arr:
# Do Something with item which is a different single element value from the #array everytime.
Ruby
Similar to Python, Ruby allows storing different types in the same array.
arr1 = []
arr2 = Array.new()
arr = [“String1”, “String2”, “String3”, 100, 200, 0.5]
Singular elements can be accessed by their respective index.
firstElementFromArray = arr[0]
To know what is the size of the array Ruby offers the properties length and count
arraySize = arr.length
size = arr.count
For traversing the array elements, Ruby offers the method each
arr.each { |element| #do something with element}
Javascript
Two ways to create arrays in Javascript
const arr0 = []
const arr = [“String1”, “String2”, “String3”]
Singular elements can be accessed by their respective index.
let firstStringFromArray = arr[0]
To know what is the size of the array Javascript offers the property length
let arraySize = arr.length;
For traversing the array elements, we can use loops with incrementing index or “forEach” that returns all the elements of an array one by one, and pass them to a callback method.
arr.forEach(element => //return something)
arr.forEach(el => { //block})
Popular programming patterns
Sliding window
The Sliding Window pattern is as its name implies, a formed window covering a number of elements and that slides through a given array. Depending on the problem that you are solving, sliding windows start from the first element and keep shifting right by one element and adjust the length of the window. In some cases, the window size remains constant and in other cases the sizes grows or shrinks.
Double pointers
Two pointers is an easy and effective technique which is typically used for searching pairs in a sorted array.
It requires two pointers one starting at the beginning of the array and the other one at the end.
Depending on the the problem we are solving, a condition determine which pointer moves toward the middle.
If the solution is found before the two pointers meet, then the two elements where the pointers are, are the solution we are looking for. Else this array doesn’t have what we are looking for.
Binary Search
A technique used to find a specific element in a sorted array.
The technique consists of comparing the middle value to the element we are targeting, if it is bigger then we repeat the comparison with the middle element of the subarray at the left side, if it is smaller we do it with the subarray at the right side. We keep repeating the process until we find our target element or until we prove our target element doesn’t exist in the array.
Conclusion
As we talk about arrays, keep in mind there are more data structures that help overcome different limitations that come with arrays.
We will be talking about those in future articles, along with their implementations and the most common coding patterns that help resolve their specific problems.
Stay tuned…
