Data Structures & Algorithms Lecture Notes

24 September 2009 • List Traversal

Outline

• Element access.

• Iterators

• Traversals

Element Access

• Need a way to reference an element in a list.

  • The reference can be used to further manipulate the element.

    • Delete this element; increase this element’s value by one; insert a new element before this one.

• Arrays use indices to reference elements.

Reference Operations

• Element references can themselves can support operations.

  • Is this the first or last element in the list?

  • Get a reference to the element before or after this one.

  • Are these two references the same?

• Note the possibility of several references at the same time.

A Reference Class

class LinkedList {
  class Iterator { ... }
  // and so on
  }

• An iterator is a reference to a list element.

  • An inner class ties the iterator to the list class.

  • There’s no reason to leave them untied.

• LinkedList.Iterator i = ...

Creating Iterators

• There are numerous ways to return iterators.

  class List<T> {
    Iterator find(T value) { ... } 
    Iterator firstElement() { ... } 
    Iterator LastElement() { ... } 
    Iterator next(Iterator i) { ... } 
    Iterator previous(Iterator i) { ... } 
    }
  

• Other iterator-creating operations can build on these.

Iterator References

• To what does an iterator refer?

  • The choices are to the element itself or to the link containing the element.

• Well designed iterators should hide the implementation.

  • That is, refer to values, not links.

  • Hiding the links makes it easy to change the list implementation.

Implementing Iterators

• Inner-class iterators have access to the list implementation.

  • List manipulations are simple and secure.

• A separate iterator class requires special data and operators.

  • There's no protection against unauthorized operator use.

Iterator Methods

• There are a number of other useful iterator methods:

    boolean atBeginning() { ... }
    boolean atEnd() { ... }
    boolean equals(Iterator i) { ... }
    T getValue() { ... }
  

• Be careful to distinguish between operations on iterators and operations on the list.

  • Maintain separation of concerns.

Iterator Under Change

• What should happen to an iterator if the associated element changes?

  • Deleting an element, or inserting a new element before or after.

• With deleting, should the iterator become useless, or move to another element?

• With inserting, should the iterator move to the new element, or stay with the original one?

  • Or maybe something else.

List Extremes

• What does it mean to be at one end of the list?

  • It could mean being at the actual ends, or

  • being one past the ends on a phantom element.

• Actual ends are simple and safe, but could lead to difficult manipulations.

• Phantom ends lead to simple and regular manipulations, but are dangerous.

List Traversal

• Iterators enable arbitrary traversal patterns through elements.

  void drunkardsWalk(List<?> l, int steps)
  
    int n = l.size()
    List.Iterator here = l.begin()
  
    while steps-- > 0
      int m = random(2n) - n
      while m < 0 ∧ here ≠ l.begin()
        here = here.previous()
        ++m
      while m > 0 ∧ here ≠ l.end()
        here = here.next()
        --m
      f(here.value())

External Traversals

• Client-directed traversals are external traversals.

  • Implemented externally to the data structure.

• External traversals are

  • complicated: what methods are needed?

  • clumsy: client-visible details.

  • dangerous: invalid operations.

Internal Traversals

• Internal traversals are an alternative to external traversals.

• Internal traversals are implemented within the data structure.

  class list<T>
    void forEach(UnaryFunction<T> f)
      // call f on every element in the list.
  
  UnaryFunction<String> printer = 
    new UnaryFunction<String>(System.out)
  stringList.forEach(printer)
  

Comparison

• Internal traversals are

  • simpler: one method per traversal type.

  • straightforward: a minimum of details.

  • safer: the fiddly bits are hidden.

• However, internal traversals are limited to what the data structure provides.

  • A random walk using forEach()?

InEx Traversals

• InEx traversals are a happy medium (?) between internal and external traversals.

  • Some of the details are implemented in the data structure.

  • Other details are implemented elsewhere (in the language, usually).

  List<String> stringList = new ...
  for (String s: stringList)
    // operate on s
  

Summary

• Data structures should provide abstract access to contained elements.

  • Access through iterators.

• Iterators should not be leak the internal details of the associated data structure.

• Methods for internal traversals can be simpler and, with the right language, more powerful than external traversals.

References

• Iterators: Signs of Weakness in Object-Oriented Languages by Henry Baker, ACM OOPS Messenger, pages 18-25, July, 1993.