Introduction
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, the list kept on changing.
In this case, we can use the List data structure to represent Sophia’s list of grocery items.
What are lists?
List:
- Is a linear data structure
- Is used to store a sequence of values
- It can grow and shrink dynamically based on the need
Common operations on a list are:
List Implementation
A list can be implemented using an array or linked list. Let’s begin with the array implementation.
An array is a data type that 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 the list data type in python which is internally a dynamic array that 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 the element is added at index position 0. The remaining memory is considered to be reserved space that will be used later for the addition or insertion of elements.
Algorithm steps:
Insert Operation in List
Algorithm Steps :
Delete Operation in List
Algorithm Steps :
Observations
Here is a code that implements the lookup functionality of an Organization’s Directory :
First, we created an Employeeclass 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 Organizationhaving 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_namewith employee name(using get_name() method). If it matches, it appends it to another list called result_listwhich 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 a list using an array is a good option for its implementation?
- List using array may involve shifting of elements in both insert and delete operations.
- When the capacity of the array is increased during the addition or insertion of elements, it may result in wastage of memory in the form of reserved space.
Conclusion
In this part of our series, we have learned about lists in python, when we can use them, and the algorithm to create an empty list using an array. Along with this, we also learned about the different operations that can be performed on a list. In the end, we saw how lists can lead to memory wastage if implemented using Array. In the next part, we shall go through the implementation of the list using another data structure called Linked List.
Stay tuned, thanks!