Data Structure (1) - Dynamic and Static Array

• What is a static array?
• When and where static array use?
• Complexity
• Static Array
• Dynamic Array
• Code
  • Python
  • Golang
  • Dynamic Array

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?

1. Storing and accessing sequential data.
2. Temporarily storing objects.
3. User by IO routines as buffers.
4. Lookup tables and inverse lookup tables.
5. Can be used to return multiple values from a function.
6. 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