CS Data Structures: 2D Array
Exordium
An array is a collection of objects. An array is one of the most frequently used data types in software development. The most fundamental type of array is a linear array, also known as a one-dimensional array. The objects in an array are accessed by their index within the array. Arrays start at index zero, meaning that if there are two items in an array, the indices of those items will be 0 and 1, respectively.
An array can perform actions such as appending an item, removing an item, and inserting an item at a specific index. In most programming languages, the size of the array can be obtained by calling something similar to array.count or array.length.
When using an array, the object types must be the same. In a statically typed language (like Swift), if an array holds different object types, an error will be thrown, indicating the array can not be heterogeneous.
In a dynamically typed language, different types can technically be stored in an array. That said, it would be odd to have an array named fruits that holds the names of fruits and the name of animals (or random numbers). It’s up to the programmer to ensure that they are structuring arrays correctly and with data that is related.
Linear arrays aren’t the only type of arrays. Some different types of arrays are two-dimensional, fixed-size, and ordered arrays; each has its use case. Also, note that any non-two-dimensional arrays are inherently one-dimensional.
Two-Dimensional (2D) Array
A 2D Array may be used for something such as laying out a grid or board. To access an element in a 2D Array, there are two indices that are used. The first being the column, the second being the row. In C and Objective-C, the following line can be written to create a two-dimensional array that is essentially a three by four grid with 12 items (bees):
int bees[3][4];To access the bee located in column 2, row 3:
bees[2][3];This way of creating a 2D Array is not applicable in all languages. For example, in Swift, a custom data structure must be built using a generic type. The generic type must contain the number of columns and rows, as well as a one-dimensional array. The 2D Array will use this one-dimensional array under the hood to store the data. A custom subscript will also have to be created, as the two-dimensional array needs a way to get and set the values. (Please note that the exact implementation of this data structure will be different in a language other than Swift).
2D Array in Swift
The 2D Array is implemented as a structure in Swift. In Swift, a structure is a value type, meaning the values are not shared between instances of the structure, as they would be in a class.
public struct Array2D<T> { // 1. public let columns: Int public let rows: Int private var array: [T]
// 2. public var count: Int { return array.count }
// 3. public init(columns: Int, rows: Int, initialValue: T) { self.columns = columns self.rows = rows array = .init(repeating: initialValue, count: columns * rows) } }
Here’s a breakdown of the above code:
- Create properties that store the number of columns, rows, and the array used to store data. This array must be of the generic type; otherwise, it won’t store whatever type of data is passed through.
- Return the number of objects in the array.
- Initialize the two-dimensional array with the number of columns, rows, and values to be stored in the array.
Within the initializer, the private array is initialized:
array = .init(repeating: initialValue, count: columns * rows)It’s a simple implementation of an array that stores the initialValue as many times as the count parameter specifies. In the following code, the 2D Array is initialized with three columns and four rows, which equates to 12 items total that are all 0.
var bees = Array2D<Int>(columns: 3, rows: 4, initialValue: 0)To view the array:
print(bees)// Array2D<Int>(columns: 3, rows: 4, array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
There is currently no way to change or retrieve the values in the array. An array needs to be able to do these things in order to be used in any way; otherwise, there is data stored in memory that will never be used.
A subscript method must be added to the Array2D struct to enable the indexing of items. Here is the subscript, which will expect a column and row:
public subscript(column: Int, row: Int) -> T { get { precondition(column < columns, “Column Index (\(column)) is out of range. Array<T>(columns: \(columns), rows: \(rows))”) precondition(row < rows, “Row Index (\(row)) is out of range. Array<T>(columns:\(columns), rows:\(rows))”) return array[row*columns + column] } set { precondition(column < columns, “Column Index (\(column)) is out of range. Array<T>(columns: \(columns), rows: \(rows))”) precondition(row < rows, “Row Index (\(row)) is out of range. Array<T>(columns:\(columns), rows:\(rows))”) array[row*columns + column] = newValue }}
This custom subscript allows the programmer to get and set values in the array based on column and row numbers.
The get method checks two conditions before returning the value. These checks are called preconditions, and they are used to ensure a condition is true before making further progress within the program. A precondition takes two parameters — the condition that needs to be checked and result in being true, and the message to be printed if the condition is false. If the condition is true, the value requested is returned. The value requested is calculated by taking the row requested and multiplying it by the total number of columns, then adding the column requested. (When I say ‘requested,’ I’m talking about row and column passed into the subscript).
The setter method uses the same preconditions and then sets the object’s value at the index using the same row*columns + column formula.
Here is the full 2D Array data structure:
public struct Array2D<T> { // 1. public let columns: Int public let rows: Int private var array: [T] // 2. public var count: Int { return array.count } // 3. public init(columns: Int, rows: Int, initialValue: T) { self.columns = columns self.rows = rows array = .init(repeating: initialValue, count: columns * rows) }
public subscript(column: Int, row: Int) -> T { get { precondition(column < columns, “Column Index (\(column)) is out of range. Array<T>(columns: \(columns), rows: \(rows))”) precondition(row < rows, “Row Index (\(row)) is out of range. Array<T>(columns:\(columns), rows:\(rows))”) return array[row*columns + column] } set { precondition(column < columns, “Column Index (\(column)) is out of range. Array<T>(columns: \(columns), rows: \(rows))”) precondition(row < rows, “Row Index (\(row)) is out of range. Array<T>(columns:\(columns), rows:\(rows))”) array[row*columns + column] = newValue } }}
Obtaining the Item at The Index Provided
Using row*columns + column to obtain the index may be a bit confusing, but remember, the Array2D struct uses a one-dimensional array under the hood. To demonstrate how this works, I’ve added some graphics. To keep with the same pattern, this array will have three columns and four rows.
The initialization of the array is as followed:
var bees = Array2D<Int>(columns: 3, rows: 4, initialValue: 0)print(bees)
// Array2D<Int>(columns: 3, rows: 4, array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
Visually, this looks something like:
Notice that the rows and columns are zero-based indices. To change the value of the objects located at [0, 0] and [1, 2] (column, row), the subscript is used:
bees[0, 0] = 1
bees[1, 2] = 5print(bees)
// Array2D<Int>(columns: 3, rows: 4, array: [1, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0])
The 5 gets placed where it is because of the row*columns + column formula. Imagine the rows as 1,0,0 being the first row, 0,0,0 being the second row, 0,5,0 as the third, and 0,0,0 as the fourth. When row*columns is multiplied, the object in front of the requested object is obtained. Then, adding column ensures the index is moved to the correct column. If the column is 0, the index doesn’t move.
In the case of setting bees[1, 2] = 5, when row*columns is calculated within the subscript, the index lands on [0, 2] , the 6th index of the array. This is because 2 (row) x 3 (the total number of columns) equals 6.
Then, by adding column , the index is moved to column ‘1’ and the index is now 7, instead of 6. Which means the value of the index is now 5. In the visualization below, the arrows between the boxes represent the progression of the index through the array.
To retrieve the value of an index, the subscript is used. It uses the same row*columns + column formula as the setter. Getting and setting are O(n) operations.
let firstBee = bees[0, 0]print(firstBee)
// 1let seventhBee = bees[1, 2]print(seventhBee)
// 5
Remove Objects
In this implementation, there are two ways to remove objects. Either by removing the last object in the array or removing an object based on its column and row.
public mutating func removeLast() { array.removeLast()}
public mutating func removeAt(column: Int, row: Int) { array.remove(at: row*columns + column)}
The Final Structure
Here’s what the entire 2D Array data structure looks like in Swift:
public struct Array2D<T> { public let columns: Int public let rows: Int private var array: [T] public var count: Int { return array.count }
public init(columns: Int, rows: Int, initialValue: T) { self.columns = columns self.rows = rows array = .init(repeating: initialValue, count: columns * rows) }
public subscript(column: Int, row: Int) -> T { get { precondition(column < columns, “Column Index (\(column)) is out of range. Array<T>(columns: \(columns), rows: \(rows))”) precondition(row < rows, “Row Index (\(row)) is out of range. Array<T>(columns:\(columns), rows:\(rows))”) return array[row*columns + column] }
set { precondition(column < columns, “Column Index (\(column)) is out of range. Array<T>(columns: \(columns), rows: \(rows))”) precondition(row < rows, “Row Index (\(row)) is out of range. Array<T>(columns:\(columns), rows:\(rows))”) array[row*columns + column] = newValue } }
public mutating func removeLast() { array.removeLast() }
public mutating func removeAt(column: Int, row: Int) { array.remove(at: row*columns + column) }}
Stopping Point
That is all for the 2D Array. This data structure is one that stores objects in a grid-like fashion and can be used for things such as drawing applications and laying out sprites in a 2D game. Accessing elements is a bit slower than a regular array, which has a constant time complexity. The time complexity of accessing and adding elements in a 2D Array is linear.
You can view the code that goes along with this post on GitHub.
Thank you for reading!
