Singly-linked list. Traversal.
Assume, that we have a list with some nodes. Traversal is the very basic operation, which presents as a part in almost every operation on a singly-linked list. For instance, algorithm may traverse a singly-linked list to find a value, find a position for insertion, etc. For a singly-linked list, only forward direction traversal is possible.
Traversal algorithm
Beginning from the head,- check, if the end of a list hasn't been reached yet;
- do some actions with the current node, which is specific for particular algorithm;
- current node becomes previous and next node becomes current. Go to the step 1.
Example
As for example, let us see an example of summing up values in a singly-linked list.
For some algorithms tracking the previous node is essential, but for some, like an example, it's unnecessary. We show a common case here and concrete algorithm can be adjusted to meet it's individual requirements.
Code snippets
Although we have two classes for singly-linked list, SinglyLinkedListNode class is used as storage only. Whole algorithm is implemented in the SinglyLinkedList class.
Java implementation
public class SinglyLinkedList {
…
public int traverse() {
int sum = 0;
SinglyLinkedListNode current = head;
SinglyLinkedListNode previous = null;
while (current != null) {
sum += current.value;
previous = current;
current = current.next;
}
return sum;
}
}
C++ implementation
int SinglyLinkedList::traverse() {
int sum = 0;
SinglyLinkedListNode *current = head;
SinglyLinkedListNode *previous = NULL;
while (current != NULL) {
sum += current->value;
previous = current;
current = current->next;
}
return sum;
}
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)
One response to "Singly-linked list traversal tutorial"
- on Feb 11, 2009 said:
nice
| Previous: Internal representation | Next: Adding a node to a singly-linked list |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!