traversing a singly linked list in C++_问答_开发者

I was wondering if it is possible to traverse a linked开发者_Python百科 list like this:


currentNode = randomNode;//where randomNode may or may not = firstNode
prevNode = firstNode;
while(prevNode != currentNode && prevNode->link != currentNode)
{
    prevNode = prevNode->link;
}

Is it possible to do this in C++ when I am trying to find the node before currentNode in a singly linked list?

I trying to implement something like this in a console app for a school assignment so assume that I can't use anything fancy like the boost libraries/list/anything that makes life easier, etc. So basically, I have only fairly primitive datatypes and libraries at my disposal.

You might want to make sure that prevNode->link is not a null reference either, in case currentNode is not actually linked.

That should work just fine. Have you tried it yet?

That code will traverse some part of your list, but which part depends on which way your list is linked. If it goes from head->tail (read: head node links to a node which links towards tail) then you would traverse your list starting from the random location to the tail. If the links are head<-tail then you would traverse from the random location to the head. In either case, you would not touch all the nodes in the list.

All of the above assumes some link list as such:

[head]<->[0...N Nodes]<->[Tail]

The links could be either way.

Also, you could link the head and tail nodes and create a circularly linked list. In that scenario, it is possible to visit all nodes by simply traversing until you are back to your original node.

Make sure you consider all of the possible edge cases:

What happens randomNode equals firstNode? What do you return? What should you return?
What happens when randomNode is the last node in the list?
What happens when randomNode is NULL?
What happens when randomNode is not in the list?

Now, not all of these cases may be applicable, depending on if you know anything about randomNode, and some of these may be trivial. But they are all worth thinking about.

If you consider all of these very carefully, there is a simple and elegant solution that handles them all.

The code looks fine, but I would suggest a minor change to your while condition

while(prevNode != currentNode && prevNode != NULL)

For two reasons

Your code, as currently stated, could stop if the node we are looking for is pointed to by either prevNode or prevNode->link (and therefore we will have no idea which particular one of the two points to currentNode -- if we wanted to know, we would have to check with an if condition). With the change above, the target node is guaranteed to be stored in prevNode (if at all -- see next point).
For safety's sake, it would be good to check that prevNode is not NULL. However, as Pavel mentions, this test is unnecessary if currentNode is guaranteed to be in the list.

Edit in response to comment

Given that you don't need to know whether currentNode is in prevNode or prevNode->link, and since you want to stop (if possible) on currentNode == prevNode->link, then your original while is fine. However...

there is an if statement higher up in the code that prevents prevNode from being null already

It seems like you're missing the point of why you should check for NULL. Yes, that's good you check it before, but the reason why we have the NULL check in the loop is in the case where currentNode is not in the list, so you eventually reach the last node. Presumably (if you do this like most other linked lists) the value of link for your last node is NULL. If so, your current code will eventually end up calling NULL->link which of course will crash your program. That's why you should still check for NULL

while(prevNode != NULL && prevNode != currentNode && prevNode->link!=currentNode)

If you're absolutely sure that currentNode will be in the list, then I guess that check is also unnecessary, but it really is a good habit to get into.

You can even have:

while (prevNode && prevNode != currentNode)
    prevNode = prevNode->link;

But what you have looks fine.

A small thing I'd change with the code as posted (aside from the possibility discussed in other answers of running off the end of the list if currentNode isn't on the list or other error handling) is that when the while loop is done you don't know if prevNode or prevNode->link points to currentNode. This isn't a huge problem (since you can easily test for it), but it seems to me that it's best to test for this special case situation before the search, so it's clear that it's a special case.