loading...

Dynamic Arrays

jjb profile image JB Updated on ・1 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Resources

  1. Dynamic arrays overview
  2. Dynamic arrays overview and implementation
  3. Dynamic arrays implementation

Takeaways:

  • Dynamic Arrays resize when they reach capacity, usually by doubling.
  • Dynamic Arrays, for insertions, have a worse case Big O of O(n) (linear). But due to doubling, the amortized* time complexity of Dynamic Arrays is O(1) (constant).
  • A Dynamic Array's space complexity is at worst O(2n) (immediately after doubling), with O(n) being wasted space (the empty half of the array). Note: O(2n) in Big O is reduced to O(n) - therefore the space complexity of a Dynamic Array is O(n).

*Another way of saying average. Per Wikipedia:

amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm

Per Brilliant:

Often, a data structure has one particularly costly operation, but it doesn't get performed very often. That data structure shouldn't be labeled a costly structure just because that one operation, that is seldom performed, is costly.

So, amortized analysis is used to average out the costly operations in the worst case.

Here's the finished implementation with test code:

If you found any errors in this post, please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Nov 1 '19 by:

Discussion

markdown guide
 

Good tutorial JB. Looking forward to follow your posts. One point I would like to add though.

The operation Prepend can be done by calling AddAt(element, 0) method inside the Prepend method :)

 

Good catch, you are probably right!