2.2.2. ALGORITHMS & DATASTRUCTURES. LINKED LISTS. ANOTHER VARIANT OF OPTIMIZING THE APPEND METHOD. TIME COMPLEXITY O(1).

The algorithm in the last article every time we insert a new element, the algorithm iterates through all the cells of the list until it reaches the last one. Then the algorithm links the last element with the new one. The complexity of such traversal will always be O(n). Without an early ending option. However, we can modify the code so that it runs in constant time O(1). For this, we should create another pointer that will link to the last element self.tail = None. Now, every time we add a new cell, we just need to access the tail attribute and return the last element. Next, we need to create a link from this element to the new one and then update the tail. As we don't have to iterate through all the cells, the insertion will work instantly.

class Node:
    def __init__(self, value=None, next_node=None):
        self.value = value
        self.next_node = next_node

    def __str__(self):
        return str(self.value)

class List:
    def __init__(self):
        # limiter
        self.top = Node()
        self.tail = None

    def append(self, value):
        '''
        Adding a new element to the end of a linked list.
        Operating time O(n).
        '''

        # Iterating through all elements sequentially to find the last one
        current = self.top
        while current.next_node is not None:
            current = current.next_node

        # Creating a reference for the last element to the new one
        current.next_node = Node(value)

    def __str__(self):
        '''
        Returns all elements of the linked list as a string
        '''
        current = self.top.next_node
        values = "["
        while current is not None:
            end = ", " if current.next_node else ""
            values += str(current) + end
            current = current.next_node

        return values + "]"

lst = List()
lst.append(75)
lst.append(12)
lst.append(28)
lst.append(6)
print(lst)