Linked List in Python

Linked List in Python

Aditya Raj Mar-29, 2022 Jan-06, 2022 Python Python Data Structure
  1. What Is a Linked List in Python
  2. How to Create a Linked List in Python
  3. Print All the Elements of a Linked List in Python
  4. Insert an Element Into a Linked List in Python
  5. Delete an Element From the Linked List in Python
  6. Count the Number of Elements in a Linked List in Python
  7. Update a Node in the Linked List in Python
  8. Why Use a Linked List in Python
  9. Full Implementation Linked List in Python
  10. Conclusion

Python provides us with various built-in data structures.

However, each data structure has its restrictions. Due to this, we need custom data structures.

This article will discuss a custom data structure called Linked List. We will also implement a linked list in Python and perform various operations on the linked list.

What Is a Linked List in Python

As the name suggests, a linked list is a data structure that contains elements connected using a link.

A linked list is created using objects called nodes. Each node contains two attributes - one for storing the data and the other for connecting to the next node in the linked list.

You can understand the structure of a node using the following figure.

Node in Python

Here,

  • A Node is an object that contains the attributes data and next.
  • The attribute data stores the data.
  • The attribute next refers to the next node in the linked list.

As shown in the following image, we can connect various nodes to create a linked list.

Linked List in Python

Here,

  • We have created a linked list that consists of four nodes.
  • The first node contains the number 10, the second node contains 20, the third node contains 30, and the last node contains 40.
  • We have also created a variable Head that refers to the first node. We only keep the Head variable in a linked list object. Data in all the other nodes are obtained by traversing the linked list starting from the first node referenced by Head.
  • The next attribute of the last node refers to a None object. The next attribute of the last node of a linked list will always refer to the None object.
  • If a linked list is empty, the Head variable will refer to the None object.

We now understand the basic structure of a linked list. Let us implement a linked list in Python.

How to Create a Linked List in Python

As nodes are the building blocks of a linked list, we will first create a node. For this, we will define a Node class with attributes data and next as shown below.

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


myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)

Output:

The data in the node is: 10
The next attribute in the node is: None

In the above example, you can observe that the next attribute of the Node refers to None by default. When we insert it into a linked list, we assign the next attribute to the nodes in the linked list, as we will discuss ahead.

We must create an object with the attribute Head to create a linked list. We can define the LinkedList class as shown below.

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


class LinkedList:
    def __init__(self):
        self.Head = None


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)

Output:

The linked list is:
10 20 30 40

In the above example, we created a linked list.

After that, we manually created the nodes using the given data, added them to the linked list one by one, and printed them. Later, we will learn to insert elements into a linked list using Python’s while loop.

Let us now discuss how we can print all the elements of a linked list without manually accessing all the nodes.

We will use a while loop to print all the linked list elements.

Starting from the Head pointer, we will first print the data in the current node using the data attribute of the node. After that, we will move to the next node using the next pointer.

We will follow this process until we reach the end of the linked list (i.e., the next attribute of a node is found to be None). As shown below, you can implement the entire logic in the printList() method.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 20 30 40 

Insert an Element Into a Linked List in Python

There are four situations while inserting an element in a linked list.

  1. The linked list can be empty before insertion.
  2. We have to insert an element at the beginning of a non-empty linked list.
  3. We have to insert an element at the end of a linked list.
  4. We have to insert an element at a given position in the linked list.

Let us discuss how to insert an element into the linked list in all situations.

Insert an Element Into an Empty Linked List

To insert an element into an empty linked list, we will define a method insertIntoEmptyList() that accepts the element as the input argument and adds a node containing the input element into the linked list.

For this, we will create a node in the insertIntoEmptyList() with the input element as the data. After creating the node, we will assign the node to the Head attribute.

In this way, the new node will become the first node of the linked list. The method can be implemented as follows.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 

Insert an Element at the Beginning of a Linked List

To insert an element at the start of a non-empty list, we will define a method insertAtBeginning() that takes an element as input and adds it to the beginning of the linked list. In the insertAtBeginning() method, we will first create a node with the input element as the data.

