A fixed (or fixed-size, fixed-length) array is an array that has a max amount of items. Such arrays are used when the programmer knows how many elements an array should hold — such as the number of enemy spaceships a game should display on-screen at once or the value of an 8-bit character.
Some languages, such as C, Objective-C, and C++, use fixed arrays, while more modern languages use arrays that aren’t set in size. In a language that uses fixed arrays, once you set the size of the array — it does not change. For example, if a fixed array is initialized with 15 elements, the array can not store 16 elements. Though the array is incapable of growth, it is capable of mutation. With the first 15 elements, if the 14th element needed to be changed, it could be. If an element needs to be deleted, it can be; the fixed-size of 15 can hold less than 15 elements; it just can’t hold more.
Below is an array in C++ that holds 15 integers. The elements of the array are placed in a contiguous block of memory:
int foo ;
When working with fixed arrays, it’s important to be precise and understand why you’re using this type of array. They leave room for overflow errors and are generally not a flexible data structure. That said, the good thing about these types of arrays is that they are predictable and fast. You know what to expect regarding the number of elements stored in the array and how large the array is in memory.
Fixed Array Operations
Fixed arrays should be able to:
- Append new elements to the end
- Insert new elements at the beginning and in the middle
- Delete elements
- Look up elements by index
- Count the size of the array
Appending an element to the end of a fixed array is easy as long as the array isn’t full. Again, the size of a fixed array does not change after it is set. This operation has a time complexity of O(1). Another quick operation is finding an element by the index, also a constant time complexity. To continue on the topic of time complexity, inserting and deleting are expensive with a fixed array. If an element is being inserted in the middle or beginning of a fixed array, all the elements to the right of the new element must be moved up a position in memory by 1.
To add the number 5 to a fixed array:
Something to note; if there is code that references an object of the array using an index, and a new element is added into the middle of the array, the indexes no longer reference the correct objects.
Furthermore, deleting an element from the array is the same process, but reversed. The elements are moved one position to the left instead of the right.
To delete the number 5 from the same array:
Both inserting and deleting elements from a fixed array results in linear time complexity — O(n).
How to Build a Fixed Array
Here, Swift is used to build a fixed array, though the concept can be used in any language.
The Fundamental Properties
The first thing to do is create the fixed array, its basic properties, and an initializer. The array needs the following properties:
- A max size to ensure it doesn’t grow past what the use case needs.
- A default value (this will be used to add an item to the array when needed).
- An internal array (in this case, it’s a Swift array).
- The count (which is updated each time an element is removed or added to the array).
- Two public properties that return information. The first being the elements within the array, and the second being the length of the array.
countis not directly used to return the array’s length (e.g.,
fixedArray.count) because it is private. It is private because in this use case, tracking the amount of elements in an array with a counter and then reading the
countproperty is faster than directly calling the internal
countmethod on the array; which traverses through each element, then returns the number of elements in the array.
The initializer sets the max amount of elements to be allowed in the array, along with the ‘default value’ of the array.
defaultValue is used to add a default object to the array when appending new objects. This will be seen in the
The other thing to add in the Swift implementation of a Fixed Array is a custom subscript. In Swift, you can add custom subscripts to Structs, Classes and Enumerations in order to access the elements of a collection, list or sequence.
When a fixed array is initialized, it is empty. This can be seen by using the
Adding Functionality to the Array
As noted in the Fixed Array Operations section of this article, fixed arrays should be able to:
- Append new elements to the end.
- Insert new elements at the beginning and in the middle.
- Delete elements.
- Look up elements by index.
- Count the size of the array.
It is important to note that any time an element is added or removed, the count variable must be updated in accordance with this action.
The first custom method will be named
appendToEnd() and it will do just that — add an element to the end of the array. Before the method adds the element, it uses
assert to make sure
count is less than
maxSize . If
count is greater than the total amount of allowed elements, no more elements can be added to the array. To learn more about using assert in Swift, check out the official Apple Documentation.
Next, inserting elements in the middle and beginning of the array. There are a few things to keep in mind when writing this method.
The array has the chance to hold different variations when adding new elements. It may be empty; it may be full; it may be half full, etc. Also, the index where an element needs to be added may be different each time the method is used.
In this instance, the method checks for the following cases then proceeds to handle the insertion accordingly:
indexis 0, and the
countproperty is 0. The array is empty, and the element needs to be inserted at the beginning, as the very first element in the array.
countis equal to
indexis 0 OR the
countis equal to
indexis not equal to 0. The array is full, and the element needs to be inserted at the beginning, or somewhere in the middle or end. This ensure that no new elements are added to the array when trying to insert them when the array is full.
indexis 0, and
countis not equal to
maxSize. In this case, the requested element needs to be inserted at the beginning, shifting the current elements to the right in order to make room for the new element. This is accomplished by appending a new default element to the end of the array, traversing through the elements starting at index 1, moving through the reversed version of the elements in the array, and moving them one space to the right. Remember that the value of
indexin this instance is 0, which ensures that the loop starts with the second element; leaving the new element in place at the 0th index of the array.
- In all other cases, the array will do the same thing as case 3 above, except the loop doesn’t start at index 0. In this case, the loop starts at the given value of
index. A visualization of this can be seen earlier in this article; under the Fixed Array Operations section.
The Fixed Array now looks like this:
To start adding elements to the array, use either the
insert methods. Here, the integers 1, 2 and 3 are added to the end of the array. Then, 5 is inserted at the 3rd index, 6 is inserted at the 4th index, and 4 is inserted at the 3rd index. The array ends up holding
[1, 2, 3, 4, 5, 6] .
Now that the array can have elements added to it, there needs to be a way to remove these elements. There are three ways to remove items in a fixed array:
- Remove the element at the end of the array.
- Remove the item based on a given index.
- Remove all of the items in the array.
To delete an item from the end, simply make sure that
count is greater than 0, use the
removeLast method on the array and decrement 1 from
Removing an element based on a given index is a bit trickier. The
index must be less than or equal to 0, and it must also be less than the value of
count. After these assertions pass,
count is decremented by 1, the element at the given index is obtained in
result and the
remove function of the Swift array is called with index as its parameter. Finally, the element that is stored in
result is returned.
Below is the usage of these two methods. The
deleteFromEnd method does not return the element that is removed, but the
removeAt method does. How they are used is up to the programmer.
The final ‘delete’ method is one that removes all of the elements from the array. The method loops through the value of
count, removes the last element and decrements
count by 1. Once it processes the array, it then sets
count to 0.
Again, the usage of this method:
The methods seen here can be changed to whatever use-case the programmer may have, but they perform the basic actions that a Fixed Array should be able to perform.
One thing that needs to be seen is the usage of the subscripts. It was mentioned earlier, but hasn’t been used in code yet.
Custom Subscript in a Fixed Array
Custom subscripts work the same way as regular subscripts. The difference is that you define what is returned when using the subscript. When an element needs to be accessed in a Fixed Array, (or other custom data type), it’s accessed by using brackets —
When defining a custom subscript in Swift, a return type must be defined. This is expected, as subscripts return elements. Here is the subscript again:
[1, 2, 3, 4, 5, 6] . Here is how an element would be accessed:
The Complete Fixed Array in Swift
That is it for the Fixed Array. This data structure can be implemented in any language, and the use case is up to the programmer. A Fixed Array can be used for situations such as tracking the number of enemies on screen in a game, creating a representation of a byte (bytes are a storage unit in computing and are made up of 8 bits. Bits are the smallest unit used for storage on a computer), or limiting the number of family members that a user can add to their family account of a subscription.
Below is the complete Fixed Array in Swift, using a generic type:
Thank you for reading. If you’re looking for more articles about computer science and software engineering, give these a read: