Kāda ir saistītā saraksta beigās elementa pievienošanas operācijas laika sarežģītība?

Laika sarežģītība operācijai, pievienojot elementu saistītā sarakstā, atkarīga no tā, vai sarakstā ir norāde uz pēdējo elementu.

• Ja ir norāde uz asti (tail), pievienošana notiek O(1) laikā, jo var uzreiz pievienot jaunu elementu pēc asti.
• Ja norāde uz asti nav, ir jāiziet cauri visam sarakstam, lai atrastu pēdējo elementu, un tad sarežģītība būs O(n), kur n ir elementu skaits sarakstā.

Piemērs ar norādi uz asti:

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