inf.util
Class HashedList<E>

java.lang.Object
  inf.util.HashedList<E>

Type Parameters:

E - the element type for elements in the List

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.List<E>

public class HashedList<E>
extends java.lang.Object
implements java.lang.Cloneable, java.util.List<E>, java.lang.Iterable<E>

This class is a linked list implementation of the List interface. It implements only those list operations that can be performed efficiently, which means index-based access to the list is not supported.

The most important difference to a java.util.LinkedList, on which class this implementation is based, is that in addition to the internal representation as a doubly linked list, a hash map is maintained that maps the elements in the list to the entries in the list containing them. This makes efficient removal from the list possible, but it also comes at a cost: some other operations become slightly more expensive and the required memory roughly doubles. Furthermore, the list cannot contain two or more equal elements or null as these are used as keys in the hash map.

In addition to implementing the List interface, the HashedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque).

Author:

Gerhard Wickler, based on the LinkedList implementation by Josh Bloch

Constructor Summary

HashedList()
This constructor creates an empty hashed list.

HashedList(java.util.Collection<? extends E> elements)
This constructor creates a hashed list containing all the elements from the given Collection in the order returned by the Collection's iterator.

HashedList(E... elements)
This constructor creates a hashed list containing the given elements in the given order.

Method Summary

boolean	add(E elt) This function appends the specified element to the end of this list.
void	add(int index, E element) This class does not support index-based access to the list and an exception will be thrown if this method is called.
boolean	addAll(java.util.Collection<? extends E> elements) This function adds all the elements from the given Collection to this list.
boolean	addAll(int index, java.util.Collection<? extends E> c) This class does not support index-based access to the list and an exception will be thrown if this method is called.
void	addFirst(E elt) This function inserts the given element at the beginning of this list.
void	addLast(E elt) This function appends the given element to the end of this list.
void	clear() This function removes all of the elements from this Collection.
HashedList<E>	clone() This function returns a shallow copy of this HashedList.
boolean	contains(java.lang.Object elt) This function returns true if this Collection contains the specified element which must not be null.
boolean	containsAll(java.util.Collection<?> elements) This function returns true if this Collection contains all the specified elements in the given Collection which must not be null.
boolean	equals(java.util.List<E> list) This function tests whether the this and the given List are equal.
boolean	equals(java.lang.Object o) This function tests whether this and the given Object are equal.
E	get(int index) This class does not support index-based access to the list and an exception will be thrown if this method is called.
E	getFirst() This function returns the first element in this list.
E	getLast() This function returns the last element in this list.
int	hashCode() This function computes a hash value for this HashedList.
int	indexOf(java.lang.Object o) This class does not support index-based access to the list and an exception will be thrown if this method is called.
boolean	isEmpty() This function tests whether this Collection contains no elements.
java.util.Iterator<E>	iterator() This function returns an iterator over the elements in this list in proper sequence.
int	lastIndexOf(java.lang.Object o) This class does not support index-based access to the list and an exception will be thrown if this method is called.
java.util.ListIterator<E>	listIterator() This function returns a list-iterator of the elements in this list (in proper sequence).
java.util.ListIterator<E>	listIterator(int index) This class does not support index-based access to the list and an exception will be thrown if this method is called.
E	remove(int index) This class does not support index-based access to the list and an exception will be thrown if this method is called.
boolean	remove(java.lang.Object elt) This function removes the occurrence of the specified element in this list.
boolean	removeAll(java.util.Collection<?> elements) This function removes the occurrence of all the specified elements in this list.
E	removeFirst() This function removes and returns the first element from this list.
E	removeLast() This function removes and returns the last element from this list.
boolean	retainAll(java.util.Collection<?> elements) This function removes the occurrence of all the elements in this list that are not in the given Collection.
E	set(int index, E element) This class does not support index-based access to the list and an exception will be thrown if this method is called.
int	size() This function returns the number of elements in this Collection.
java.util.List<E>	subList(int fromIndex, int toIndex) This class does not support index-based access to the list and an exception will be thrown if this method is called.
java.lang.Object[]	toArray() This function returns an array containing all of the elements in this list in the correct order.
<T> T[]	toArray(T[] a) This function fills a given Array with all of the elements in this list in the correct order.
java.lang.String	toString() This function returns a printable representation of this HashedList.

Methods inherited from class java.lang.Object

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

Constructor Detail

HashedList

public HashedList()

This constructor creates an empty hashed list.

HashedList

public HashedList(java.util.Collection<? extends E> elements)

This constructor creates a hashed list containing all the elements from the given Collection in the order returned by the Collection's iterator.

