Why are list considered dynamic?

An array is a data structure which arranges items sequentially. In most programming languages, its done in typically a more or less similar manner but in Python, its done a bit differently.

But before we dive into the specifics associated with Python, we must first have a quick look at what a regular array is.

General definition and characteristics of an Array

Each position in the array has an index, starting at 0, with elements stored sequentially corresponding to those indexes.

Arrays typically come with fast appends and lookups adding a new element at the end of the array as well as retrieving an element from a given index in the array both take O[1] time only.

On the other hand, the shortcomings of arrays include theyre of fixed size. The number of elements were going to have in our array always needs to be specified beforehand. [But NOT in a dynamic array, which well get to later:]]

Also, we have O[n] worst time for any insertion or deletion operation in the array. You might question why that is if we just insert an element without moving all the others or just delete an element without moving over and rearranging all the others, wont the runtime be lesser?

The answer is this theory actually violates the very idea arrays operate on keeping elements sequentially arranged in memory. If gaps are left to facilitate quicker insertion or deletions, we will no longer be able to know exactly where each element in the array will be.

Quick note: If youre wondering about what worst time is or want to get a basic conceptual idea of time complexity, please do consider reading my previous article on Big O notations!

Lists in Python the difference!

Now that weve seen what arrays look like, we can move on to defining and understanding them in our programming language of choice Python!

Python does not give regular array data structures like Java or C++.

The one big point of difference of how arrays are implemented in Python is that theyre not normal arrays, theyre dynamic arrays.

A dynamic array has the property of auto-resizing. The arrays we define no longer need to be of fixed size, the number of elements we have in them can change[increase or decrease] anytime. Thus, it means that we can add or delete elements dynamically.

So how do the runtime for different operations differ then?

Insertion and deletion as well as lookup of elements and the append operation all take the same amount of time O[n] and O[1] respectively. But there is a big point to take into consideration here, something to be beware of.

The time complexities mentioned here are not worst case time complexities, they are actually the amortised worst case times. This concept is quite easy to grasp once you understand the motivation behind it.

Heres how this wiki article states it:

The motivation for amortised analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic.

What this means is amortisation consists of looking over the whole series of operations [each line of code or groups of lines of code] in the algorithm and then determining if they add up to be as costly or not. This is because while some operations in the algorithm might be costly, some might be actually very cheap, hence summing those up and looking at the entire algorithm, the runtime of the algorithm might not be as costly in practise!

How does this apply to dynamic arrays?

Now, as we were talking about dynamic arrays [implemented as Lists] before, lets get back into it to understand this new concept of time complexity.

What happens when we try to append an element to an array that is already full? To make extra room, dynamic arrays automatically make a new, bigger underlying array of size twice as big as the current one.

The operations involved here will now include these creating a new array of double the current size and then copying the elements of the current [old] array into the new array, one by one, and then finally, adding the new element to the array.

How much time does it take?

Let us look at an example first, to get the intuition behind and then well move into the necessary jargon.

Well, copying over each element will definitely cost O[n] time, thus the new append operation the one we do when the capacity of our array is already full, will take O[n] time instead of an O[1] time in the worst case!

BUT, we have to take into consideration the amortised cost of this append operation too.

In general, when we push a new element to an array which is not full, it takes O[1] time. This time is always O[1] until the array becomes full. Once we try to append an additional element after its full, we need to double the size of the array in O[n] time and then push in the next element. Once we do that, once again we can do the appends in O[1] time and this time we can repeat these appends for double the array size!

So, the number of O[1] appends we get has doubled until after we get to exhausting the capacity of the new array we made.

Therefore, these, in practise, are said to sort of cancel out each other, and so we get an worst case amortised time of O[1] for our list append operation!

Now, lets look at some of the prime functions available in Python for our list operations!

Now that we have discussed the logic behind lists, let us look at how Python helps us with our regular data structure tasks with some of its main list manipulation functions.

I wont be going over all of them, obviously, but the ones I feel are used most frequently while designing our algorithms and the ones that you should really know about will certainly be mentioned here.

Weve already seen the append function which is used: To add an element to the end of the list.

Next up we have:

• index function: that returns the index of the element in the list.

• reverse function: it reverses the elements of the list.

• pop function: it removes the item at the given index from the list and returns the removed item.

• remove function: it removes the first matching element [which is passed as an argument] from the list.

• sort function: it sorts the elements of a given list in either ascending or descending order.

Here are some resources for furthering your knowledge on arrays and in general, data structures :]

1. Interview Cake is brilliantly designed website where you can learn about all the data structures in comprehensive detail, all for free. You can also see Python implementations of them and practise in their editor too.
2. Data Structures and Implementations, is a PDF styled, detailed guide on the concept of time complexity and data structures, all in one long web page. A very worthy read.

Thank you for reading and if you liked this article, please do leave a few claps to show your appreciation and Ill see you in the next one!

Do you want to get one free, clean email from me every week or two weeks containing the best of my curated articles and tutorials that I publish? Join my Codecast!

Connect with me on Twitter and LinkedIn!