Ի՞նչ է կապված ցանկի վերջում տարր ավելացնելու գործողության ժամանակային բարդությունը։

Կապակցված ցանկի վերջում տարր ավելացնելու գործողության ժամանակային բարդությունը կախված է նրանից, թե ցանկը ունի արդյոք վերջին տարրին ցուցիչ:

• Եթե կա ցուցիչ (tail), ապա ավելացումը կատարվում է O(1) ժամանակում, քանի որ կարելի է անմիջապես ավելացնել նոր տարր վերջինից հետո:
• Եթե ցուցիչ չկա, ապա անհրաժեշտ է անցնել ամբողջ ցանկը, որպեսզի գտնեք վերջին տարրին, և այդ դեպքում բարդությունը կլինի O(n), որտեղ n — տարրերի քանակն է:

Օրինակ՝ ցուցիչով:

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;
        }
    }
}