The Backend Story of Lists in Python

How are elements stored? Referencing? How is continuity maintained? Mutability? Complexity? & various other bits of info. Let’s figure it all out in this article & make our foundation of Python Lists strong by learning what happens in the backend from the moment we declare a list.

Manvendra Bhadauria
CodeX
Published in
8 min readAug 5, 2021

--

Introduction: Have you ever come across a topic that, on the surface, appears to be very difficult to understand or implement? I’m sure we’ve all come across such topics from time to time, and let me be clear: Python Lists is not one of them. Have you ever wondered what happens in the backend when you declare a list, how elements are stored, are we using referencing? , how is the continuity maintained, is it mutable, the complexity of lists.
In this essay, I’ll break down Python Lists and address all of these problems in a straightforward manner making Python List & its working an easy-to-understand topic for everyone. Let’s get into it and start by learning the definition of Python Lists.

Definition: A list is a data structure in Python that is a mutable, or changeable, ordered sequence of elements. Each element or value that is inside of a list is called an item. Just as strings are defined as characters between quotes, lists are defined by having values between square brackets. Please be careful as lists can be thought of as analogous to arrays, but they aren’t the same thing. Arrays traditionally have a fixed memory size whilst lists have dynamic memory allocation. When you are working in Python, call a list a list. When you are working in PHP or Javascript, call an array an array. When you are working in C, call for help!

Following are some examples of lists in Python:[ ] #Empty list
[1, 2, 3] #List of integers
[1, 2, 5.6, 9.8] #List of numbers (Floating point and Integers)
[‘a’, ‘b’, ‘c’] #List of characters
[‘a’, 1, 4.3, “Zero”] #List of mixed data types
[“One”, “Two”, “Three”] #List of strings.

So reading the definition above we can infer that Lists is a data structure in python somewhat similar to arrays but not analogous. Before breaking down the above definition and understanding it with a real-world example let’s understand some of the terms used in the above definition.

  • Element: Any entity or object such as a numeric value, string, boolean that we are storing in the list.
  • Data Structure: In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification.
  • Mutable: In layman’s terms, mutable is the attribute of a data structure in Python that makes it editable, i.e., we may change or alter the data structure’s elements in the place itself. We will learn about this a bit later in this article in detail.
  • Index: Indexes are the numbering of boxes that store the components of a list. Indexes begin with 0 and conclude with n-1, and they are used for access and change, n is the list’s size, i.e. the number of elements in the lists.

Let’s take a closer look at the definition using a real-life example to explain lists. We’ll compare trains to lists, so each compartment of a train can be thought of like a box of a list for storing elements, and just as we can change the number of passengers in each compartment, we can also change the value of the element, we can also change the size of a train depending on the need, also we can do the same with lists, which makes them dynamic, unlike arrays. Also unlike arrays, lists are heterogeneous, allowing us to store elements of many data types. Below you can see a brief difference between arrays and lists.

Array VS Lists

Mutable And Immutable Concept

The Python data types can be broadly categorized into ​two​ — ​Mutable​ and
Immutable​ types. Let us now discuss these two types in detail.

  • Since everything in Python is an Object, every variable holds an object
    instance.
  • When an object is initiated, it is assigned a unique object id (Address in the memory).
  • Its type is defined at runtime and once set it can never change.
  • However, its state can be changed if it is ​mutable​. In other words, the value of a ​mutable​ object can be changed after it is created, whereas the value of an ​immutable​ object can’t be changed.

Note:​ Objects of built-in types like (int, float, bool, str, tuple, Unicode) are ​immutable​. Objects of built-in types like (list, set, dictionary) are ​mutable​. A list is mutable as we can insert/delete/reassign values in a list whereas variables are immutable.

How are elements stored in the Lists?

Whenever we create a list in python it is stored in memory and as we discussed it is dynamic allocation so let’s see in detail how elements are stored in a list. We will simply understand this.
Suppose we start by creating a list have elements :

ls = [1, 2 , 'Manvendraaaa' , 1.2]Length of list ls is 4 containg elements of integers , float , and string data types. 

