- A static Array is a fixed length containing n elements indexable from the range [ 0 , n - 1 ].
- Storing and accessing sequential data
- Temporarily storing objects
- Used by 10 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
| / | 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 ) |
- 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 ]
Q : How can we implement a dynamic array ?
- One way is to use a static array !
- Create a static array with an initial capacity .
- Add element to the underlying static array, keeping track of the of elements.
- If adding another element will exceed the capacity, then create a new static array with twice the capacity and copy the original element into it.
Source Code Explain in the video start in ( 00:27:40 )