Байланысқан тізімнің соңына элемент қосу операциясының уақыттық күрделілігін қалай анықтауға болады?

Қосымша элементті байланысты тізімнің соңына қосу уақыттық күрделілігі тізімнің соңғы элементке көрсеткіші бар-жоғына байланысты.

• Егер соңғы элементке көрсеткіш болса, қосу O(1) уақыт алады, себебі жаңа элементті тікелей соңғыдан кейін қосуға болады.
• Егер соңғы элементке көрсеткіш болмаса, барлық тізімді өтіп, соңғы элементті табу керек, және сол кезде күрделілік O(n) болады, мұнда n — тізімдегі элементтер саны.

Python-да соңғы көрсеткіші бар мысал:

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

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

    def append(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

Мұнда append әдісі тұрақты уақытта O(1) жұмыс істейді.