Class List<K,D>

java.lang.Object
  Dictionary<K,D>
      List<K,D>

Type Parameters:

K - The type of the keys

D - The type of the data

All Implemented Interfaces:

Map<K,D>

public class List<K,D>
extends Dictionary<K,D>

A List is a Map implemented as double-linked list. There are linear time insertion and lookup operations. Moreover, there are constant time operations to add an element in front of the list or at the end of the list. However, if these constant time operations are used, then the list is not a Map any more, e.g., there might be multiple data-entries for the same key.
Note, that null-values are not supported as keys.

Author:

Rossmanith

Constructor Summary

List()

Method Summary

void	append(K k, D d) Appends the value k -> d at the end of the list.
void	delete(K k) Deletes the (first) element of this list with given key k, if such an element exists.
D	find(K k) Looks up the data stored under the key k.
void	insert(K k, D d) Associates the data d to the key k in this map.
boolean	iselement(K k) Checks whether the key k is present in this map.
Listiterator<K,D>	iterator() Creates a new iterator over all associations between keys and data.
void	prepend(K k, D d) Appends the value k -> d at the beginning of the list.

Methods inherited from class Dictionary

array, isempty, print, simpleiterator, size

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

List

public List()

Method Detail

insert

public void insert(K k,
                   D d)

Description copied from interface: Map

Associates the data d to the key k in this map. A possible old entry for k will be deleted.

Specified by:

insert in interface Map<K,D>

Specified by:

insert in class Dictionary<K,D>

Parameters:

k - The key to store.

d - The data associated to the key k.

iselement

public boolean iselement(K k)

Checks whether the key k is present in this map. (linear time)

Specified by:

iselement in interface Map<K,D>

Overrides:

iselement in class Dictionary<K,D>

Parameters:

k - The key to look for.

Returns:

true, if k is contained in this map, and false, otherwise.

See Also:

Map.iselement(Object)

append

public void append(K k,
                   D d)

Appends the value k -> d at the end of the list. (constant time) Note that this operation can destroy uniqueness of the key-to-data mapping as required in Map.

Parameters:

k -

d -

prepend

public void prepend(K k,
                    D d)

Appends the value k -> d at the beginning of the list. (constant time) Note that this operation can destroy uniqueness of the key-to-data mapping as required in Map.

Parameters:

k -

d -

find

public D find(K k)

Looks up the data stored under the key k. (linear time)

Specified by:

find in interface Map<K,D>

Overrides:

find in class Dictionary<K,D>

Parameters:

k - The key under which the data is stored.

Returns:

The data, which is stored under the key k, or null, if there is no data associated to k.

See Also:

Map.find(Object)

delete

public void delete(K k)

Deletes the (first) element of this list with given key k, if such an element exists.

Specified by:

delete in interface Map<K,D>

Specified by:

delete in class Dictionary<K,D>

Parameters:

k - The key which should be deleted.

iterator

public Listiterator<K,D> iterator()

Description copied from interface: Map

Creates a new iterator over all associations between keys and data.

Specified by:

iterator in interface Map<K,D>

Specified by:

iterator in class Dictionary<K,D>

Returns:

The Iterator over all keys with associated data.