data_structures
Class SList<O>

java.lang.Object
  extended by data_structures.List<O>
      extended by data_structures.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 data_structures.List
first, length
 
Constructor Summary
  SList()
          Construct an empty static list.
protected SList(int length, data_structures.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, data_structures.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 data_structures.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,
                data_structures.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,
                            data_structures.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>