How to know if this while loop is O(n) or O(1)?

Question

I have the task to code a method that return the length of a self-made linked list. The method must be in constant time O(1). My idea was to increment the counter by 1 always that a node in a linked list isn't null and not mess with the size of the list at all to avoid O(n).

My code:

public int getLength() {
    // TODO Code hier einfügen
    
    if (headNode == null) {
        return 0;
    } 

    int count = 0;
    while (headNode != null)
    {
        count++;
        headNode = headNode.next;
    }
    return count;
}

Is my code in constant time O(1)? If not how would you create a length method for a linked list in O(1)?

Answer 1

Your code is O(n) since you are traversing all the nodes of the linked list atleast once. To address second part of your question, there are two ways it can be done:

1. Define a static variable length, everytime you add or remove an element from the list, you have to update this variable.
2. Change the structure of your nodes to store the index of everynode or in the head node keep an extra pointer length that keeps track of length of the linked list.

Hope this helps.. Happy Coding :)