sdds
Class List<O>

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

public abstract class List<O>
extends java.lang.Object

A singly-linked list (the abstract superclass of DList and SList).

In general, the time for each operation is as follows:

Author:
Stephen G. Ware

Field Summary
protected  sdds.List.Node<O> last
          The last node in the list
protected  int length
          The number of elements in the list
 
Constructor Summary
protected List()
          Construct an empty list.
protected List(int length, sdds.List.Node<O> last)
          Construct a list with a given size and a given first node.
protected List(O[] elements)
          Construct a list which initially contains a given set of elements.
 
Method Summary
abstract  List<O> add(List<O> otherList)
          Add every element from otherList to the list.
abstract  List<O> add(O element)
          Add an element to the list in O(1) time.
abstract  List<O> add(O[] elements)
          Add x elements to the list in O(x) time.
abstract  List<O> clone()
          Return a new list which Object.equals(java.lang.Object) this list but is not == to this list.
 boolean contains(O element)
          Search the list to see if it contains a given object in O(n) time.
 boolean containsEquals(O element)
          Search the list to see if it contains a given object in O(n) time.
 boolean equals(java.lang.Object other)
          Check if this list is the same as another.
 O get(int index)
          Get an arbitrary element from the list in O(n) time.
 O getLast()
          Return the last element added to the list in O(1) time.
 java.util.Iterator<O> iterator()
          Return an Iterator that will yield each element in the list.
 int length()
          Return the number of elements in the list in O(1) time.
abstract  List<O> remove(O element)
          Remove the first instance of a given object from the list in O(n) time.
abstract  List<O> removeAll(O element)
          Remove every instance of a given object from the list in O(n) time.
abstract  List<O> removeAllEquals(O element)
          Remove every instance of a given object from the list in O(n) time.
abstract  List<O> removeEquals(O element)
          Remove the first instance of a given object from the list in O(n) time.
 O[] toArray(O[] array)
          Return an array containing all the elements in this list.
 java.lang.String toString()
          Return a string representation of this list and all its elements.
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

length

protected int length
The number of elements in the list


last

protected sdds.List.Node<O> last
The last node in the list

Constructor Detail

List

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

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

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

List

protected List()

Construct an empty list.


List

protected List(O[] elements)

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

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

length

public int length()

Return the number of elements in the list in O(1) time.

Returns:
the number of elements

add

public abstract List<O> add(O element)

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

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

Parameters:
element - the element to be added
Returns:
a list exactly like this one, but with element added to it

add

public abstract List<O> add(O[] elements)

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

Parameters:
elements - an array of elements to be added
Returns:
a list exactly like this one, but with all the elements added to it

add

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

Add every element from otherList to the list.

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

Parameters:
otherList - a list of elements to be added to this list
Returns:
a list exactly like this one, but with each element from otherList added to it

getLast

public O getLast()

Return the last element added to the list in O(1) time.

Returns:
the last element

get

public O get(int index)

Get an arbitrary element from the list in O(n) time.

get(list.length() - 1) is equivalent to getLast().

Parameters:
index - the number of the element to be returned
Returns:
the index'th element or null if index is greater than or equal to length.

contains

public boolean contains(O element)

Search the list to see if it contains a given object in O(n) time. Objects are compared using ==.

Parameters:
element - the object to search for
Returns:
true is the object is in this list, false otherwise

containsEquals

public boolean containsEquals(O element)

Search the list to see if it contains a given object in O(n) time. Objects are compared using Object.equals(java.lang.Object).

Parameters:
element - the object to search for
Returns:
true is the object is in this list, false otherwise

remove

public abstract List<O> remove(O element)

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

Parameters:
element - the object to remove
Returns:
a list exactly like this one, but which contains one less instance of element, or the same list if no instance of element was found

removeEquals

public abstract List<O> removeEquals(O element)

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

Parameters:
element - the object to remove
Returns:
a list exactly like this one, but which contains one less instance of element, or the same list if no instance of element was found

removeAll

public abstract List<O> removeAll(O element)

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

Parameters:
element - the object to remove every instance of
Returns:
a list exactly like this one, but which contains no instances of element, or the same list if no instances of element were found

removeAllEquals

public abstract List<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).

Parameters:
element - the object to remove every instance of
Returns:
a list exactly like this one, but which contains no instances of element, or the same list if no instances of element were found

iterator

public java.util.Iterator<O> iterator()

Return an Iterator that will yield each element in the list.

The first element yielded will be the last element added to the list; the last element yielded will be the first element added to the list.

Returns:
an iterator

toArray

public O[] toArray(O[] array)

Return an array containing all the elements in this list.

The first element in the array (index 0) will be the first element added to the list.

Parameters:
array - an array of type O of any length
Returns:
an array of all the elements in this list

equals

public boolean equals(java.lang.Object other)

Check if this list is the same as another.

Two lists are considered the same if they contain the same elements in the same order. Elements are compared using Object.equals(java.lang.Object).

The class of the list is not taken into account. In other words, a DList can be equal to an SList if they contain the same elements in the same order.

Overrides:
equals in class java.lang.Object
Parameters:
other - another list
Returns:
true is the lists are the same, false if the lists are different or if other is not a list

clone

public abstract List<O> clone()

Return a new list which Object.equals(java.lang.Object) this list but is not == to this list.

Overrides:
clone in class java.lang.Object

toString

public java.lang.String toString()

Return a string representation of this list and all its elements.

Overrides:
toString in class java.lang.Object