4: List Structures and Iterators

Last updated
Save as PDF

Page ID: 46702

Wikibooks - Data Structures
Wikipedia

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

We have now seen two different data structures that allow us to store an ordered sequence of elements. However, they have two very different interfaces. The array allows us to use get-element() and set-element() functions to access and change elements. The node chain requires us to use get-next() until we find the desired node, and then we can use get-value() and set-value() to access and modify its value. Now, what if you've written some code, and you realize that you should have been using the other sequence data structure? You have to go through all of the code you've already written and change one set of accessor functions into another. What a pain! Fortunately, there is a way to localize this change into only one place: by using the List Abstract Data Type (ADT).

List<item-type> ADT

get-begin():List Iterator<item-type>

Returns the list iterator (we'll define this soon) that represents the first element of the list. Runs in \(O(1)\) time.

get-end():List Iterator<item-type>

Returns the list iterator that represents one element past the last element in the list. Runs in \(O(1)\) time.

prepend(new-item:item-type)

Adds a new element at the beginning of a list. Runs in \(O(1)\) time.

insert-after(iter:List Iterator<item-type>, new-item:item-type)

Adds a new element immediately after iter. Runs in \(O(N)\) time.

remove-first()

Removes the element at the beginning of a list. Runs in \(O(1)\) time.

remove-after(iter:List Iterator<item-type>)

Removes the element immediately after iter. Runs in \(O(N)\) time.

is-empty():Boolean

True if there are no elements in the list. Has a default implementation. Runs in \(O(1)\) time.

get-size():Integer

Returns the number of elements in the list. Has a default implementation. Runs in \(O(N)\) time.

get-nth(n:Integer):item-type

Returns the nth element in the list, counting from 0. Has a default implementation. Runs in \(O(N)\) time.

set-nth(n:Integer, new-value:item-type)

Assigns a new value to the nth element in the list, counting from 0. Has a default implementation. Runs in \(O(N)\) time.

The iterator is another abstraction that encapsulates both access to a single element and incremental movement around the list. Its interface is very similar to the node interface presented in the introduction, but since it is an abstract type, different lists can implement it differently.

List Iterator<item-type> ADT

get-value():item-type

Returns the value of the list element that this iterator refers to.

set-value(new-value:item-type)

Assigns a new value to the list element that this iterator refers to.

move-next()

Makes this iterator refer to the next element in the list.

equal(other-iter:List Iterator<item-type>):Boolean

True if the other iterator refers to the same list element as this iterator.

All operations run in \(O(1)\) time.

There are several other aspects of the List ADT's definition that need more explanation. First, notice that the get-end() operation returns an iterator that is "one past the end" of the list. This makes its implementation a little trickier, but allows you to write loops like:

var iter:List Iterator := list.get-begin()
while(not iter.equal(list.get-end()))
 # Do stuff with the iterator
 iter.move-next()
end while

Second, each operation gives a worst-case running time. Any implementation of the List ADT is guaranteed to be able to run these operation at least that fast. Most implementations will run most of the operations faster. For example, the node chain implementation of List can run insert-after() in \(O(1)\).

Third, some of the operations say that they have a default implementation. This means that these operations can be implemented in terms of other, more primitive operations. They're included in the ADT so that certain implementations can implement them faster. For example, the default implementation of get-nth() runs in \(O(N)\) because it has to traverse all of the elements before the nth. Yet the array implementation of List can implement it in \(O(1)\) using its get-element() operation. The other default implementations are:

abstract type List<item-type>
 method is-empty()
  return get-begin().equal(get-end())
 end method

 method get-size():Integer
  var size:Integer := 0
  var iter:List Iterator<item-type> := get-begin()
  while(not iter.equal(get-end()))
   size := size+1
   iter.move-next()
  end while
  return size
 end method

 helper method find-nth(n:Integer):List Iterator<item-type>
  if n >= get-size()
   error "The index is past the end of the list"
  end if
  var iter:List Iterator<item-type> := get-begin()
  while(n > 0)
   iter.move-next()
   n := n-1
  end while
  return iter
 end method

 method get-nth(n:Integer):item-type
  return find-nth(n).get-value()
 end method

 method set-nth(n:Integer, new-value:item-type)
  find-nth(n).set-value(new-value)
 end method
end type