After that, we will point the next attribute of the newly created node to the node where the Head attribute of the linked list points. Next, we will assign the newly created node to the Head attribute.

In this way, the new node will be inserted at the start of the linked list.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode

    def insertAtBeginning(self, element):
        newNode = Node(element)
        newNode.next = self.Head
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
30 20 10 

As shown below, we can combine the above methods to create a single method to insert an element at the beginning of a linked list.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
30 20 10 

We have merged the insertIntoEmptyList() method into the insertAtBeginning() method because inserting into an empty linked list essentially means that we are inserting an element at the beginning of the linked list.

Insert an Element at the End of a Linked List

Inserting an element at the end of an empty list is similar to inserting the element at the start of the linked list.

To insert an element at the end of a linked list, we will first check if the linked list is empty. If the linked list is found to be empty, we can simply assign a node containing the new element to the Head attribute as we did in the insertAtBeginning() method.

Otherwise, we will traverse the linked list till the end using a while loop. We will start with the Head and keep moving to the next node using the next attribute of the nodes until we find that the next attribute of the node points to None.

Once we reach a node whose next attribute points to None, we are at the last node. Now, we will create a new node using the input data and assign this node to the next attribute of the last node of the linked list.

In this way, the new element will be inserted at the end of the linked list. You can implement this entire logic in the method insertAtEnd() as follows.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 20 30 

Insert an Element at a Given Position in the Linked List

We will use a counter variable and a while loop to insert an element at a given position in the linked list.

We will start from the Head pointer and keep moving to the next node using the while loop. In each iteration, we will also increment the counter variable.

Once we reach the node before the given position, we exit the while loop. Also, we will exit the loop if we reach the end of the linked list. Otherwise, the program will run into an error.

After that, if we are still at the Head, we have to add the element at the first position of the linked list; we will assign the node at the given position to the next pointer containing the new node element. Next, we will assign the new element’s node to the linked list’s Head.

If we don’t have to insert the element at the 1st position, we will assign the node at the given position to the next pointer of the node containing the new element. Next, we will assign the new node to the next attribute of the node at position-1.

In this way, the new element will be inserted at the given position. As shown below, you can implement the entire logic in the insertAtPosition() method.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 
The elements in the linked list are:
10 20 
The elements in the linked list are:
10 20 30 
The elements in the linked list are:
10 40 20 30 

Delete an Element From the Linked List in Python

There can be three situations when we try to delete an element from a linked list.

  1. We have to delete the first element of the linked list.
  2. We have to delete the last element of the linked list.
  3. We have to delete the element at any position in the Linked list.

Let us discuss all these cases one by one.

Delete the First Element of a Linked List

To delete the first element of a linked list, we will first check if the linked list is empty or not.

For this, we will check if the Head of the linked list points to None. If yes, we will inform the user that the linked list is empty and we have no element to delete.

Otherwise, we will assign the first node to a temporary variable. After that, we will assign the second node of the linked list to the Head attribute.

Then, we will delete the first node stored in the temporary variable using the del statement. As shown below, you can implement the entire logic in the deleteFromBeginning() method.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
20 30 

Delete the Last Element of a Linked List

To delete the last element of a linked list, we will first check if the linked list is empty or not.

For this, we will check if the Head of the linked list points to None. If yes, we will inform the user that the linked list is empty and we have no element to delete.

If there are elements present in the list, we will follow the following process.

  1. Assign the first node to a variable current.
  2. Initialize a variable previous to None.
  3. Traverse the linked list using a while loop, assign the node at the current variable to the previous variable, and advance the current variable to the next node until the current variable reaches the last node. In this case, the next attribute of the node assigned to current becomes None.
  4. Once the current variable reaches the last node, we will assign None to the next attribute of the previous variable and delete the node assigned to the current variable.

We can delete the last element of a linked list by executing the above steps. As shown below, you can implement the entire logic in the deleteFromLast() method.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 
The elements in the linked list are:
10 40 

Delete the Element at Any Given Position in the Linked List

To delete an element at any given position in the linked list, we will first check if the linked list is empty or not.

For this, we will check if the Head of the linked list points to None. If yes, we will inform the user that the linked list is empty and we have no element to delete.

