(Almost) everything you need for your Single Linked List adventures

single_linked_list_ops.py

class Node():
    """
    Basic component for single linked list - A node
    A node consist of a value and a pointer to another node
    """
    def __init__(self, data):
        self.val = data
        self.next = None


class LinkedList():

    """
    A linked list is a collection of nodes sequentially attached
    """
    def __init__(self):
        self.head = None

    def printList(self):
        """
        Print the values in a linked list - O(n)
        """
        temp = self.head
        while temp:
            print(temp.val, end = " ")
            temp = temp.next

    def findLength(self):
        """
        Find the number of nodes in the linked list - O(n)
        """
        length = 0
        tmp = self.head
        
        while tmp:
            length += 1
            tmp = tmp.next

        return length


    def insertNodeAtHead(self, data):
        """
        Comparing to arrays, the biggest advantage of a linked list is insertion/deletion

        Arrays insertion/deletion - O(n) 
        Linked list insertion/deletion - O(1)
        """
        node = Node(data)
        if self.head:
            node.next = self.head
        self.head = node
           

    def insertNodeAtTail(self, data):
        """
        Comparing to arrays, the biggest advantage of a linked list is insertion/deletion

        Arrays insertion/deletion - O(n) 
        Linked list insertion/deletion - O(1)

        If tail is given, we could avoid the loop in the function 
        """

        if self.head:
            tmp = self.head
            while tmp.next:
                tmp = tmp.next
            tmp.next = Node(data)
        else:
            self.head = Node(data)

    def insertNodeAtPosition(self, data, position=None):
        """
        Comparing to arrays, the biggest advantage of a linked list is insertion/deletion

        Arrays insertion/deletion - O(n) 
        Linked list insertion/deletion - O(1)
        """

        if not position:
            return self.insertNodeAtTail(data)
        
        if position == self.findLength():
            return self.insertNodeAtTail(data) 

        tmp = self.head
        tmp_pos = 0
        newNode = Node(data)

        while tmp_pos < position:
            tmp = tmp.next
            tmp_pos += 1
        
        # Store current next node for post insertion
        current_next_node = tmp.next
        # Insert new node
        tmp.next = newNode
        # Next of new node the node we've stored before
        newNode.next = current_next_node

    def deleteNode(self, position):
        """
        Comparing to arrays, the biggest advantage of a linked list is insertion/deletion

        Arrays insertion/deletion - O(n) 
        Linked list insertion/deletion - O(1)
        """

        tmp = self.head

        if position == 0:
            head = head.next
        else:
            tmp_pos = 0
            while tmp_pos < position:
                tmp = tmp.next
                tmp_pos += 1
            if tmp.next:
                tmp.next = tmp.next.next
            else:
                tmp.next = None

    def reverseList(self):
        """
        Reverse the linked list by reversing the next node of each node - O(n)
        """
        prev_node = None
        next_node = None
        current_node = self.head

        while current_node:
            #  Save the next element for later swapping
            next_node = current_node.next
            # Remap current element's next to previous node
            # This is the reversal step
            current_node.next = prev_node
            # Now current is the prev node as we are shifitng right
            prev_node = current_node
            # Next node Saved before is now reset, we move to next value in the right
            current_node = next_node

        self.head = prev_node

    
    def getNode(self, positionFromTail):
        """
        Get value of a node from a given position from tail - O(n)
        """

        lenList = self.findLength()

        pos_from_head = lenList - positionFromTail 

        tmp = self.head
        for i in range(pos_from_head):
            tmp = tmp.next

        return tmp.val

    def removeDuplicates(self):
        """
        Remove all the duplicate nodes in a linked list - O(n)
        """

        seen = set()
        tmp = self.head
        seen.add(tmp.val)

        while tmp.next:
            if tmp.next.val in seen:
                tmp.next = tmp.next.next
            else:
                seen.add(tmp.next.val)
                tmp = tmp.next

    def has_cycle(self):
        """
        Check if the linked list has a cycle in it - O(n)
        """

        tmp = self.head
        node_set = set()
        while tmp:
            if tmp.next in node_set:
                return 1
            node_set.add(tmp.next)
            tmp = tmp.next
        return 0
    
    def __eq__(self, other):
        if self.findLength() != other.findLength():
            return False

        linkedListOneHead = self.head
        linkedListTwoHead = other.head

        while linkedListOneHead:
            if linkedListOneHead.val != linkedListTwoHead.val:
                return False
            linkedListOneHead = linkedListOneHead.next
            linkedListTwoHead = linkedListTwoHead.next
        return True

    



# if __name__ == "__main__":

#     aList = LinkedList()
#     aList.insertNodeAtTail(10)
#     aList.insertNodeAtTail(11)
#     aList.insertNodeAtTail(12)

#     print(aList.printList())
#     aList.reverseList()
#     print("\nList after reversal:")
#     print(aList.printList())
#     aList.reverseList()
#     print("\nList after second reversal:")
#     print(aList.printList())

#     print(aList == aList)
#     aList.removeDuplicates()

#     print(aList.printList())