Skip to main content
Engineering LibreTexts

4: List Structures and Iterators

  • Page ID
    46702
  • \( \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}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    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
    


    This page titled 4: List Structures and Iterators is shared under a CC BY-SA license and was authored, remixed, and/or curated by Wikibooks - Data Structures (Wikipedia) .

    • Was this article helpful?