Why list is dynamic in Python?

Implementation of Dynamic Array in Python

PythonServer Side ProgrammingProgramming

Dynamic Array

In python, a list, set and dictionary are mutable objects. While number, string, and tuple are immutable objects. Mutable objects mean that we add/delete items from the list, set or dictionary however, that is not true in case of immutable objects like tuple or strings.

Nội dung chính Show

Implementation of Dynamic Array in Python
Dynamic Array
Basics of the dynamic array implementation
dynamicArray.py

In python, a list is a dynamic array. Let's try to create a dynamic list

>>> #Create an empty list, named list1 >>> list1 = [] >>> type (list1) <class 'list'>

Add some items onto our empty list, list1

>>> # Add items >>> list1 =[2, 4, 6] >>> list1 [2, 4, 6] >>> # Another way to add items, using append. >>> list1.append('Tutorialspoint') >>> list1 [2, 4, 6, 'Tutorialspoint']

Remove some item from a list

>>> # deleting item from a list >>> list1.pop() 'Tutorialspoint' >>> list1 [2, 4, 6]

From above we can see that list is actually an extension of an array, where we can modify(increase or decrease) the size a list. We started with a list of size zero and then add four items to it.

Basics of the dynamic array implementation

Consider an example where the list .i.e. list1 is appended when the size of the array is full then, we need to perform below steps to overcome its size limitation shortcoming. This is the basis behind the dynamic array implementation

Allocate a new array list2 with a larger capacity
Set list2[i] = list1[i], for i = 0,1.n-1, where n is the current number of the item.
Set list1=list2, as now list2 is referencing our new list.
And then, just insert (append) new item to our list (list1).

Let's create a simple code on how to implement the dynamic array concept in python programming. We will create our own dynamic array class by using the built-in library class in python called ctypes which is going to be used as a raw array from the ctypes module.

dynamicArray.py

import ctypes class DynamicArray(object): #Initialize it def __init__(self): #We'll have three attributes self.n = 0 # by default self.capacity = 1 # by default self.A = self.make_array(self.capacity) # make_array will be defined later #Length method def __len__(self): #It will return number of elements in the array return self.n def __getitem__(self, k): #it will return the elements at the index k if not 0 <=k <self.n: return IndexError('k is out of bounds') return self.A[k] def append(self, element): #checking the capacity if self.n == self.capacity: #double the capacity for the new array i.e self.resize(2*self.capacity) # _resize is the method that is defined later # set the n indexes of array A to elements self.A[self.n] = element self.n += 1 def _resize(self, new_cap): #new_cap is for new capacity #declare array B B = self.make_array(new_cap) for k in range(self.n): B[k] = self.A[k] # referencing the elements from array A to B #ones refered then self.A = B # A is now the array B self.capacity = new_cap # resets the capacity #making the make-array method using ctypes def make_array(self,new_cap): return (new_cap * ctypes.py_object)() arr = DynamicArray()

As our dynamic class is ready to use, let try something with it

>>> len(arr) 0 >>> arr.append(1) >>> #First item entered >>> len(arr) 1 >>> arr.append('Tutorialspoint') >>> #second item entered >>> len(arr) 2 >>> arr[1] 'Tutorialspoint'

Thats it, we have created our own dynamic array and we can resize the array which is a list in python.