Linear List

• A generic linear list of objects

• Internal implementation may vary.

• Array Implementation:

  

• Linked List Implementation

  

• Task : Want to run through all values in a linear list.

• If the list is an array with public access then we can write something like this:

int i;
for(i=0;i<data.length;i++)
		// do something with data[i]

• Similarly for a linked list with public access , we can write something like this:

Node m;
for( m= head; m != null; m = m.next){
	//do something with m.data
}

• But we don’t know which function to use above because the internal implementation is hidden!!

Iterators

• Need something like this:

  Start at the beginning of the list;
  while (there is a next element){
  	get the next element;
  	do something with it;
  }
  

• Do this by encapsulating in an interface called Iterator

  public interface Iterator{
  	public abstract boolean has_next();
  	public abstract Object get_next();
  

• Now how do we implement this Iterator in LinearList

  • Need a pointer to remember position of the iterator.
  • Also need to handle the case of nested loop iteration.

• Solution : Create an Iterator object and export it!!

  

• Now we can traverse easily: