Quick Index
Overview


Here I am again. A LinkedList. I want to talk about how I traverse (visit) all or some of my nodes.

Note that I have a "firstNode". Thus I will start there, and then I will simply "traverse" (walk) forward through all the nodes and I will end when I get to my "lastNode".

I could also start at "lastNode" and traverse backward back through all my nodes and end at "firstNode".
How Do I Detect the Last Node?
Can you guess how I detect when I am at the last node?


Remember that, for the last node only, the "nextLink" is null.

Thus, for the node I am currently visiting, I can simply test to see if "nextLink" is null. If so, I'm at the end of the list (at the last node).
How to Detect the First Node?
Can you guess how I detect when I am at the first node?


Remember that, for the first node only, the "prevLink" is null.

Thus, for the node I am currently visiting, I can simply test to see if "prevLink" is null. If so, I'm at the start of the list (at the first node).


Prep for Traversing (Looping)


Let's assign my "firstNode" to a temporary variable. We can call it anything -- let's use "nextNode".

The object "this" is me (a LinkedList object)!

nextNode = this.firstNode


Traversing (Looping)


Here we go on our traversal -- hang on tight!

Visit Node1
 nextNode = this.firstNode;

We are now at "Node1".

And we can "do whatever" as we visit this node (and its data)! We "do whatever inside the loop block.
Move to Node2
 nextNode = nextNode.getNextNode();

We are now at "Node2".

And we can again do what we need to do during this "visit".
Move to Node3
 nextNode = nextNode.getNextNode();

We are now at "Node3".

And again we "visit" how we like.
The End
 nextNode = nextNode.getNextNode();

Node3's next node is null. We have reached the end.

In the next step, we'll try to come up with an algorithm that describes the traversal fun we just had.


Algorithm


The linked list traversal algorithm is simple, as shown here.

let nextNode = this.firstNode
while (nextNode != null) {
	Do Whatever
	nextNode = nextNode.getNextNode()
}
Note: "this" is me (i.e., a LinkedList)






























Data Structures And Algorithms (DSA) (Chapter 401 - Linked List Logic)










Chapter 401 - Linked List Logic Traversing a Linked List

Contents Intro OO Review Concepts Design Traversal Algorithms Memory

Chapter Top Search TOC