This is the second part of our Data Structures and Algorithms using Python series where we are going to learn about the first data structure called Lists.
If you haven’t read the first part yet, find it here where we introduced Data Structures in brief.
Let’s assume this scenario first:
It was a Saturday morning and Sophia was in the grocery shop with her list of grocery items. The list kept on changing as she moved from one section of the shop to another. She added few items, removed few and kept on scanning the list.
She in fact, started with a list of 4 items and ended up buying many more.
If we have to represent Sophia’s grocery list, how can we do it?
Here, we need to represent Sophia’s list as a sequence of grocery items. The sequence keeps changing frequently.
As Sophia moved from one section to another in the shop, list kept on changing.
In this case, we can use list data structure to represent Sophia’s list of grocery items.
- Is a linear data structure
- Is used to store a sequence of values
- It can grow and shrink dynamically based on need
Common operations on list are:
List can be implemented using array or linked list. Let’s begin with the array implementation.
Array is a data type which is of fixed capacity and can store a collection of elements. However we can use it to implement the list data structure. For implementation we will be using list data type in python which is internally a dynamic array which can grow and shrink based on the elements added to or removed from it. Initially, it is created with a certain capacity and based on elements getting added or removed, the capacity is increased or decreased respectively.
To begin with, let’s create an empty list.
Add Operation in List
When an element is added to an empty list in Python, a block of memory is allocated and element is added at index position 0. The remaining memory is considered to be reserved space which will be used later for addition or insertion of elements.
Insert Operation in List
Algorithm Steps :
Delete Operation in List
Algorithm Steps :
Here is a code that implements the look up functionality of an Organization’s Directory :
First, we created an Employee class with name, employee id and email id. It has a constructor and three methods — get_name(), get_emp_id() and get_email_id() that return employee name, employee id and employee email id respectively. We created another class called Organization having two methods — lookup() and display(). The lookup() method takes key_name (name of the employee) as an argument. It, then, iterates over the entire list of employees and matches key_name with employee name(using get_name() method). If it matches, it appends it to another list called result_list which is then passed to display() method which takes result_list (a list) as an argument. It iterates over the list to print the employee details.
This is how a basic Directory System works.
Sophia’s list is having frequent insertions and deletions. Do you think list using array is a good option for its implementation?
- List using array may involve shifting of elements in both insert and delete operations.
- When capacity of the array is increased during addition or insertion of elements, it may result in wastage of memory in the form of reserved space.
In this part of our series, we have learnt about lists in python, when we can use them and the algorithm to create an empty list using array. Along with this, we also learnt about the different operations that can be performed on a list. In the end, we saw how list can lead to memory wastage if implemented using Array. In the next part, we shall go through the implementation of list using another data structure called Linked List.
Stay tuned, thanks!
You can connect to me here.