data_structures
Class DList<O>

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

public class DList<O>
extends List<O>

A dynamic singly-linked List.

Author:
Stephen G. Ware

Field Summary
 
Fields inherited from class data_structures.List
first, length
 
Constructor Summary
  DList()
          Construct an empty dynamic list.
protected DList(int length, data_structures.List.Node<O> first)
          Construct a dynamic list with a given size and a given first node.
  DList(O[] elements)
          Construct a dynamic list which initially contains a given set of elements.
 
Method Summary
 DList<O> add(List<O> otherList)
          Add every element from otherList to the dynamic list.
 DList<O> add(O element)
          Add an element to the dynamic list in O(1) time.
 DList<O> add(O[] elements)
          Add x elements to the dynamic list in O(x) time.
 DList<O> clone()
          Return a deep copy of the dynamic list.
 boolean contains(O element)
          Search the dynamic list to see if it contains a given object in O(n) time.
 boolean containsEquals(O element)
          Search the dynamic 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 dynamic list in O(n) time.
 O getLast()
          Return the last element added to the dynamic list in O(1) time.
 java.util.Iterator<O> iterator()
          Return an Iterator that will yield each element in the dynamic list.
 int length()
          Return the number of elements in the dynamic list in O(1) time.
 DList<O> remove(O element)
          Remove the first instance of a given object from the dynamic list in O(n) time.
 DList<O> removeAll(O element)
          Remove every instance of a given object from the dynamic list in O(n) time.
 DList<O> removeAllEquals(O element)
          Remove every instance of a given object from the dynamic list in O(n) time.
 DList<O> removeEquals(O element)
          Remove the first instance of a given object from the dynamic list in O(n) time.
 O[] toArray(O[] array)
          Return an array containing all the elements in the dynamic list.
 java.lang.String toString()
          Return a string representation of this dynamic list and all its elements.
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

DList

protected DList(int length,
                data_structures.List.Node<O> first)

Construct a dynamic 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

DList

public DList()

Construct an empty dynamic list.


DList

public DList(O[] elements)

Construct a dynamic 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 dynamic list in O(1) time.

Overrides:
length in class List<O>
Returns:
the number of elements

add

public DList<O> add(O element)

Add an element to the dynamic 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].

Specified by:
add in class List<O>
Parameters:
element - the element to be added
Returns:
this list

add

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

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

Specified by:
add in class List<O>
Parameters:
elements - an array of elements to be added
Returns:
this list

add

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

Add every element from otherList to the dynamic list.

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

Specified by:
add in class List<O>
Parameters:
otherList - a list of elements to be added to this list
Returns:
this list

getLast

public O getLast()

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

Overrides:
getLast in class List<O>
Returns:
the last element

get

public O get(int index)

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

get(0) is equivalent to getLast().

Overrides:
get in class List<O>
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 dynamic list to see if it contains a given object in O(n) time. Objects are compared using ==.

Overrides:
contains in class List<O>
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 dynamic list to see if it contains a given object in O(n) time. Objects are compared using Object.equals(java.lang.Object).

Overrides:
containsEquals in class List<O>
Parameters:
element - the object to search for
Returns:
true is the object is in this list, false otherwise

remove

public DList<O> remove(O element)

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

Specified by:
remove in class List<O>
Parameters:
element - the object to remove
Returns:
this list

removeEquals

public DList<O> removeEquals(O element)

Remove the first instance of a given object from the dynamic 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:
this list

removeAll

public DList<O> removeAll(O element)

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

Specified by:
removeAll in class List<O>
Parameters:
element - the object to remove every instance of
Returns:
this list

removeAllEquals

public DList<O> removeAllEquals(O element)

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

Specified by:
removeAllEquals in class List<O>
Parameters:
element - the object to remove every instance of
Returns:
this list

iterator

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

Return an Iterator that will yield each element in the dynamic 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.

Overrides:
iterator in class List<O>
Returns:
an iterator

toArray

public O[] toArray(O[] array)

Return an array containing all the elements in the dynamic list.

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

Overrides:
toArray in class List<O>
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 contains the same elements in the same order.

Overrides:
equals in class List<O>
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 DList<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>

toString

public java.lang.String toString()

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

Overrides:
toString in class List<O>