Array Flashcards
What is an Array?
One of the simplest and most basic data structures.
It can:
- hold a fixed number of elements of the same type
- elements occupy a contiguous memory block
Used as:
- a basis for other (more complex) data structure
When we create a new array we have to specify two things:
- the type of the elements in the array
- the maximum number of elements that can be stored in the array
(capacity of the array)
The memory occupied will be the capacity * the size of one element.
Is a static structure: once the capacity of the array is specified, you cannot add or delete slots from it (you can add and delete elements from the slots, but the number of slots, the capacity, remains the same).
The array itself is memorized by the address of the first element.
If array indexing starts from 0:
Address of the ith element = address of array + i * size of an element
If array indexing starts from 1:
the above formula is stil valid, but with i-1 instead of i
Advantages & Disadvantages Array
Advantages:
- any element of the array can be accessed in constant time (Θ(1)), because the address of the element can simply be computed
Disadvantage:
- we need to know/estimate from the beginning the number of elements:
- if the capacity is too small: we cannot store every element we want to
- if the capacity is too big: we waste memory
What is an Iterator?
What is an Dynamic Array?
An Array whose size can grow or shrink, depending on the number of elements that need to be stored in the array.
Dynamic Arrays:
- are still arrays
- elements are still kept at contiguous memory locations
- we still have the advantage of being able to compute the address of
every element in Θ(1) time.
For a DA e need the following fields:
- cap: denotes the number of slots allocated for the array (it's capacity) - len: denotes the actual number of elements stored in the array - elems: denotes the actual array with capacity slots for TElems allocated
DynamicArray:
cap: Integer len: Integer elems: TElem[]
What is the Resize operation for a Dynamic Array?
When the value of len = the value of capacity, we say that the array is full.
Resize is usually performed before an insert operation:
- if more elements need to be added, the capacity of the array is increased
(usually doubled) and the array is resized
- during the resize operation a new, bigger array is allocated &
the existing elements are copied from the old array to the new one
Optionally, resize can be performed after delete operations as well:
- if the dynamic array becomes ”too empty”,
a resize operation can be performed to shrink its size
(to avoid occupying unused memory)
Obs:
After a resize operation the elements of the Dynamic Array will still occupy a contiguous memory zone, but it will be a different one than before
How do dynamic arrays in other programming languages grow at resizing:
- C++ - multiply by 1.5 (initially 1, then 2, 3, 4, 6, 9, 13, etc.)
- Java - multiply by 1.5 (initially 10, then 15, 22, 33, etc.)
- Python - multiply by ≈ 1.125 (0, 4, 8, 16, 25, 35, 46, 58, etc.)
- C# - multiply by 2 (initially 0, 4, 8, 16, 32, etc.)
Is Dynamic Array a DS or an ADT?
Dynamic Array is a data structure, it describes:
- how data is actually stored in the computer
(in a single contiguous memory block)
- how it can be accessed and processed
- it can be used as a representation to implement different abstract data
types
However, Dynamic Array is so frequently used that in most programming languages it exists as a separate container as well.
The Dynamic Array is not really an ADT, since it has one single possible implementation, but we still can treat it as an ADT, and discuss its interface.
What is the domain of an ADT Dynamic Array?
Domain
DA = {da | da = (cap, len, e1e2e3…elen), cap, len ∈ N, len ≤ cap, ei is of type TElem}
What are the operations on an ADT Dynamic Array?
What is an ADT Dynamic Array Iterator?