Parameters:

elements - the initial elements for this list

HashedList

public HashedList(E... elements)

This constructor creates a hashed list containing the given elements in the given order.

Parameters:

elements - the initial elements for this list

Method Detail

clone

public HashedList<E> clone()

This function returns a shallow copy of this HashedList. The elements themselves are not cloned.

Overrides:

clone in class java.lang.Object

Returns:

a shallow copy of this HashedList instance

add

public boolean add(E elt)

This function appends the specified element to the end of this list. Note that this element must not be in the list already or null. Use addLast(...) for more readable code.

Specified by:

add in interface java.util.Collection<E>

Specified by:

add in interface java.util.List<E>

Parameters:

elt - element to be appended to this list

Returns:

true (as per the general contract of Collection.add(...))

addAll

public boolean addAll(java.util.Collection<? extends E> elements)

This function adds all the elements from the given Collection to this list. The new elements will be appended to the end of this list in the order returned by the given Collection's iterator. Note that none of the given elements must already be in the list or null.

Specified by:

addAll in interface java.util.Collection<E>

Specified by:

addAll in interface java.util.List<E>

Parameters:

elements - the Collection of new elements to be appended

Returns:

true (as per the general contract of Collection.addAll(...))

isEmpty

public boolean isEmpty()

This function tests whether this Collection contains no elements. If this is true, the size of the Collection is 0.

Specified by:

isEmpty in interface java.util.Collection<E>

Specified by:

isEmpty in interface java.util.List<E>

Returns:

true iff this list contains no elements

size

public int size()

This function returns the number of elements in this Collection. The result is a positive integer.

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in interface java.util.List<E>

Returns:

the length of this List

contains

public boolean contains(java.lang.Object elt)

This function returns true if this Collection contains the specified element which must not be null. The test is performed by looking up the element in the hash table and should thus be efficient.

Specified by:

contains in interface java.util.Collection<E>

Specified by:

contains in interface java.util.List<E>

Parameters:

elt - element whose presence in this list is to be tested

Returns:

true if this list contains the specified element

containsAll

public boolean containsAll(java.util.Collection<?> elements)

This function returns true if this Collection contains all the specified elements in the given Collection which must not be null. The test is performed by looking up the elements in the hash table and should thus be relatively efficient.

Specified by:

containsAll in interface java.util.Collection<E>

Specified by:

containsAll in interface java.util.List<E>

Parameters:

elements - the elements whose presence in this list is to be tested

Returns:

true if this list contains all the specified elements

toArray

public java.lang.Object[] toArray()

This function returns an array containing all of the elements in this list in the correct order.

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.List<E>

Returns:

an array containing all of the elements in this list in the correct order

toArray

public <T> T[] toArray(T[] a)

This function fills a given Array with all of the elements in this list in the correct order. If the given Array is too small a new Array of sufficient size is created. If the given Array is oversized a null element indicates the end of the list.

Specified by:

toArray in interface java.util.Collection<E>

Specified by:

toArray in interface java.util.List<E>

Parameters:

a - the Array to be filled

Returns:

T[] a possibly new array containing all of the elements in this list in the correct order

clear

public void clear()

This function removes all of the elements from this Collection.

Specified by:

clear in interface java.util.Collection<E>

Specified by:

clear in interface java.util.List<E>

remove

public boolean remove(java.lang.Object elt)

This function removes the occurrence of the specified element in this list. If the list does not contain the element, it is unchanged.

Specified by:

remove in interface java.util.Collection<E>

Specified by:

remove in interface java.util.List<E>

Parameters:

elt - element to be removed from this list, if present

Returns:

true if the list contained the specified element

removeAll

public boolean removeAll(java.util.Collection<?> elements)

This function removes the occurrence of all the specified elements in this list. If the list does not contain any of the elements, it is unchanged.

Specified by:

removeAll in interface java.util.Collection<E>

Specified by:

removeAll in interface java.util.List<E>

Parameters:

elements - the elements to be removed from this list, if present

Returns:

true if the list was modified as a result

retainAll

public boolean retainAll(java.util.Collection<?> elements)

This function removes the occurrence of all the elements in this list that are not in the given Collection. If the list contain all the elements, it is unchanged.

Specified by:

retainAll in interface java.util.Collection<E>

Specified by:

retainAll in interface java.util.List<E>

Parameters:

elements - the elements to be retained this list, if present

Returns:

true if the list was modified as a result

add

public void add(int index,
                E element)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

add in interface java.util.List<E>

Parameters:

index - index at which the specified element is to be inserted

element - element to be inserted