The elements in the list are not stored themselves. Instead, every element of the list is stored at random locations, and the list stores the address of those random locations.

Suppose the elements of the list 'ls' are stored at random location with random address stated below in the format :variable_name = value --> address of random locationa = 1 --> 520
b = 2 --> 680
c = 'Manvendraaaa' --> 240
d = 1.2 --> 980
The list will hold these addresses and it will look something like :
ls = [520,680,240,980]
Note : The addresses are only for demostration in real they are hexadecimal values.

I hope the above part is clear so now we will proceed and discuss what happens when we change an element from the list ‘ls’.

So suppose we want to change the element 'Manvendraaaa' to 'Medium'. We know that the element is at index 2. So as soon as we type the program to change it what happens in the backend. Let's see :ls[2] = 'Medium' #Command to change the element to 'Medium'The moment we execute this command a new random location will be created with the element 'Medium' stored there and now instead of the variable 'c' pointing towards it will point towards the location where 'Medium' is stored as variable are immutable.
c = 'Medium' --> 460
Now c stores the address of the location where 'Medium' is stored & the list 'ls' stores the location of c as list are mutable. Keeping this in mind the array will look like : ls = [520,680,460,980]
ls = [1, 2 , 'Medium' , 1.2]

So from the above points, it is pretty clear that Python Lists use referencing in the backend for storing elements in the list. Referencing means using the addresses to perform operations instead of using the elements themselves. For example, the variable ‘a’ is holding the address of the location where 1 is stored, and the list ‘ls’ is holding the address of the location where a is stored.

How is continuity of Lists maintained?

So far we have understood the concept of mutability, referencing & how are elements stored in the lists. While learning about the later concept we learned that the list stores elements using referencing and the elements are stored at random locations, so how does the indexing work and how are we maintaining the continuity of the list? This is where the concept of resizing comes into play.

Whenever we created the list ls with 4 elements we reserved a continuous block of memory which can store 4 elements consecutively. The list we were having was : ls = [1, 2 , 'Medium' , 1.2]Suppose now we want to store a new element 'Happy' at the end of the list 'ls'. So we can't be sure that there is an empty space at the end of the list and for that reason python uses resizing for optimizing this problem. The moment we will use append to add the element 'Happy' at the end of list :ls.append('Happy')So if there is no empty space at the end of the list 'ls' python will find a new block in the memory of double the size of the list 'ls' and copy all the element of the list 'ls' into it and now 'ls' will point to that new list & then append the new element at end at there is enough space for more new elements. This process is called Resizing of List and is used in python because lists are dynamically allocated. Finallyour list will look like :ls = [1, 2 , 'Medium' , 1.2 , 'Happy'] #With more spaces left

Why are Lists slower than Arrays?

It takes 47 percent longer to read from a List than it does to read from an array. That’s a significant difference, but not quite as significant as writing, which takes 695 percent longer! So why is List so much slower? There are many reasons for this but I’ll be pointing out the most obvious one’s here in this article :

  • Arrays have fixed sizes as they are statically defined & can hold data of only one kind whereas the data stored in lists are heterogeneous & the size of the list, for this reason, is not static.
  • While writing in the lists we need to check both the space available and the data type we are writing whereas in arrays we prior tells the datatype and hence we only store one kind of data and each block of an array has a fixed size, unlike lists.
  • The above point also concludes that the size required by the list is normally larger than that required by an array.

Overview: That was it from my side on the topic “How a Python List perates in the Backend”. Before you all hop onto another article, here’s a link to an article on ‘15 things you should know about Lists in Python’.

This article explains different methods/operations of lists in detail along with a code walkthrough by

. Do check it out ❤.

Editors Note: First and foremost, thank you for sticking with the article until the end. If you learned something new please leave a clap & follow for more such amazing articles in the future. Also do give me your feedback on how I can improve my writing.

--

--

Manvendra Bhadauria
CodeX
Writer for

Philomath | Data Science Enthusiast ❤ | Learning and Sharing