Mekkora az időbeli komplexitása annak az műveletnek, amikor egy elemet hozzáadunk a láncolt lista végéhez?

A láncolt lista végére történő elem hozzáadásának időkomplexitása attól függ, hogy van-e mutató a lista utolsó elemére.

• Ha van mutató a végére (tail), akkor a hozzáadás O(1) idő alatt történik, mivel azonnal hozzáadhatunk egy új elemet a tail után.
• Ha nincs mutató a végére, akkor végig kell járni az egész listát, hogy megtaláljuk az utolsó elemet, és ekkor a komplexitás O(n) lesz, ahol n a lista elemeinek száma.

Példa mutatóval a végé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;
        }
    }
}