Data Structure and Algorithms — Implement Dynamic Array in Python

Y Tech
Y Tech
Jul 13, 2020 · 2 min read

This is an introduction to dynamic array and its implementation

An array is a contiguous area of memory of equal-size elements. Array length is usually fixed, which means you need to specify the number of elements your array can hold ahead of time.

A dynamic array is an array which has an important feature: auto-resizing. With this feature, you can easily expand your array by adding more elements in it, so that you do not need to determine the size ahead of time.

In this tutorial, we will discuss about the implementation of dynamic array by using regular fixed length array.

Define Interfaces

Below is the thinking process for the design of dynamic array:

  1. Pre-Create an array with a given size (e.g. an array with size 10). All the elements in this pre-created array are Nulls.
  2. Use this pre-created array to represent our dynamic array. So now we have a dynamic array with size 0, and a potential maximum size of 10.
  3. When we want to append a new element into the dynamic array, we can keep assigning elements to the empty slots of the array, until the array is full.
  4. When the array is full, and we want to append more elements into the array, what we can do is: create a new array with a larger size (e.g. an array with size 20); then copy the 10 elements in the first array into the new array, and now we can use the new array to represent our dynamic array; now we have a dynamic array with size 10, and a potential maximum size of 20.

The main features we need for this dynamic array class include the followings:

  1. Get the length of the array
  2. Access an element in the array
  3. Append a new element to the array
  4. Pop the element from the end of the array

Python Implementation

BigO Analysis

  • Read/update an element in dynamic array — O(1)
  • Append in the end of dynamic array:
  1. If the size of the dynamic array is less than capacity: O(1)
  2. If the size of the dynamic array reached capacity: O(n) to copy the n elements into the new array; however, after this operation, the next n appends will have time complexity of O(1) each. So, the amortized time complexity is (O(n) + O(1) * n) / n = O(2) which is still constant

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store