Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

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,
  1. check, if the end of a list hasn't been reached yet;
  2. do some actions with the current node, which is specific for particular algorithm;
  3. 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.

Singly-linked list traversal example
Singly-linked list traversal example, step 1
Singly-linked list traversal example, step 2
Singly-linked list traversal example, step 3
Singly-linked list traversal example, step 4
Singly-linked list traversal example, final state


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

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

One response to "Singly-linked list traversal tutorial"

  1. Guest on Feb 11, 2009 said:

    nice


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        

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: