LinkedList used in an interview's test

Question

[EDIT]Fixed my code. Is while(temp != NULL), not while(temp->next != NULL). Sorry to insert wrong code.

Today I've participated an online programming test. The interviewer used Codility to evaluate my code and the other interviewees. At some moment a question about Linked list was made. It's about to count how many items a linked list has. I did the only possible approach to do this, AFAIK:

//This is struct declaration
struct SomeStruct
{
    int value;
    SomeStruct* next;
}

int elementCount(SomeStruct* list)
{
    int count = 0;
    if(list != NULL)
    {
        SomeStruct* temp = list;
        while(temp != NULL)
        {
            count++;
            temp = temp->next;
        }
    }
    return count;
}

I remember when I send this code as answer for this question, Codility points me out that this solution is wrong because its consume too much time to execute the task. In my head and in this thread on SO there's no other way to get size of linked list without traversing it, not in a simple way.

Is there a problem with Codility when it says this solution is wrong? Or there are another approaches?

PS: the test allowed using of STL

Answer 1

well you don't have to evaluate the indirection temp->next twice for each iteration.

you can simply do

int count( SomeStruct const* pNode )
{
    int result = 0;
    while( pNode != 0 )
    {
        ++result;
        pNode = pNode->next;
    }
    return result;
}

Also, as WhozCraig notes, your code was logically wrong (yielding an off by one result), not just potentially inefficient.

Answer 2

Your solution is incorrect, since it returns 1 less than the actual count. Just try applying it to a list with 1 element.

Why did you come up with this strange two-tiered structure with an if and and a cycle that checks temp->next? Why not just

unsigned elementCount(const SomeStruct *list)
{
  unsigned count = 0;
  for (const SomeStruct *temp = list; temp != NULL; temp = temp->next)
    ++count;
  return count;
}

I suspect that you decided to treat the element pointed by the list as the unused and reserved "header" element. Indeed, sometimes it might make sense to do implement lists that way. But I see nothing like that stated in your post. Did they tell you to treat it that way specifically?

Answer 3

Codility may be using a circularly linked list to check, in this case, your code will never end.

Using STL trivilailzes this though, as it has a List<> with a size method.