Throws:

java.lang.UnsupportedOperationException - unconditionally

addAll

public boolean addAll(int index,
                      java.util.Collection<? extends E> c)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

addAll in interface java.util.List<E>

Parameters:

index - index at which the specified element is to be inserted

c - elements to be inserted into this list

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

set

public E set(int index,
             E element)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

set in interface java.util.List<E>

Parameters:

index - index of element to return

element - element to be stored at the specified position

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

indexOf

public int indexOf(java.lang.Object o)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

indexOf in interface java.util.List<E>

Parameters:

o - element to search for

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

lastIndexOf

public int lastIndexOf(java.lang.Object o)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

lastIndexOf in interface java.util.List<E>

Parameters:

o - element to search for

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

get

public E get(int index)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

get in interface java.util.List<E>

Parameters:

index - index of element to return

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

listIterator

public java.util.ListIterator<E> listIterator()

This function returns a list-iterator of the elements in this list (in proper sequence). It obeys the general contract of List.listIterator(int).

The list-iterator is fail-fast: if the list is structurally modified at any time after the Iterator is created, in any way except through the list-iterator's own remove or add methods, the list-iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behaviour at an undetermined time in the future.

Specified by:

listIterator in interface java.util.List<E>

Returns:

a ListIterator of the elements in this list (in proper sequence), starting at the specified position in the list

See Also:

List.listIterator()

listIterator

public java.util.ListIterator<E> listIterator(int index)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

listIterator in interface java.util.List<E>

Parameters:

index - index of first element to be returned from the list iterator (by a call to the next method)

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

subList

public java.util.List<E> subList(int fromIndex,
                                 int toIndex)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

subList in interface java.util.List<E>

Parameters:

fromIndex - low endpoint (inclusive) of the subList

toIndex - high endpoint (exclusive) of the subList

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

remove

public E remove(int index)

This class does not support index-based access to the list and an exception will be thrown if this method is called.

Specified by:

remove in interface java.util.List<E>

Parameters:

index - the index of the element to removed

Returns:

nothing

Throws:

java.lang.UnsupportedOperationException - unconditionally

iterator

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

This function returns an iterator over the elements in this list in proper sequence. Actually, it returns a ListIterator.

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in interface java.util.List<E>

Returns:

Iterator an iterator over the elements in this list in proper sequence

addFirst

public void addFirst(E elt)

This function inserts the given element at the beginning of this list.

Parameters:

elt - the element to be inserted at the beginning of this list

addLast

public void addLast(E elt)

This function appends the given element to the end of this list. (It is identical in function to the add(...) method; included only for consistency.)

Parameters:

elt - the element to be inserted at the end of this list

getFirst

public E getFirst()

This function returns the first element in this list.

Returns:

the first element in this list

Throws:

java.util.NoSuchElementException - if this list is empty

getLast

public E getLast()

This function returns the last element in this list.

Returns:

the last element in this list

Throws:

java.util.NoSuchElementException - if this list is empty

removeFirst

public E removeFirst()

This function removes and returns the first element from this list.

Returns:

the first element from this list

Throws:

java.util.NoSuchElementException - if this list is empty

removeLast

public E removeLast()

This function removes and returns the last element from this list.

Returns:

the last element from this list

Throws:

java.util.NoSuchElementException - if this list is empty

equals

public boolean equals(java.lang.Object o)

This function tests whether this and the given Object are equal. If the given Object is a List, equality means equal elements in equal order. If it is a Collection the order is not taken into account. Otherwise they are not equal.

Specified by:

equals in interface java.util.Collection<E>

Specified by:

equals in interface java.util.List<E>

Overrides:

equals in class java.lang.Object

Parameters:

o - the Object this HashedList is compared to

Returns:

boolean whether they contain equal elements

equals

public boolean equals(java.util.List<E> list)

This function tests whether the this and the given List are equal. Here, equality means equal elements in equal order.

Parameters:

list - the List this one is compared to

Returns:

boolean whether they contain equal elements in the same order

hashCode

public int hashCode()

This function computes a hash value for this HashedList. Note that this function is relatively expensive to compute (linear in the size of the List) and thus, hashing may not be very efficient.

Specified by:

hashCode in interface java.util.Collection<E>

Specified by:

hashCode in interface java.util.List<E>

Overrides:

hashCode in class java.lang.Object

Returns:

a hash value for this HashedList

toString

public java.lang.String toString()

This function returns a printable representation of this HashedList. It is printed as a Lisp-style list.

Overrides:

toString in class java.lang.Object

Returns:

a String representation of this HashedList.