Understanding Dynamic Arrays: Implementation and Insights

Introduction

Have you ever wondered how Python’s list effortlessly expands when you add elements? Unlike static arrays, which have a fixed size, dynamic arrays adjust their capacity automatically. This ability is crucial in data structures and algorithm optimization.

In this week's blog post, I’ll walk through the implementation of a simplified dynamic array, discuss its challenges, and reflect on what I learned. Understanding how dynamic arrays work under the hood strengthens problem-solving skills and enhances efficiency when writing Python programs.

Python’s built-in list functions as a dynamic array, handling memory reallocation internally. However, manually implementing a dynamic array offers insights into how resizing, insertion, and deletion work at a lower level.

Key Features of Our Dynamic Array Implementation

• ✔ Supports append(), insert(), delete(), get(), and resize()
• ✔ Uses low-level memory allocation with ctypes to mimic a C-like array
• ✔ Dynamically expands when full by allocating a new array with double capacity

Part 1: Implementing a Dynamic Array

Below is the Python implementation of a simplified dynamic array. This implementation supports basic operations like append(), insert(), delete(), and resize(). It also dynamically grows or shrinks based on the number of elements, mimicking how Python's list works under the hood.

Python Implementation

import ctypes

            class DynamicArray:
                """A simplified dynamic array similar to Python's list.
            
                Features:
                - Dynamically resizes when full by doubling its capacity.
                - Shrinks when less than 25% full.
                - Supports append(), insert(), delete(), __getitem__().
                """
            
                def __init__(self):
                    self._n = 0
                    self._capacity = 1
                    self._A = self._make_array(self._capacity)
            
                def __len__(self):
                    return self._n
            
                def __getitem__(self, k):
                    if not 0 <= k < self._n:
                        raise IndexError("Index out of bounds")
                    return self._A[k]
            
                def __repr__(self):
                    return "[" + ", ".join(str(self._A[i]) for i in range(self._n)) + "]"
            
                def append(self, obj):
                    if self._n == self._capacity:
                        self._resize(2 * self._capacity)
                    self._A[self._n] = obj
                    self._n += 1
            
                def insert(self, k, value):
                    if not 0 <= k <= self._n:
                        raise IndexError("Index out of bounds")
                    if self._n == self._capacity:
                        self._resize(2 * self._capacity)
                    for i in range(self._n, k, -1):
                        self._A[i] = self._A[i - 1]
                    self._A[k] = value
                    self._n += 1
            
                def delete(self, k):
                    if not 0 <= k < self._n:
                        raise IndexError("Invalid index")
                    for i in range(k, self._n - 1):
                        self._A[i] = self._A[i + 1]
                    self._n -= 1
                    if 0 < self._n < self._capacity // 4 and self._capacity > 16:
                        self._resize(self._capacity // 2)
            
                def _resize(self, c):
                    B = self._make_array(c)
                    for k in range(self._n):
                        B[k] = self._A[k]
                    self._A = B
                    self._capacity = c
            
                def _make_array(self, c):
                    return (c * ctypes.py_object)()
            
            # Example usage
            if __name__ == "__main__":
                arr = DynamicArray()
                try:
                    arr.delete(0)
                except IndexError as e:
                    print(f"Error: {e}")
            
                arr.append(10)
                arr.append(20)
                arr.insert(1, 15)
                print(arr)  # Output: [10, 15, 20]
            
                try:
                    arr.delete(5)
                except IndexError as e:
                    print(f"Error: {e}")
            
                arr.delete(2)
                print(arr)  # Output: [10, 15]
            
          

This example demonstrates appending, inserting, and deleting elements in the dynamic array.

Part 2: Reflection on Implementation

Understanding Dynamic Arrays

Dynamic arrays are versatile and efficient data structures, offering flexibility and performance benefits in various scenarios. This project forced me to really think about what happens under the hood when Python’s list dynamically resizes itself. It involves allocating new memory, copying old data, and continuing operations—which works well until frequent resizing leads to an O(n) operation.

Why Dynamic Over Static?

• Resizes itself—No awkward "Uh, I don’t have space for that" moments like with static arrays.
• Memory-efficient—It only grows when needed, unlike a linked list hogging memory for pointers.
• Fast append()—Except for those annoying moments when it has to resize.

Implementation Challenges

• Memory Management: Manually allocating memory with ctypes was a wake-up call.
• Shifting Elements: Inserting or deleting in the middle required shifting elements, leading to O(n) operations.
• Resizing Bugs: Debugging index errors due to incorrect copying during resizing.

Considering Big O

Amortized Complexity: Amortized complexity refers to the average time per operation over a sequence of operations, accounting for occasional expensive operations like resizing.

For example, consider appending 8 elements to a dynamic array that starts with a capacity of 1. The array resizes at capacities 1, 2, and 4, resulting in 1 + 2 + 4 = 7 copy operations. Over 8 appends, the average cost per operation is (8 + 7) / 8 = 1.875, which is close to O(1).

Takeaways

Dynamic arrays are convenient, but now I understand why dynamic arrays are so efficient and how they balance memory management with performance. They work so well because of handling memory intelligently and trading off between speed and flexibility.

Dynamic arrays offer a balance between memory efficiency and performance, making them ideal for scenarios where the size of the data set is unpredictable. They excel in providing fast access and append operations, but resizing and shifting elements can be costly. Understanding these trade-offs helps in choosing the right data structure for specific use cases.

At the end of the day, understanding how data structures actually work gives me an edge in writing better code. While Python handles a lot of this automatically, knowing what's happening under the hood makes debugging and optimization much easier.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms.
• Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data Structures and Algorithms in Python.
• GeeksForGeeks. (n.d.). Dynamic Array in Python - Link (Accessed 2023)
Python - Link
• CS50 Harvard. (2025). Memory and Dynamic Arrays Lecture - Link
• Course Instructional Material from CPSC 34000, Week 5 PowerPoint: Chapter 5 | Array-Based Sequences.