\manpage {slist} {E} {Singly Linked Lists}
 
\definition
An instance $L$ of the parameterized data type \name\ is a sequence of items
($slist\_item$). Each item in $L$ contains an element of data type $E$, called
the element type of $L$. The number of items in $L$ is called the length of $L$. If $L$ has length zero it is called the empty list. In the sequel $\<x\>$ is
used to denote a list item containing the element $x$ and $L[i]$ is used to
denote the contents of list item $i$ in $L$.
 
\creation L 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes it to
            the empty list. }
 
 
\create {(E\ x)}
   { creates an instance \var\ of type \name\ and initializes it to
            the one-element list $\<x\>$.  }
 
 
\operations 2 5 
 
\op  int length {()}
           {  returns the length of $L$. }
 
 
\op  int size {()}
           {  returns $L$.length(). }
 
 
\op  bool empty {()}
           {  returns true if $L$ is empty, false otherwise. }
 
 
\op  slist\_item first {()}
           {  returns the first item of $L$. }
 
 
\op  slist\_item last {()}
           {  returns the last item of $L$. }
 
 
\op  slist\_item succ {(slist\_item\ it)}
           {  returns the successor item of item $it$, nil if
	     $it=L$.last().\\
	     \precond $it$ is an item in $L$. }
 
 
\op  slist\_item cyclic\_succ {(slist\_item\ it)}
           {  returns the cyclic successor of item $it$, i.e.,
	     $L$.first() if $it = L$.last(), $L$.succ($it$) otherwise. }
 
 
\op  E contents {(slist\_item\ it)}
           {  returns the contents $L[it]$ of item $it$.\\
	     \precond $it$ is an item in $L$. }
 
 
\op  E inf {(slist\_item\ it)}
           {  returns $L$.contents($it$).\\
             \precond $it$ is an item in $L$. }
 
 
\op  E  head {()}
           {  returns the first element of $L$, i.e. the contents
	     of $L$.first().\\
	     \precond $L$ is not empty. }
 
 
\op  E  tail {()}
           {  returns the last element of $L$, i.e. the contents
	     of $L$.last().\\
	     \precond $L$ is not empty. }
 
 
\op  slist\_item push {(E\ x)}
           {  adds a new item $\<x\>$ at the front of $L$ and returns it.  }
 
 
\op  slist\_item append {(E\ x)}
           {  appends a new item $\<x\>$ to $L$ and returns it.  }
 
 
\opl slist\_item insert {(E\ x, \ slist\_item\ it)}
           {  inserts a new item $\<x\>$ after item $it$ into $L$ and
             returns it.\\
	     \precond $it$ is an item in $L$. }
 
 
\op  E pop {()}
           {  deletes the first item from $L$ and returns its
             contents. \\
	     \precond $L$ is not empty. }
 
 
\op  void conc {(slist\<E\>\&\ L1)}
           {  appends list $L1$ to list $L$ and makes $L1$ the empty list.\\
\precond $L != L1$ }
 
 
\arrop E\&  {slist\_item\ it}
         {  returns a reference to the contents of $it$. }
 
 
\binop slist\_item += {E\ x}
         {  appends a new item $\<x\>$ to $L$ and returns it.  }
 
 
