Reading Time: 7 Minutes

In this series of exploring abstract data types we will be diving into concepts like trees, graph traversals, stack, queue, linked list, hash tables etc in python programming language. This series requires you to have a basic understanding of python programming, concepts of class, object oriented programming, functions and scope, data types such as array, list, tuple, strings, integers, dictionary etc.

For those who are beginners into the world of programming, and have explored the basic data types, assume that all the use cases and requirements related to data can be performed using them. Even I had the same mindset when I started to learn data structures, I was able to handle data of any volume and complexity with the basic data types such as list and dictionary.

But then when I started diving deep into the world of data structures, I began to understand the different aspects of it and how they can help to formulate complex relationships between data and overall improve code efficiency when we are dealing with large and complex data.

Linked lists applications can me seen widely in fields like GPS navigation( where each node can store the waypoints and directions), web browser’s history management, Job scheduling in your CPU, database management systems( records and data blocks efficient retrieval), polynomial addition, etc

Linked list is a linear data structure consisting of a sequence of elements, where each element (also known as node) points to the next one in the sequence, forming a chain-like structure.

Let’s explore some basic terminologies associated with linked list before we dive into the logics behind it.

1. Node Structure:
   • A linked list is composed of nodes. Each node contains two main components: • Data: This holds the actual value or data that the node stores, such as an integer, string, or any other data type. • Next Pointer: This is a reference or link to the next node in the sequence. It indicates the node that follows in the list.
2. Head:
   • The head is a reference to the first node in the linked list. It serves as the entry point for accessing the list.
3. Tail:
   • The tail is a reference to the last node in the linked list. It allows for efficient appending of new nodes to the end of the list.
   Here is an example of a simple representation of a linked list:

Now this look like your general array or a list, and might think that why do we even need this, here are some of it’s advantages:

• Dynamic Size: Linked lists can dynamically grow or shrink in size, making them flexible for managing data.
• Insertion and deletion of elements within a linked list are generally efficient, especially compared to arrays or lists with fixed sizes.
• Linked lists allocate memory for each node only when needed, which can save memory compared to arrays.

Instead of giving the entire code and writing comments in sides, I will give a complete breakdown of the program segment by segment.

Source Code

1.First the basic unit of linked list, which is the node has to created as a template using class. Here the data is initially set to None using method overloading.

class node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

2. Now the template for the linked list is designed. The self.ptr is the initial node, I will mention the need for self.lst in the later part of the code.

class LList:
    def __init__(self):
        self.ptr = node()
        self.lst = []

3. All the functions which I will explain below is written under the LList class. Now the insert function is created.

def insertnode(self, data):
    newnode = node(data)
    current = self.ptr

    while current.next is not None:
        current = current.next
    current.next = newnode

In the while loop we are checking for the node before the tail node, and then setting that found node’s pointer to our new node(data).

4. Once the basic insertion operation is done we have to view the linked list in the output screen, so with the same logic as used above we have to design a display function.

def display(self):
    temp = self.ptr
    while temp.next is not None:
        temp = temp.next
        print(temp.data, end='->')

    print('Null')

5. Delete node function:

def deletenode(self, data):
    if self.ptr.data == data:
        temp = self.ptr.next
        del self.ptr
        self.ptr = temp

    else:
        p = self.ptr
        while p.next.data != data:
            p = p.next
        temp = p.next.next
        del p.next
        p.next = temp

Here the self.ptr.data points to the head of the linked list, if the the node to be deleted is the head, then the if condition is performed, the corresponding node of the head is stored in temp and once the head node is deleted, the head becomes temp.

If the node to be deleted is not the head node, then the linked list is traversed iteratively with a while loop checking for the node, if found then the same approach as used in the first condition is used to transfer the pointer and delete the node.

6. At any point if you want to check whether the linked list is empty or not without using display, you can use the below function:

def isempty(self):
    cur = self.ptr
    c = 0
    while cur.next is not None:
        c = c + 1
        cur = cur.next

    if c == 0:
        return True
    else:
        return False

7. The final code segment to use the functionalities which we created above would look like this→

head = LList()
while True:
    choice = int(input("1.INSERT\n2.DELETE\n3.ISEMPTY\n4.EXIT\n"))
    if choice == 1:
        element = int(input("enter the element to be inserted"))
        head.insertnode(element)
        head.display()
    elif choice == 2:
        element = int(input("enter the element to be deleted"))
        head.deletenode(element)
        head.display()
    elif choice == 3:
        print(head.isempty())
    elif choice == 4:
        break
		else:
				print("Enter the correct option")

So that a wrap, we have covered all the basic aspects of a linked list. Thank you for reading all along, hope I have helped to you to learn this concept in a simple way.If you have any doubts or need further explanations, do let me know in the comment section.

If you have any questions or need further clarification, please feel free to ask in the comment section below. Your curiosity and engagement are highly valued. Click here to view all the concepts related to machine learning.

Thank you for reading all along, subscribe to sapiencespace and enable notifications to get regular insights.

mage Credits: Nubelson Fernandes, Tim-Stief