|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectdata_structures.List<O>
O
- the type of object the list will holdpublic abstract class List<O>
A singly-linked list. This is the abstract superclass of DList
and SList
.
In general, the time for each operation is as follows:
Field Summary | |
---|---|
protected data_structures.List.Node<O> |
first
The first 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,
data_structures.List.Node<O> first)
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 |
---|
protected int length
protected data_structures.List.Node<O> first
Constructor Detail |
---|
protected List(int length, data_structures.List.Node<O> first)
Construct a list with a given size and a given first node.
length
- the number of elements in the listfirst
- the first node in the listprotected List()
Construct an empty list.
protected List(O[] elements)
Construct a list which initially contains a given set of elements.
elements
- the elements the list will initially containMethod Detail |
---|
public int length()
Return the number of elements in the list in O(1) time.
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]
.
element
- the element to be added
public abstract List<O> add(O[] elements)
Add x elements to the list in O(x) time.
elements
- an array of elements to be added
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()
otherList
- a list of elements to be added to this list
public O getLast()
Return the last element added to the list in O(1) time.
public O get(int index)
Get an arbitrary element from the list in O(n) time.
get(list.length() - 1)
is equivalent to getLast()
.
index
- the number of the element to be returned
length
.public boolean contains(O element)
Search the list to see if it contains a given object in O(n) time. Objects are compared using ==
.
element
- the object to search for
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)
.
element
- the object to search for
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 ==
.
element
- the object to remove
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)
.
element
- the object to remove
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 ==
.
element
- the object to remove every instance of
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)
.
element
- the object to remove every instance of
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.
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.
array
- an array of type O of any length
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.
equals
in class java.lang.Object
other
- another list
public abstract List<O> clone()
Return a new list which Object.equals(java.lang.Object)
this list but is not ==
to this list.
clone
in class java.lang.Object
public java.lang.String toString()
Return a string representation of this list and all its elements.
toString
in class java.lang.Object
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |