Skip to main content
Engineering LibreTexts

4.2: Implementations

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

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    In order to actually use the List ADT, we need to write a concrete data type that implements its interface. There are two standard data types that naturally implement List: the node chain described in the Introduction, normally called a Singly Linked List; and an extension of the array type called a Vector, which automatically resizes itself to accommodate inserted nodes.

    Singly Linked List

    type Singly Linked List<item-type> implements List<item-type>
    

    head refers to the first node in the list. When it's null, the list is empty.

      data head:Node<item-type>
    

    Initially, the list is empty.

      constructor()
        head := null
      end constructor
    
      method get-begin():Sll Iterator<item-type>
        return new Sll-Iterator(head)
      end method
    
    

    The "one past the end" iterator is just a null node. To see why, think about what you get when you have an iterator for the last element in the list and you call move-next().

      method get-end():Sll Iterator<item-type>
        return new Sll-Iterator(null)
      end method
    
      method prepend(new-item:item-type)
        head = make-node(new-item, head)
      end method
    
      method insert-after(iter:Sll Iterator<item-type>, new-item:item-type)
        var new-node:Node<item-type> := make-node(new-item, iter.node().get-next())
        iter.node.set-next(new-node)
      end method
    
      method remove-first()
        head = head.get-next()
      end method
    
    

    This takes the node the iterator holds and makes it point to the node two nodes later.

      method remove-after(iter:Sll Iterator<item-type>)
        iter.node.set-next(iter.node.get-next().get-next())
      end method
    end type
    

    If we want to make get-size() be an \(O(1)\) operation, we can add an Integer data member that keeps track of the list's size at all times. Otherwise, the default \(O(N)\) implementation works fine.

    An iterator for a singly linked list simply consists of a reference to a node.

    type Sll Iterator<item-type>
      data node:Node<item-type>
    
      constructor(_node:Node<item-type>)
        node := _node
      end constructor
    

    Most of the operations just pass through to the node.

      method get-value():item-type
        return node.get-value()
      end method
    
      method set-value(new-value:item-type)
        node.set-value(new-value)
      end method
    
      method move-next()
        node := node.get-next()
      end method
    

    For equality testing, we assume that the underlying system knows how to compare nodes for equality. In nearly all languages, this would be a pointer comparison.

      method equal(other-iter:List Iterator<item-type>):Boolean
        return node == other-iter.node
      end method
    end type
    

    Vector

    Let's write the Vector's iterator first. It will make the Vector's implementation clearer.

    type Vector Iterator<item-type>
      data array:Array<item-type>
      data index:Integer
    
      constructor(my_array:Array<item-type>, my_index:Integer)
        array := my_array
        index := my_index
      end constructor
    
      method get-value():item-type
        return array.get-element(index)
      end method
    
      method set-value(new-value:item-type)
        array.set-element(index, new-value)
      end method
    
      method move-next()
        index := index+1
      end method
    
      method equal(other-iter:List Iterator<item-type>):Boolean
        return array==other-iter.array and index==other-iter.index
      end method
    end type
    

    We implement the Vector in terms of the primitive Array data type. It is inefficient to always keep the array exactly the right size (think of how much resizing you'd have to do), so we store both a size, the number of logical elements in the Vector, and a capacity, the number of spaces in the array. The array's valid indices will always range from 0 to capacity-1.

    type Vector<item-type>
      data array:Array<item-type>
      data size:Integer
      data capacity:Integer
    

    We initialize the vector with a capacity of 10. Choosing 10 was fairly arbitrary. If we'd wanted to make it appear less arbitrary, we would have chosen a power of 2, and innocent readers like you would assume that there was some deep, binary-related reason for the choice.

      constructor()
        array := create-array(0, 9)
        size := 0
        capacity := 10
      end constructor
    
      method get-begin():Vector-Iterator<item-type>
        return new Vector-Iterator(array, 0)
      end method
    

    The end iterator has an index of size. That's one more than the highest valid index.

      method get-end():List Iterator<item-type>
        return new Vector-Iterator(array, size)
      end method
    

    We'll use this method to help us implement the insertion routines. After it is called, the capacity of the array is guaranteed to be at least new-capacity. A naive implementation would simply allocate a new array with exactly new-capacity elements and copy the old array over. To see why this is inefficient, think what would happen if we started appending elements in a loop. Once we exceeded the original capacity, each new element would require us to copy the entire array. That's why this implementation at least doubles the size of the underlying array any time it needs to grow.

      helper method ensure-capacity(new-capacity:Integer)
    

    If the current capacity is already big enough, return quickly.

        if capacity >= new-capacity
          return
        end if
    

    Now, find the new capacity we'll need,

        var allocated-capacity:Integer := max(capacity*2, new-capacity)
        var new-array:Array<item-type> := create-array(0, allocated-capacity - 1)
    

    copy over the old array,

        for i in 0..size-1
          new-array.set-element(i, array.get-element(i))
        end for
    

    and update the Vector's state.

        array := new-array
        capacity := allocated-capacity
      end method
    

    This method uses a normally-illegal iterator, which refers to the item one before the start of the Vector, to trick insert-after() into doing the right thing. By doing this, we avoid duplicating code.

      method prepend(new-item:item-type)
        insert-after(new Vector-Iterator(array, -1), new-item)
      end method
    

    insert-after() needs to copy all of the elements between iter and the end of the Vector. This means that in general, it runs in \(O(N)\) time. However, in the special case where iter refers to the last element in the vector, we don't need to copy any elements to make room for the new one. An append operation can run in \(O(1)\) time, plus the time needed for the ensure-capacity() call. ensure-capacity() will sometimes need to copy the whole array, which takes \(O(N)\) time. But much more often, it doesn't need to do anything at all.

    Amortized Analysis

    In fact, if you think of a series of append operations starting immediately after ensure-capacity() increases the Vector's capacity (call the capacity here \(C\)), and ending immediately after the next increase in capacity, you can see that there will be exactly \({\dfrac {C}{2}}=O(C)\) appends. At the later increase in capacity, it will need to copy \(C\) elements over to the new array. So this entire sequence of \({\dfrac {C}{2}}\) function calls took \({\dfrac {3C}{2}}=O(C)\) operations. We call this situation, where there are \(O(N)\) operations for \(O(N)\) function calls "amortized \(O(1)\) time".

      method insert-after(iter:Vector Iterator<item-type>, new-item:item-type)
        ensure-capacity(size+1)
    

    This loop copies all of the elements in the vector into the spot one index up. We loop backwards in order to make room for each successive element just before we copy it.

        for i in size-1 .. iter.index+1 step -1
          array.set-element(i+1, array.get-element(i))
        end for
    

    Now that there is an empty space in the middle of the array, we can put the new element there.

        array.set-element(iter.index+1, new-item)
    

    And update the Vector's size.

        size := size+1
      end method
    
    

    Again, cheats a little bit to avoid duplicate code.

      method remove-first()
       remove-after(new Vector-Iterator(array, -1))
      end method
    
    

    Like insert-after(), remove-after needs to copy all of the elements between iter and the end of the Vector. So in general, it runs in \(O(N)\) time. But in the special case where iter refers to the last element in the vector, we can simply decrement the Vector's size, without copying any elements. A remove-last operation runs in \(O(1)\) time.

      method remove-after(iter:List Iterator<item-type>)
        for i in iter.index+1 .. size-2
          array.set-element(i, array.get-element(i+1))
        end for
        size := size-1
      end method
    
    

    This method has a default implementation, but we're already storing the size, so we can implement it in \(O(1)\) time, rather than the default's \(O(N).\)

      method get-size():Integer
        return size
      end method
    

    Because an array allows constant-time access to elements, we can implement get- and set-nth() in \(O(1)\), rather than the default implementation's \(O(N)\)

      method get-nth(n:Integer):item-type
        return array.get-element(n)
      end method
    
      method set-nth(n:Integer, new-value:item-type)
        array.set-element(n, new-value)
      end method
    end type
    

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

    • Was this article helpful?