Singly Linked Lists

[hassan_]

Hi guys I'm just revising for my data structure and algorithms exam and got stuck on a few questions can someone help me with this one please:

Of the following what statement is NOT true about Singly Linked Lists:

1. Traversing the list backwards is not efficiently possible.
2. Removing the next elemet of a given node is possible efficiently.
3. Finding any list element is possible in constant time.
4. Singly linked list needs less memory than doubly linked list with the same contents.

And why is this not true about Singly linked lists?

Thanks.

Has.

[laserlight]

Try a process of elimination first: which of those statements are true about singly linked lists?

[hassan_]

I personally thought the answer was,

3. Finding any list element is possible in constant time.

But I just wanted a bit of clarification.

[laserlight]

I'd say that you are correct. Note that there is a second part to the question though, and ironically it would help you confirm that your answer is correct :)

[hassan_]

The reason I thought the answer was 3. was because for any given list of of n elements, the search for an element it takes O(n) steps and thus finding an element in a singly linked list is not done in constant time.

Am I right in saying that?