What is a static array?
A static array is a fixed length container containing n elements indexable from the range $[0, n-1]$.
What is meant by being indexable? This mean that each slot/index in the array can be referenced with a number.
When and where static array use?
- Storing and accessing sequential data.
- Temporarily storing objects.
- User by IO routines as buffers.
- Lookup tables and inverse lookup tables.
- Can be used to return multiple values from a function.
- Used in dynamic programming to cache answers to subproblems.
Complexity
| Action | Static Array | Dynamic Array |
|---|---|---|
| Access | $O(1)$ | $O(1)$ |
| Search | $O(n)$ | $O(n)$ |
| Insert | - | $O(n)$ |
| Append | - | $O(1)$ |
| Delete | - | $O(n)$ |
Static Array
The length of static array is fixed, and the array index starts with 0.
Dynamic Array
The dynamic array can grow and shrink in size.
Code
Python
code:
array = [5, 41, -1, 26, -9]
# access
print(array[0])
# search
print(array.index(26))
# insert
array.insert(1, 20)
print(array)
# append
array.append(17)
print(array)
# delete by value
array.remove(-9)
print(array)
# delete by index
array.pop(3)
print(array)
output:
5
3
[5, 20, 41, -1, 26, -9]
[5, 20, 41, -1, 26, -9, 17]
[5, 20, 41, -1, 26, 17]
[5, 20, 41, 26, 17]
Golang
code:
package main
import "fmt"
func Search(a []int, num int) int {
for i, n := range a {
if n == num {
return i
}
}
return -1
}
func Insert(a []int, idx int, num int) []int {
a = append(a, 0)
copy(a[idx+1:], a[idx:])
a[idx] = num
return a
}
func Remove(a []int, num int) []int {
for i, n := range a {
if n == num {
return append(a[:i], a[i+1:]...)
}
}
return a
}
func Pop(a []int, idx int) []int {
for i := range a {
if i == idx {
return append(a[:i], a[i+1:]...)
}
}
return a
}
func main() {
array := []int{5, 41, -1, 26, -9}
// access
fmt.Println(array[0])
// search
fmt.Println(Search(array, 26))
// insert
array = Insert(array, 1, 20)
fmt.Println(array)
// append
array = append(array, 17)
fmt.Println(array)
// delete by value
array = Remove(array, -9)
fmt.Println(array)
// delete by index
array = Pop(array, 3)
fmt.Println(array)
}
output:
5
3
[5 20 41 -1 26 -9]
[5 20 41 -1 26 -9 17]
[5 20 41 -1 26 17]
[5 20 41 26 17]
Dynamic Array
code:
package main
import "fmt"
func main(){
array := []int{}
array = append(array, 5)
fmt.Println(array, len(array), cap(array))
array = append(array, 41)
fmt.Println(array, len(array), cap(array))
array = append(array, -1)
fmt.Println(array, len(array), cap(array))
array = append(array, 26)
fmt.Println(array, len(array), cap(array))
array = append(array, 9)
fmt.Println(array, len(array), cap(array))
}
output:
[5] 1 1
[5 41] 2 2
[5 41 -1] 3 4
[5 41 -1 26] 4 4
[5 41 -1 26 9] 5 8