Data Structures and Algorithms using Python (Part 4 : Operations on Linked Lists)

Data Structures DATA STRUCTURES AND ALGORITHMS USING PYTHON SERIES Image

    In the last part, we had discussed about the basics of Linked List and how to add elements in a linked list as well as its traversal. In this 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.

    At times, Sophia can come across situations when she wants to check whether her list contains an item or not. Let’s learn how we can search elements in a linked list.

    In the last part, we ended up the below code :

    Search Operation

    Let us now modify this code to add a new method find_node(data) to find a node with the given data in the linked list. If found, the method will return node, otherwise, it would return None.

    What we did is, we started with head node as temp. We started the iteration till temp is None i.e. the last node, and checked if the data is equal to the data we are trying to search using the get_data() method in the Node class. If it is equal, we simply return the temp variable else we continue the iteration. If we didn’t find the data during the entire iteration, we return None.

    Insert Operation

    Many a times, we come across situations where we are required to add an element after a specific element. This operation is known as Insertion. For example, if Sophia wanted to add Salt after Sugar in her list, she has to go through the following algorithm :

    For the insert operation, we require the data to be added and the data after which we have to add the incoming data. We first create a node using the incoming data. After that we can have three conditions — data_before is None, data_before is not None and in the list or data_before is not in the list.

    If the data_before is None, it means we have to make the incoming node as head node, so we set it as head node. We also check if the next link is None. If it is, it means there is no more element in the list and we have to set it as tail node as well.
    If the data_before is not None, we find the data_before node using the find_node() method that we created above. If we find the data_before node, we make the new node’s link refer to the node_before’s link and the node_before’s link refer to the new node. Then we check if the new_node’s link is None. If it is, set it as the tail node.
    If we didn’t find the data_before node, we simply display an error saying we didn’t find the node.

    Delete Operation

    The final operation we’ll discuss is Delete which can be used to delete elements from the list. For example, if Sophia wishes to delete Salt and Milk from her list, she has to follow the following algorithm :

    For the delete operation, we just require the data to be deleted. In this operation as well, we can have three conditions — data is in the list and it is head node, data is in the list but not head node or data is not in the list.

    We first find the node with the data given. If it is not found, we display an appropriate error. If it is found, we check if it is head node. If it is head node, then we check if it is tail node as well. If it is tail node also, we set the tail node to None and head node to the next node. If it is not the head node, we set a temp variable to the head node and iterate the list till the end. If we find the node, we set the next part of temp to the next part of the node we found. If the node is tail node as well, we set the next part as None and stop the iteration right there, else we continue.

    We have now seen the basic operations on Linked Lists such as Add, Display, Count Number of Elements, Insert, Search and Delete. Our final code after these operations is :

    List using Array vs Linked List

    We may choose between array or linked list for implementing list based on the problem statement. If the problem has frequent insertions and deletions, prefer linked list. Otherwise, if it involves only accessing the elements at random or in sequence with less number of insertions and deletions, use array.

    Conclusion

    In the last three parts, we have completed Lists. In the upcoming part, we shall discuss about Stack data structure.
    Stay Tuned, Thanks!

    You can read my blogs here also.

    Tags: #Coding, #Python

    0 Comments

    To add a comment, please Signup or Login