com.scottlogic.util
Class UnsortedList<T>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractList<T>
          com.scottlogic.util.SortedList<T>
              com.scottlogic.util.UnsortedList<T>

Type Parameters:

T - the type of element that this sorted list will store.

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<T>, java.util.Collection<T>, java.util.List<T>

public class UnsortedList<T>
extends SortedList<T>

Implementation of a regular list that uses an AVL tree. Supports all optional operations.

Performs the operations: #add(int, Object), get and #remove(int) operations in in time O(log(n)) and the #contains(Object) and remove(Object) operations in time O(n), where n is the number of elements in the list.

This implementation is not synchronised so if you need multi-threaded access then consider wrapping it using the Collections.synchronizedList(java.util.List) method.

The iterators this list provides are fail-fast, so any structural modification, other than through the iterator itself, cause it to throw a ConcurrentModificationException.

Version:

1.0

Author:

Mark Rhodes

See Also:

Collection, AbstractList, Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class com.scottlogic.util.SortedList

SortedList.Node

Field Summary

Fields inherited from class java.util.AbstractList

modCount

Constructor Summary

UnsortedList()
Constructs a new UnsortedList.

Method Summary

void	add(int index, T element) Inserts the specified element at the specified position in this list.
boolean	add(T object) Adds the given object to the end of this UnsortedList, which can be null.
void	addToHead(T element) Adds the given element to the head of this list.
boolean	contains(java.lang.Object obj) Returns whether or not the given object whether or not the given object is present in this UnsortedList.
boolean	remove(java.lang.Object value) Removes the first element in the list with the given value, if such a node exists, otherwise does nothing.
T	set(int index, T element) Replaces the element at the specified position in this list with the specified element.

Methods inherited from class com.scottlogic.util.SortedList

add, clear, findNodeAtIndex, get, getRoot, isEmpty, iterator, remove, size, toArray, toArray

Methods inherited from class java.util.AbstractList

addAll, equals, hashCode, indexOf, lastIndexOf, listIterator, listIterator, removeRange, subList

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, removeAll, retainAll, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.List

addAll, containsAll, removeAll, retainAll

Constructor Detail

UnsortedList

public UnsortedList()

Constructs a new UnsortedList.

Method Detail

set

public T set(int index,
             T element)

Replaces the element at the specified position in this list with the specified element.

Specified by:

set in interface java.util.List<T>

Overrides:

set in class java.util.AbstractList<T>

Parameters:

index - the index in this UnsortedList to add this given element.

element - the object to add to this UnsortedList.

Returns:

the element that was replaced at the given index.

Throws:

java.lang.IllegalArgumentException - in the case that the element is null.

java.lang.IndexOutOfBoundsException - in the case that (0 <= index < size()) does not hold.

contains

public boolean contains(java.lang.Object obj)

Returns whether or not the given object whether or not the given object is present in this UnsortedList.

This implementation takes O(n) time, where n is the number of element in this list.

Specified by:

contains in interface java.util.Collection<T>

Specified by:

contains in interface java.util.List<T>

Overrides:

contains in class SortedList<T>

Parameters:

obj - the object to check for.

Returns:

true if the given object is present in this UnsortedList and false otherwise.

remove

public boolean remove(java.lang.Object value)

Removes the first element in the list with the given value, if such a node exists, otherwise does nothing. Works in time O(n), where i is the number of elements in this UnsortedList.

Returns whether or not a matching element was found and removed or not.

Specified by:

remove in interface java.util.Collection<T>

Specified by:

remove in interface java.util.List<T>

Overrides:

remove in class SortedList<T>

Parameters:

value - the object to remove from this SortedList.

Returns:

true if the given object was found in this SortedList and removed, false otherwise.

add

public void add(int index,
                T element)

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Works in time O(log(n)), where n is the number of elements in the list.

Specified by:

add in interface java.util.List<T>

Overrides:

add in class java.util.AbstractList<T>

Parameters:

index - at which the element should be added.

element - the object to by inserted.

Throws:

java.lang.IllegalArgumentException - in the case that the given element is null.

java.lang.IndexOutOfBoundsException - in the case that (0 <= index <= size()) does not hold.

addToHead

public void addToHead(T element)

Adds the given element to the head of this list. Shifts the elements currently in the list (if any) to the right (adds one to their indices).

Works in time O(log(n)), where n is the number of elements in the list.

Parameters:

element - the object to by inserted.

Throws:

java.lang.IllegalArgumentException - in the case that the given element is null.

add

public boolean add(T object)

Adds the given object to the end of this UnsortedList, which can be null.

Specified by:

add in interface java.util.Collection<T>

Specified by:

add in interface java.util.List<T>

Overrides:

add in class SortedList<T>

Parameters:

object - the object to add.

Returns:

true.