Array: Python Implementation

Array is a data structure to store data at contiguous memory locations.

Element in an array is accessed in constant time provided we know the first element memory address and the data-type of the data stored in the array. Only data of a single data-type can be stored in an array. An array can either hold integer or float or string etc; but not a combination of float, integer or integer, string etc.

Array is light on memory requirement, as we only need to store the values, not any identifier or index for the value.

Traversing an array is simple and is O(n) complexity operation.

Array complexity

Time complexity

Worst case

Access Search Insertion Deletion
O(1) O(n) O(n) O(n)

Space Complexity


Example array and memory addresses

Following is one graphical demonstration of an array which has 7 elements. Each element of the array is an integer and takes 32 bit of memory to store the value.

The next element of the array can be accessed based on the starting element memory address as follows:

memory_address_of_next_element = memory_address_of_start_element 
 + single_element_memory_size * index

In the above array single_element_memory_size = 32, memory_address_of_start_element=100

Element at index i can be accessed as 100 + 32 * i.
Address of element at index 3 is 100 + 32 * 3=196


Arrays are of constant size, language like C/C++ does not allow to resize the array dynamically. To increase the size of an array, the user has to create a new array with the desired size and copy the elements from previous array, which is O(n) complexity operation.


When deleting an element from the array, reindexing is required for the elements succeeding the removed element. Complexity of reindexing is again O(n)

Array Implementation in Python

Here we will use Python to implement a simple Array data structure. We will use Python’s ctypes to allocate a block of contiguous memory for our array.

A contiguous block of memory can be allocated as follows:

import ctypes

# allocate memory for 10 unsigned integers
array = (ctypes.c_unit * 10) ()

# allocate memory for 10 floating point numbers
array = (ctypes.c_float * 10) ()

# allocate memory for 10 python objects, exact amount of memory will depend on the object type stored
# if integer is stored then 32 bit per object, if float is stored 96 bit per object etc
array = (ctypes.py_object * 10) ()

Lets verify if the above construct really give consecutive memory addresses:

>>> import ctypes
>>> array = (ctypes.c_uint * 10)()
>>> for i in range(10):
...     array[i] = i+1
>>> array[0]
>>> array[9]
>>> id(array[0])
>>> id(array[1])
# Get hexadecimal representation of the memory address
>>> hex(id(array[0]))
# The following address is 32 bit far from the address of array[0]
# 0x10182b8e0 - 0x10182b8c0 = 0x20 = 2 * 16 + 0 * 1 = 32
>>> hex(id(array[1]))
# The following address is 32 bit far from the address of array[1]
>>> hex(id(array[2]))
# The following address is 32 bit far from the address of array[2]
>>> hex(id(array[3]))

In the above example snippet we use id function to get memory address and hex to convert the address to hexadecimal format for readability.

Here in our implementation we will use ctypes.py_object to allocate memory such that user don’t have to explicitly set the data type while creating the array.

Here we will implement Array with the following features:

  1. Append
    Append an element to the array.
  2. Remove
    Remove an element at an index of the array
  3. Pop
    Remove and returns the last element of the array
  4. Set item __setitem__
    Set an element using explicit index
  5. Get item __getitem__
    Get an element using explicit index
import ctypes
from typing import Any

class Array:
  """Array data structure implementation in Python.
    capacity: Maximum capacity of the array.
  def __init__(self, capacity: int):
    """Initialize instance level attributes."""
    self.capacity = capacity
    # allocate memory
    self._array = self._allocate_memory(capacity)
    # Point to next available index to store data
    self.next_id = 0
    # Fill the array with None values

  def _prefill_array(self) -> None:
    """Prefill the array with None values."""
    for idx in range(self.next_id, self.capacity):
      self._array[idx] = None

  def _allocate_memory(self, capacity: int) -> Any:
    """Allocate memory to hold n objects.
     capacity: Capacity of the array.

      Initialized array.
    return (ctypes.py_object * capacity)()

  def __len__(self) -> int:
    """Returns the length of the array.

      Length of the array.
    return self.next_id

  def __getitem__(self, index: int) -> Any:
    """Get an array element using index.

      index: Index of the element.

      Element at that index.

      IndexError: If the index is out of range.
    if not 0 <= index < self.next_id:
      return IndexError('Index out of range.')
    return self._array[index]

  def __setitem__(self, index: int, value: Any) -> None:
    """Set an array element using index.

      index: Index of the element.
      value: Value of the element.

      IndexError: If the index is out of range.
    if index > self.capacity - 1:
      raise IndexError("Index out of range")
    self._array[index] = value
    if self.next_id < index:
      self.next_id = index + 1

  def append(self, value: Any) -> None:
    """Append an element to the array.

      value: Value of the element to append.
    if self.next_id == self.capacity:
      self._increase_capacity(2 * self.capacity)

    self._array[self.next_id] = value
    self.next_id += 1

  def _increase_capacity(self, new_capacity: int) -> None:
    """Increase array capacity.

      new_capacity: New capacity of the array.
    _array = self._allocate_memory(new_capacity)
    # copy over the elements from the current array to the new one
    for i in range(self.next_id):
      _array[i] = self._array[i]

    self._array = _array
    # update capacity
    self.capacity = new_capacity

  def remove(self, index: int) -> None:
    """Remove an element at an index.

      index: Index of the element to remove.

      IndexError: If index is out of range.
    if 0 > index or index > self.next_id - 1:
      return IndexError('Index out of range.')

    for idx in range(index, self.next_id - 1):
      self._array[idx] = self._array[idx + 1]
    self.next_id += -1

  def pop(self) -> Any:
    """Remove and return the last element.

      Last element of the array.
    if not self.next_id:
      raise ValueError("Empty array.")
    val = self._array[self.next_id - 1]
    self._array[self.next_id - 1] = None
    self.next_id -= 1
    return val

  def __repr__(self) -> str:
    """Representation of the Array object.

      A str representing the array.
    return str([self._array[val] for val in range(self.next_id)])

Using the array

# Initialize an array to store 20 elements
>>> my_array = Array(capacity=20)
# store element 5 at index 0 (use append)
>>> my_array.append(5)
# Store using index, store 10 at index 1
>>> my_array[1] = 10
# Remove element at index 0
>>> my_array.remove(1)
# pop the last element
>>> my_array.pop()

Python inbuilt Array DS

Python also provide an inbuilt array implementation, which can be accessed as follows

import array

# initialize an array of integer with values [1, 10, 4, 3]
# here "i" mean signed integer data type.
>>> my_array = array.array("i", [1, 10, 4, 3])
>>> my_array[1]
>>> my_array[2]