Skip to content

Arrays in python

Python has dynamic arrays called list.

Lists are basically arrays of points to an python object. Everything in python are objects. And every object contains a reference counter - it keep tracks of all the reference to the object, pointer to the type, and finally the data to be stored inside that object.

Due to these things an object takes up additional space of 16 bytes.

1D array: byte address of element i = base address + (size of each element)*(i - first_index)

Example

a = [0,1,2,3,4,5,6] | base address = 1000 | size of element = 2 byte | find location of a[4]

location of a[4] = 1000 + 2*(4-0) = 1008

Alt text

Insertion & Deletion

  • Best case : at the end, \(\Omega(1)\)
  • Worst case: at the beginning, O(n)
  • Average case: in the middle, \(\Theta(n)\)