Python - Data Structures - Episode 1 - Lists - Part 1
Author : Hamza EL YAAQOUBI
Introduction
In this article, I will talk about a very important data structure which is used all the times.
It’s about Lists and their specification.
Why do we need lists ?
It may happen that you have to read, store, process, and finally, print dozens, maybe hundreds, perhaps even thousands of numbers. What then ? Do you need to create a separate variable for each value ? Will you have to spend long hours writing statements like the one below ?
If you don’t think that this is a complicated task, then take a piece of paper and write a program that :
- reads five numbers,
- prints them in order from the smallest to the largest (NB, this kind of processing is called sorting).
- You should find that you don’t even have enough paper to complete the task.
So far, maybe you’ve learned how to declare variables that are able to store exactly one given value at a time. Such variables are sometimes called scalars by analogy with mathematics. All the variables you’ve used so far are actually scalars.
Think of how convenient it would be to declare a variable that could store more than one value. For example, a hundred, or a thousand or even ten thousand. It would still be one and the same variable, but very wide and capacious.
What if you could just number them ? And then say : give me the value number 2; assign the value number 15; increase the value number 10000.
Initialize a list
As you can see, you are now able to understand why we need sequences to store data.
Note that lists are an ordered sequences and can contain duplicate items.
Let’s create a variable called array. It is filled with a list of four values. It stars with an open square bracket and ends with a closed square bracket. All of four elements are separated by commas :
array = [1, 2, 3, 4]
The elements inside a list may have different types. Some of them may be integers, others floats, and others may be lists (Multidimensional lists).
Elements in a List start from index zero. This mean that the item stored in the beginning of the list will have the number zero.
So, according to our example :
- The first element is assigned to number zero
- The second element is assigned to number one
- The third element is assigned to number two
- The fourth (last) element is assigned to number three
Refer to the following screenshot :
NB : In memory, Python stores four items. So if we want to add other elements in the list, Python will double automatically the initial size, we call that operation ‘Dynamic Size Array’.
Keep in mind that list is a collection of elements and each element is a scalar
Add / insert element in the list
As you can see, we are now able to do some operations in our list after initialization. In this section we will talk about how to append or insert new elements and what’s the complexity time of each operation.
- Append method : append()
- Description
This method allows us to add an item to the end of the list. It’s equivalent to the following notation (we will talk about this notation later) : array[len(array):] = [x]
- Syntax
Here’s the syntax for append() method :
list.append(item)
This method does not return any value, but it updates the existing list.
- Complexity Time
In order to add a new element in the existing list, the append method get the last free index and insert directly the element. It means that this operation is executed in a constant time.
Using the Big O Notation, the time complexity is O(1).
- Example
list = [1, 2, 3]
list.append(4)
print('The list contains the following elements : ', list)
This snippet outputs :
- Insert method : insert()
- Description
This method allows us to insert an item at a given position.
- Syntax
Here’s the syntax for insert() method :
list.insert(index, item)
- The first argument index is the index of the element before which to insert
- The item is the element o insert
This method does not return any value, but it inserts the given element at the given index in the list.
- Complexity Time
To insert a new element at the given index, all elements which are located in the right of the index of the element to be inserted are shifted in the right. It means that in the worst case this operation is executed in a linear time.
Using the Big O Notation, the time complexity is O(N) which N is the length of the list.
- Example
We will insert 4 in the front of the list declared below :
list = [1, 2, 3]
list.insert(0, 4)
print('The list contains the following elements : ', list)
This snippet outputs :
Conclusion
In this article, we have seen why we need lists, how to initialize it, and how to add or insert new elements in the list and what’s the time complexity of each operation.
Here’s key takeaways for the time complexity :
In the next article, we will talk about other operations such as : access, search and delete.
Share this article and Stay tuned.