structure5
Class CircularList<E>

java.lang.Object
  structure5.AbstractStructure<E>
      structure5.AbstractList<E>
          structure5.CircularList<E>

All Implemented Interfaces:

java.lang.Iterable<E>, List<E>, Structure<E>

public class CircularList<E>
extends AbstractList<E>

An implementation of lists using circularly linked elements, similar to that of java.util.LinkedList.

This class is an implementation of the List interface. Operations accessing or modifying either the head or the tail of the list execute in constant time. Circular lists are as space-efficient as singly linked lists, but tail-related operations are less costly.

Example usage: To place a copy of every unique parameter passed to a program into a CircularList, we would use the following:

 public static void main(String[] arguments)
 {
     CircularList argList = new CircularList();
     for (int i = 0; i < arguments.length; i++){
         if (!argList.contains(arguments[i])){
             argList.add(arguments[i]);
         }
    }
    System.out.println(argList);
 }
 

See Also:

SinglyLinkedList, DoublyLinkedList

Field Summary

protected int	count Number of elements within circular list.
protected Node<E>	tail A reference to tail of list.

Constructor Summary

CircularList()
Construct an empty circular list.

Method Summary

void	add(E value) Add an element to head of circular list.
void	add(int i, E o) Insert value at location.
void	addFirst(E value) Add an element to head of list.
void	addLast(E value) Add a value to tail of circular list.
void	clear() Remove elements of list.
boolean	contains(E value) Check if a list contains an element.
E	get(int i) Get value at location i.
E	getFirst() Determine if a list is empty.
E	getLast() Peek at last element of list.
protected Node<E>	getTail() Accessor method for tail field
int	indexOf(E value) Determine first location of a value in list.
boolean	isEmpty() Determine if a list is empty.
java.util.Iterator<E>	iterator() Construct an iterator over elements of list.
int	lastIndexOf(E value) Determine last location of a value in list.
E	remove(E value) Remove a value from a list.
E	remove(int i) Remove and return value at location i.
E	removeFirst() Remove a value from head of list.
E	removeLast() Remove a value from tail of list.
E	set(int i, E o) Set value stored at location i to object o, returning old value.
int	size() Determine size of list.
java.lang.String	toString() Generate a string representation of list.

Methods inherited from class structure5.AbstractList

get, remove

Methods inherited from class structure5.AbstractStructure

elements, hashCode, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface structure5.Structure

elements, values

Field Detail

tail

protected Node<E> tail

A reference to tail of list. tail points to head.

count

protected int count

Number of elements within circular list.

Constructor Detail

CircularList

public CircularList()

Construct an empty circular list.

Precondition:

constructs a new circular list

Method Detail

add

public void add(E value)

Add an element to head of circular list.

Specified by:

add in interface List<E>

Specified by:

add in interface Structure<E>

Overrides:

add in class AbstractList<E>

Parameters:

value - value to be added to list.

See Also:

AbstractList.addLast(E)

Postcondition:

adds value to beginning of list

addFirst

public void addFirst(E value)

Add an element to head of list.

Specified by:

addFirst in interface List<E>

Overrides:

addFirst in class AbstractList<E>

Parameters:

value - value added to head of list.

Precondition:

value non-null

Postcondition:

adds element to head of list

addLast

public void addLast(E value)

Add a value to tail of circular list.

Specified by:

addLast in interface List<E>

Overrides:

addLast in class AbstractList<E>

Parameters:

value - value to be added.

Precondition:

value non-null

Postcondition:

adds element to tail of list

getFirst

public E getFirst()

Determine if a list is empty.

Specified by:

getFirst in interface List<E>

Overrides:

getFirst in class AbstractList<E>

Returns:

True if there are no elements within list.

Precondition:

!isEmpty()

Postcondition:

returns value at head of list

getLast

public E getLast()

Peek at last element of list.

Specified by:

getLast in interface List<E>

Overrides:

getLast in class AbstractList<E>

Returns:

value of last element of list.

Precondition:

!isEmpty()

Postcondition:

returns value at tail of list

removeFirst

public E removeFirst()

Remove a value from head of list.

Specified by:

removeFirst in interface List<E>

Overrides:

removeFirst in class AbstractList<E>

Returns:

value removed.

Precondition:

!isEmpty()

Postcondition:

returns and removes value from head of list

removeLast

public E removeLast()

Remove a value from tail of list.

Specified by:

removeLast in interface List<E>

Overrides:

removeLast in class AbstractList<E>

Returns:

value removed.

Precondition:

!isEmpty()

Postcondition:

returns and removes value from tail of list

contains

public boolean contains(E value)

Check if a list contains an element.

Specified by:

contains in interface List<E>

Specified by:

contains in interface Structure<E>

Overrides:

contains in class AbstractList<E>

Parameters:

value - value sought.

Returns:

True iff value is within list.

Precondition:

value != null

Postcondition:

returns true if list contains value, else false

remove

public E remove(E value)

Remove a value from a list.

Parameters:

value - value sought.

Returns:

value removed from list.

Precondition:

value != null

Postcondition:

removes and returns element equal to value, or null

size

public int size()

Determine size of list.

Returns:

number of elements in list.

Postcondition:

returns number of elements in list

get

public E get(int i)

Get value at location i.

Parameters:

i - position of value to be retrieved.

Returns:

value retrieved from location i (returns null if i invalid)

Precondition:

0 <= i < size()

Postcondition:

returns object found at that location

getTail

protected Node<E> getTail()

Accessor method for tail field

set

public E set(int i,
             E o)

Set value stored at location i to object o, returning old value.

Parameters:

i - location of entry to be changed.

o - new value

Returns:

former value of ith entry of list.

Precondition:

0 <= i < size()

Postcondition:

sets ith entry of list to value o, returns old value

add

public void add(int i,
                E o)

Insert value at location.

Parameters:

i - index of this new value

o - value to be stored

Precondition:

0 <= i <= size()

Postcondition:

adds ith entry of list to value o

remove

public E remove(int i)

Remove and return value at location i.

Parameters:

i - position of value to be retrieved.

Returns:

value retrieved from location i (returns null if i invalid)

Precondition:

0 <= i < size()

Postcondition:

removes and returns object found at that location

indexOf

public int indexOf(E value)

Determine first location of a value in list.

Parameters:

value - value sought.

Returns:

index (0 is first element) of value, or -1

Precondition:

value is not null

Postcondition:

returns (0-origin) index of value, or -1 if value is not found

lastIndexOf

public int lastIndexOf(E value)

Determine last location of a value in list.

Parameters:

value - value sought.

Returns:

index (0 is first element) of value, or -1

Precondition:

value is not null

Postcondition:

returns (0-origin) index of value, or -1 if value is not found

iterator

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

Construct an iterator over elements of list. Elements are traversed from head to tail.

Returns:

iterator associated with list.

See Also:

AbstractIterator, Iterator, Enumeration, Structure.elements()

Postcondition:

returns iterator to traverse list elements

isEmpty

public boolean isEmpty()

Determine if a list is empty.

Specified by:

isEmpty in interface List<E>

Specified by:

isEmpty in interface Structure<E>

Overrides:

isEmpty in class AbstractList<E>

Returns:

True iff list is empty.

Postcondition:

returns true if no elements in list

clear

public void clear()

Remove elements of list.

Postcondition:

removes all elements from list

toString

public java.lang.String toString()

Generate a string representation of list.

Overrides:

toString in class java.lang.Object

Returns:

String representing list.

Postcondition:

returns a string representing list