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
equalsfirstNode
? What do you return? What should you return? - What happens when
randomNode
is the last node in the list? - What happens when
randomNode
isNULL
? - 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
orprevNode->link
(and therefore we will have no idea which particular one of the two points tocurrentNode
-- if we wanted to know, we would have to check with anif
condition). With the change above, the target node is guaranteed to be stored inprevNode
(if at all -- see next point). - For safety's sake, it would be good to check that
prevNode
is notNULL
. However, as Pavel mentions, this test is unnecessary ifcurrentNode
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.
精彩评论