sdds
Class SList<O>

java.lang.Object
  extended by sdds.List<O>
      extended by sdds.SList<O>
Type Parameters:
O - the type of object the list will hold

public class SList<O>
extends List<O>

A static singly-linked List.

Author:
Stephen G. Ware

Field Summary
 
Fields inherited from class sdds.List
last, length
 
Constructor Summary
  SList()
          Construct an empty static list.
protected SList(int length, sdds.List.Node<O> first)
          Construct a static list with a given size and a given first node.
  SList(O[] elements)
          Construct a static list which initially contains a given set of elements.
 
Method Summary
 SList<O> add(List<O> otherList)
          Add every element from otherList to the static list.
 SList<O> add(O element)
          Add an element to the static list in O(1) time.
 SList<O> add(O[] elements)
          Add x elements to the static list in O(x) time.
 SList<O> clone()
          Return a deep copy of the dynamic list.
protected  SList<O> makeList(int length, sdds.List.Node<O> first)
          This protected method is used instead of a constructor to create new lists when this list is modified.
 SList<O> remove(O element)
          Remove the first instance of a given object from the static list in O(n) time.
 SList<O> removeAll(O element)
          Remove every instance of a given object from the static list in O(n) time.
 SList<O> removeAllEquals(O element)
          Remove every instance of a given object from the list in O(n) time.
 SList<O> removeEquals(O element)
          Remove the first instance of a given object from the static list in O(n) time.
 
Methods inherited from class sdds.List
contains, containsEquals, equals, get, getLast, iterator, length, toArray, toString
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

SList

protected SList(int length,
                sdds.List.Node<O> first)

Construct a static list with a given size and a given first node.

Parameters:
length - the number of elements in the list
first - the first node in the list

SList

public SList()

Construct an empty static list.


SList

public SList(O[] elements)

Construct a static list which initially contains a given set of elements.

This constructor is more efficient in both time and space than creating an empty static list and then adding the elements to it.

Parameters:
elements - the elements the list will initially contain
Method Detail

makeList

protected SList<O> makeList(int length,
                            sdds.List.Node<O> first)

This protected method is used instead of a constructor to create new lists when this list is modified.

All subclasses of SList should use this method instead of a constructor. This method can be overridden in a subclass and made to return objects of the subclass's type. This avoids the new to re-write the modifying methods such as add(O) and remove(O) in every subclass.

Parameters:
length - the number of elements in the list
first - the first node in the list

add

public SList<O> add(O element)

Add an element to the static list in O(1) time.

The first element (index 0) is added first, which means that calling List.getLast() on the returned list will return elements[elements.length - 1].

Specified by:
add in class List<O>
Parameters:
element - the element to be added
Returns:
a clone of the list with element added to it

add

public SList<O> add(O[] elements)

Add x elements to the static list in O(x) time.

This method is only marginally more efficient than multiple calls to add(O) and is provided for convenience only.

Specified by:
add in class List<O>
Parameters:
elements - an array of elements to be added
Returns:
a clone of the list with all the elements added to it

add

public SList<O> add(List<O> otherList)

Add every element from otherList to the static list.

The first element added is the first element that was added to otherList, which means result.List.getLast()==otherList.List.getLast().

Specified by:
add in class List<O>
Parameters:
otherList - a list of elements to be added to this list
Returns:
a clone of the list with each element from otherList added to it

remove

public SList<O> remove(O element)

Remove the first instance of a given object from the static list in O(n) time. Objects are compared using ==.

Specified by:
remove in class List<O>
Parameters:
element - the object to remove
Returns:
a clone of the list which contains one less instance of element, or the same list if no instance of element was found

removeEquals

public SList<O> removeEquals(O element)

Remove the first instance of a given object from the static list in O(n) time. Objects are compared using Object.equals(java.lang.Object).

Specified by:
removeEquals in class List<O>
Parameters:
element - the object to remove
Returns:
a clone of the list which contains one less instance of element, or the same list if no instance of element was found

removeAll

public SList<O> removeAll(O element)

Remove every instance of a given object from the static list in O(n) time. Objects are compared using ==.

This method is more time efficient than multiple calls to remove(O).

Specified by:
removeAll in class List<O>
Parameters:
element - the object to remove every instance of
Returns:
a clone of the list which contains no instances of element, or the same list if no instances of element were found

removeAllEquals

public SList<O> removeAllEquals(O element)

Remove every instance of a given object from the list in O(n) time. Objects are compared using Object.equals(java.lang.Object).

This method is more time efficient than multiple calls to removeEquals(O).

Specified by:
removeAllEquals in class List<O>
Parameters:
element - the object to remove every instance of
Returns:
a clone of this list which contains no instances of element, or the same list if no instances of element were found

clone

public SList<O> clone()

Return a deep copy of the dynamic list.

The clone list can be modified without affecting the original.

Specified by:
clone in class List<O>