If there are elements present in the linked list, and we have to delete an element at any other position, we will follow the following steps.

  1. Assign the first node to a variable current.
  2. Initialize a variable previous to None.
  3. Initialize a variable count to 1.
  4. Traverse the linked list using a while loop, increment count in each iteration, assign the node at the current variable to previous, and advance the current variable to the next node until the count variable has the position of the element to be deleted or we reach the end of the linked list. At this point, the variable current will be referring to the node that has to be deleted.
  5. Once the count becomes equal to the element’s position to be deleted, There can be two situations.
  6. If we are still at the Head, at the 1st position, we will assign the node referred by the next attribute of the current variable to the Head attribute. After that, we will delete the current variable.
  7. If we are not at the 1st position, we will assign the next node of the current variable to the next attribute of the node assigned to the previous variable. We will delete the node assigned to the current variable. In this way, the element at the given position will be deleted.

We can implement the above logic in the deleteAtPosition() method discussed below.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
40 30 

Count the Number of Elements in a Linked List in Python

To count the number of elements in a linked list, we will simply initialize a variable count to 0.

After that, we will start from the Head and move to the next node using a while loop until we reach the end of the linked list. In each iteration of the while loop, we will increment the count by 1.

After executing the while loop, we will have the number of elements in the linked list in the variable count. You can implement this logic as shown in the countElements() method below.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()

Output:

The elements in the linked list are:
10 40 20 30 
Number of elements in the linked list are: 4

Update a Node in the Linked List in Python

There can be two situations to update the value in a node in the linked list.

  1. We need to replace a value.
  2. We need to assign a new value to the element at any given position in the linked list.

Replace a Value in the Linked List

To replace a value in the linked list, we will start from the first node and traverse the linked list using a while loop.

We will check if the current node contains the value to be replaced at each node. If yes, we will replace the value in the current node with the new value.

In this way, we can update the first occurrence of any element in the linked list as shown in the replaceElement() method.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 100 
The elements in the linked list are:
10 40 150 100 

Update the Element at a Given Position in the Linked List

To update the element at a given position in the linked list, we will first check if the linked list is empty. If yes, there can be two situations.

If the linked list is empty and we have to update an element other than the first position, we will notify the user that it cannot be done.

If the linked list is empty and we have to update the element at the first position, we will create a new node with the given element and assign the node to the Head of the linked list. Otherwise, we will initialize a variable counter to 1.

After that, we will traverse the linked list using a while loop. In each iteration of the while loop, we will move to the next node in the linked list, increment the variable counter by 1, and check if we have reached the element’s position that needs to be updated.

If we reach the position that needs to be updated, we will update the value in the current node of the linked list and notify the user.

If we cannot reach the position that needs to be updated and the while loop terminates, we will notify the user that there are not enough elements and we cannot update the value. This logic can be implemented as shown below in the updateAtPosition() method.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()

Output:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 100 30 
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30 

Why Use a Linked List in Python

  • If you don’t need random access to the elements, linked lists can be a better alternative. You should use linked lists instead of normal lists in Python when we have millions of elements to store and don’t need random access.
  • The actual size of lists is very large compared to the number of elements present in them. The actual size of a list is about 1.5 times the number of elements present in it. It ensures that we have enough memory to insert elements into the list. However, a linked list doesn’t require extra spaces.
  • When we insert an element into the linked list, only storage is required. Lists also require contiguous memory location. On the contrary, nodes of a linked list can be present at any location in the physical memory. They are connected using references.
  • You can implement both stack and queue data structures efficiently using linked lists. On the other hand, implementing a queue using a list is costly in time complexity.

Full Implementation Linked List in Python

Following is the full running code for implementing a linked list in Python with all the methods discussed in this article.

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


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")

Conclusion

In this article, we have discussed the linked list data structure and its implementation in Python. We have also implemented the methods for various operations in a linked list.

In this article, we have implemented all the operations using methods. You can also implement each operation using functions that take the linked list’s Head as input and return the head after executing the required operations.

However, this will require more resources during execution. Thus, I suggest you use the approach used in this article.

Related Article - Python Data Structure

  • Implement a Tree Data Structure in Python