This is in continuation of our Data Structures and Algorithms using Python series. In the last part, we discussed about Lists and its implementation using Array. As a conclusion, we had found that list can lead to memory wastage if implemented using Array. In this part, we shall go through the implementation of list using another data structure called Linked List.
As Sophia’s list is going to have frequent additions and deletions, it may not be a good choice to implement it using arrays.
There is one more implementation for list which is using Linked List. Let’s explore list using linked list.
A linked list consists of a group of nodes which together represent a sequence or a list. Each node will have a data part which holds the actual data and an address part which holds the link to the next node. The first node in the list is known as head node and the last node is known as tail node. Unlike array, in linked list, the nodes need not be stored in contiguous memory locations.
In the above program, we created a class Node with constructor that takes data as an argument. We have other four methods called getters and setters to get data, set data, get next and set next. Then we created an instance of the Node object called item_node with Sugar as an argument which is nothing but the data part. When the instance is created, we called the get_data() method to get the item and hence, Sugar is printed.
To link the nodes and create a linked list, let’s create a new class, LinkedList with two attributes, head and tail both initialized to None as shown below.
Assume that Sophia’s list is maintained as a linked list and she wants to traverse through the list and display the items in the list starting from the first item.
Notice the Pointer P which traverses from Sugar to Biscuits one after another, i.e. , from Head H to Tail P .
In the above algorithm, we are using a while loop to traverse the Linked List until we reach the tail node.
Let’s start creating Sophia’s list from the beginning. She wants to add “Sugar” as the first item and after that add “Teabags” to the end of the linked list.
Algorithm Steps :
To add data to a Linked List, we first create a node using the data provided. Then, we have two conditions :
- Empty Linked List — If the linked list is empty, i.e., the head node is not referring to any other node as of now, we make the head as well as the tail node refer to the new node we created just now.
- Linked List having one or more node(s) — If the linked list already contains node(s), we make the tail node’s link refer to new node we created just now. This way, we have added a new element to the end of the linked list and now the new node has become the tail node.
First we created two classes — Node and Linked List, as we have seen above. In the linked list class, now we have other two methods called add() and display() to add and display elements in the linked list respectively.
In the add() method, we have implemented the same algorithm that we discussed above. We created an instance of Node class using the data. Then we checked if the head node is referring to None. If yes, it means the list is empty and we need to make the head as well as tail node refer to the new node that we created. If not, it means we have already some element(s) present in the list and hence we need to refer the tail node’s link to the new node.
In the display() method, we are using a while loop (as discussed above) to traverse the linked list and the get_data() method in the Node class comes in handy here for printing the data.
In addition to these two methods, we have used another additional dunder method __str__() which also does the same job of printing the data in one line.
Count Number of Elements
To count the number of elements, we have defined a count_nodes() method outside the Node and Linked List class which takes a Linked list object as an argument. Within the method, we initialize a count variable with zero. Then we set a temp variable to the head of the list using the get_head() method and traverse the list using a while loop until we reach the final node. In each iteration, we increase the count variable by one and in the end, we return the count variable.
Let’s end this part right here. In this part, we discussed the basics of Linked List and how to add elements in a linked list as well as its traversal. In the next part, we shall discuss few more operations on Linked List such as Search, Insert and Delete. Along with this, we’ll also compare Arrays with Linked Lists.
Stay Tuned, thanks !