listClasses

Class BasicDoubleLinkedList<T>

java.lang.Object

listClasses.BasicDoubleLinkedList<T>

All Implemented Interfaces:

java.lang.Iterable<T>

Direct Known Subclasses:

SortedDoubleLinkedList

public class BasicDoubleLinkedList<T>
extends java.lang.Object
implements java.lang.Iterable<T>

This generic doubly-linked list relies on a head (reference to first element of the list) and tail (reference to the last element of the list). Both are set to null when the list is empty. Both point to the same element when there is only one element in the list. A node structure has only three fields: data, prev reference, and next reference. The class must only define the following entities: a class Node, head and tail references and an integer representing the list size. All the entities are defined as protected so they can be accessed by the subclass.

Author:

Dept of Computer Science, UMCP

Constructor Summary

Constructors

Constructor and Description
BasicDoubleLinkedList() Defines an empty linked list.

Method Summary

Modifier and Type	Method and Description
BasicDoubleLinkedList<T>	add(int index, T data) Adds element at the index position in the list.
BasicDoubleLinkedList<T>	addToEnd(T data) Adds element to the end of the list.
BasicDoubleLinkedList<T>	addToFront(T data) Adds element to the front of the list.
T	get(int index) Returns but does not remove the element at the index position in the list.
T	getFirst() Returns but does not remove the first element from the list.
T	getLast() Returns but does not remove the last element from the list.
int	getSize() Notice you must not traverse the list to compute the size.
java.util.Iterator<T>	iterator() This method must be implemented using an anonymous inner class that defines the iterator.
BasicDoubleLinkedList<T>	remove(T targetData, java.util.Comparator<T> comparator) Removes ALL instances of targetData from the list.
T	retrieve(int index) Removes and returns the element at the index position from the list (zero indexed).
T	retrieveFirstElement() Removes and returns the first element from the list.
T	retrieveLastElement() Removes and returns the last element from the list.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

BasicDoubleLinkedList

public BasicDoubleLinkedList()

Defines an empty linked list. No nodes are created. We do not use dummy nodes for this list (if you don't know what a dummy list is don't worry about it).

Method Detail

getSize

public int getSize()

Notice you must not traverse the list to compute the size. This method just returns the value of the instance variable you use to keep track of size.

Returns:

list size

addToEnd

public BasicDoubleLinkedList<T> addToEnd(T data)

Adds element to the end of the list. Do not use iterators to implement this method. Take care of the double references.

Parameters:

data -

Returns:

reference to current object

addToFront

public BasicDoubleLinkedList<T> addToFront(T data)

Adds element to the front of the list. Do not use iterators to implement this method. Take care of the double references.

Parameters:

data -

Returns:

reference to current object

add

public BasicDoubleLinkedList<T> add(int index,
                                    T data)

Adds element at the index position in the list. Do not use iterators to implement this method. Zero indexing is to be used. Take care of the double references.

Parameters:

data -

Returns:

reference to current object

getFirst

public T getFirst()

Returns but does not remove the first element from the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

data element or null

getLast

public T getLast()

Returns but does not remove the last element from the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

data element or null

get

public T get(int index)

Returns but does not remove the element at the index position in the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

data element or null

retrieveFirstElement

public T retrieveFirstElement()

Removes and returns the first element from the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

data element or null

retrieveLastElement

public T retrieveLastElement()

Removes and returns the last element from the list. If there are no elements the method returns null. Do not implement implement this method using iterators.

Returns:

data element or null

retrieve

public T retrieve(int index)

Removes and returns the element at the index position from the list (zero indexed). If there are no elements the method returns null. Do not implement implement this method using iterators.

Returns:

data element or null

remove

public BasicDoubleLinkedList<T> remove(T targetData,
                                       java.util.Comparator<T> comparator)

Removes ALL instances of targetData from the list. Notice that you must remove the elements by performing a single traversal over the list. You may not use any of the other retrieval methods associated with the class in order to complete the removal process. You must use the provided comparator (do not use equals) to find those elements that match the target. Do not implement this method using iterators. Take care of the double references per node, i.e. the prev and next.

Parameters:

targetData -

comparator -

Returns:

reference to current object

iterator

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

This method must be implemented using an anonymous inner class that defines the iterator. Remember that we should be able to call the hasNext() method as many times as we want without changing what is considered the next element. Only students in the honor section will implement the iterator's remove() method. If you don't need to implement the iterator's remove() method, throw UnsupportedOperationException.

Specified by:

iterator in interface java.lang.Iterable<T>

Returns:

iterator