Bog'langan ro'yxatning oxiriga element qo'shish operatsiyasining vaqt murakkabligi qanday?

Bog'langan ro'yxatga element qo'shish operatsiyasining vaqt murakkabligi ro'yxat oxiriga ko'rsatkich (pointer) bor-yo'qligiga bog'liq.

• Agar oxiriga ko'rsatkich (tail) bo'lsa, qo'shish O(1) vaqt oladi, chunki yangi elementni darhol tail'dan keyin qo'shish mumkin.
• Agar tail ko'rsatkichi bo'lmasa, oxirgi elementni topish uchun butun ro'yxatni aylanib chiqish kerak bo'ladi va bu holda murakkablik O(n) bo'ladi, bu yerda n ro'yxatdagi elementlar soni.

Tail ko'rsatkichi bilan misol:

class LinkedList {
    Node head;
    Node tail;

    void addLast(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
}