# 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!

**Partners Ads**personalised mugs sport tickets