Scribd
Upload
213 views15 pages

Static and Dynamic Arrays: William Fiset

The document discusses static and dynamic arrays, explaining that a static array has a fixed length while a dynamic array can grow and shrink in size by using an underlying static array and allocating a new larger array when the current one reaches capacity. Examples are provided of accessing, inserting, and deleting elements from static and dynamic arrays to illustrate their differences in complexity. Code snippets demonstrate implementing basic operations on arrays.

Uploaded by

Bena Ax
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
213 views15 pages

Static and Dynamic Arrays: William Fiset

The document discusses static and dynamic arrays, explaining that a static array has a fixed length while a dynamic array can grow and shrink in size by using an underlying static array and allocating a new larger array when the current one reaches capacity. Examples are provided of accessing, inserting, and deleting elements from static and dynamic arrays to illustrate their differences in complexity. Code snippets demonstrate implementing basic operations on arrays.

Uploaded by

Bena Ax
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Static and

Dynamic Arrays

William Fiset
Outline
• Discussion and examples about Arrays
• What is an Array?
• When and where is a Array used?
• Complexity
• Static array usage example
• Dynamic Array implementation details
• Code Implementation
Discussion and
examples
What is a static
Array?
A static array is a fixed length
container containing n elements
indexable from the range [0, n-1].

Q: What is meant by being ‘indexable’?

A: This means that each slot/index in the


array can be referenced with a number.
When and where is a
static Array used?
1) Storing and accessing sequential data

2) Temporarily storing objects

3) Used 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
Static Array Dynamic Array

Access O(1) O(1)

Search O(n) O(n)

Insertion N/A O(n)

Appending N/A O(1)

Deletion N/A O(n)


Static Array
A = 44 12 -5 17 6 0 3 9 100

0 1 2 3 4 5 6 7 8

Elements in A are referenced by their index.


There is no other way to access elements in
an array. Array indexing is zero-based,
meaning the first element is found in
position zero.
Static Array
A = 44 12 -5 17 6 0 3 9 100

0 1 2 3 4 5 6 7 8

A[0] = 44
A[1] = 12
A[4] = 6
A[7] = 9
A[9] => index out of bounds!
Static Array
A = -1 12 -5 17 6 0 3 9 100

0 1 2 3 4 5 6 7 8

A[0] = 44 A[0] := -1
A[1] = 12
A[4] = 6
A[7] = 9
A[9] => index out of bounds!
Static Array
A = -1 12 -5 17 6 18 3 9 100

0 1 2 3 4 5 6 7 8

A[0] = 44 A[0] := -1
A[1] = 12 A[5] := 18
A[4] = 6
A[7] = 9
A[9] => index out of bounds!
Static Array
A = -1 12 -5 17 6 18 25 9 100

0 1 2 3 4 5 6 7 8

A[0] = 44 A[0] := -1
A[1] = 12 A[5] := 18
A[4] = 6
A[6] := 25
A[7] = 9
A[9] => index out of bounds!
Operations on
Dynamic Arrays
Dynamic Array
The dynamic array can grow and
shrink in size.

A = 34 4

A.add(-7) A = 34 4 -7

A.add(34) A = 34 4 -7 34

A.remove(4) A = 34 -7 34
Dynamic Array
Q: How can we implement a dynamic array?
A: One way is to use a static array!

1) Create a static array with an initial


capacity.

2) Add elements to the underlying static array,


keeping track of the number of elements.

3) If adding another element will exceed the


capacity, then create a new static array with
twice the capacity and copy the original
elements into it.
Dynamic Array
Suppose we create a dynamic array with an
initial capacity of two and then begin
adding elements to it.

Ø Ø 7 Ø 7 -9

7 -9 3 Ø 7 -9 3 12

7 -9 3 12 5 Ø Ø Ø

7 -9 3 12 5 -6 Ø Ø

You might also like