[go: up one dir, main page]
Scribd
Upload
58 views15 pages

Arrays

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. It provides examples of using static arrays by indexing elements and details how a dynamic array can be implemented using a static array underneath, dynamically allocating more space when needed by creating a new static array with double the capacity and copying elements over. The complexity of different array operations is also summarized.

Uploaded by

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

Arrays

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. It provides examples of using static arrays by indexing elements and details how a dynamic array can be implemented using a static array underneath, dynamically allocating more space when needed by creating a new static array with double the capacity and copying elements over. The complexity of different array operations is also summarized.

Uploaded by

d ponnapalli
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

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
iscussion and example
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