Phone: +91 80884989467 Email: [email protected]
Follow us

Singly Linked List Implementation Using Python

Singly Linked List Implementation Using Python

Hey, I suppose you have read my last article on the Linked list. If don’t then please read it first it will give you a better understanding of the linked list data structure. Here is the URL of the article Introduction to Linked List.

Now let’s implement the Singly Linked List.

Creating Node

Below is the template of the Node element which contains two fields one for data and another for a pointer which connects between Nodes.

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

Inserting Node into the singly linked list

Lets first define the singly linked list class

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

Here I have taken two-pointer one for the head and second for the tail to maintain the tail pointer. So that we don’t have to iterate over and over again at the time of insertion.

Insertion At Tail

Check if the head is pointing to None, if it’s pointing to None that means we linked list is empty(means we have not performed any insert operation). So in that case first create a Node and assign it to the head and then point the head to the tail. Now head and tail pointer is pointing to the same Node. if head is not None which means we have inserted elements to the list, so in that case first create a Node point it to a temporary variable and point tail next pointer to a temporary variable and then move the tail pointer to temporary variable.

class SinglyLinkedList:
    .
    .
    def insertNodeAtTail(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            tmp = Node(data)
            self.tail.next = tmp
            self.tail = tmp
Insertion At Head

If head is None then the case is same as explained in the insertNodeAtTail operation. But if head is not None then create Node and assign it to temporary variable and now point temporary variable next pointer to head and at the end points head to temp. In this overall operation, we are moving one step backward from the head.

    def insertNodeAtHead(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            tmp = Node(data)
            tmp.next = self.head
            self.head = tmp

Print elements of the linked list

Print operation is very important to see the elements for your list. So here I have pointed head to one temporary variable and in the next step written a while loop on the temporary variable and printed data of it.

    def printNodes(self):
        tmp = self.head
        while tmp:
            print(tmp.data)
            tmp = tmp.next

Reverse elements of the linked list

The reverse operation is the most famous interview question asked by interviewers :). So let’s understand it properly. So to perform the reverse operation we need three-pointer 1. prev 2. current & 3. next pointer. As the name suggests the previous pointer points to the last Node of the current pointer. So if the current is pointing to head in that case prev pointer will point to None and same for next pointer which will point to the current of next None. Now loop over current pointer, get next Node then point current of next to prev. Now move the pointers to forward direction by pointing prev to current and current to next and at the end point head pointer to prev pointer.

    def reverseList(self):
        prev = None
        current = self.head
        while current is not None:
            next_ = current.next
            current.next = prev
            prev = current
            current = next_
        self.head = prev

Remove duplicate elements from the linked list

Remove duplicate elements from the linked list is also famous interview question. So basic idea is to remove duplicate elements from the linked list. So simple idea is that if prev Node and current Nodes values are same that means its duplicate. Then point prev pointer to next of next Node and check for the similar condition.

    def removeDuplicateNodes(self):
        prev = self.head
        while prev.next is not None and prev is not None:
            next_ = prev
            while next_.next is not None:
                if prev.data == next_.next.data:
                    dup = next_.next
                    next_.next = next_.next.next
                    del dup
                else:
                    next_ = next_.next
            prev = prev.next
Full Code
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insertNodeAtTail(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            tmp = Node(data)
            self.tail.next = tmp
            self.tail = tmp

    def insertNodeAtHead(self, data):
        if self.head is None:
            self.head = Node(data)
            self.tail = self.head
        else:
            tmp = Node(data)
            tmp.next = self.head
            self.head = tmp

    def removeDuplicateNodes(self):
        prev = self.head
        while prev.next is not None and prev is not None:
            next_ = prev
            while next_.next is not None:
                if prev.data == next_.next.data:
                    dup = next_.next
                    next_.next = next_.next.next
                    del dup
                else:
                    next_ = next_.next
            prev = prev.next

    def printNodes(self):
        tmp = self.head
        while tmp:
            print(tmp.data)
            tmp = tmp.next

    def reverseList(self):
        prev = None
        current = self.head
        while current is not None:
            next_ = current.next
            current.next = prev
            prev = current
            current = next_
        self.head = prev


if __name__ == "__main__":
    sll = SinglyLinkedList()
    sll.insertNodeAtTail(1)
    sll.insertNodeAtTail(8)
    sll.insertNodeAtTail(9)
    sll.insertNodeAtTail(4)
    sll.insertNodeAtTail(3)
    sll.insertNodeAtTail(2)
    sll.insertNodeAtTail(1)
    sll.removeDuplicateNodes()
    sll.printNodes()
Time Complexity of Singly Linked List

Insertion - O(1)

Deletion - O(1)

Access - O(n)

Search - O(n)

Space Complexity - O(n)