structure
Class CircularList

java.lang.Object
  |
  +--structure.AbstractStructure
        |
        +--structure.AbstractList
              |
              +--structure.CircularList

All Implemented Interfaces:

List, Structure

Direct Known Subclasses:

AppendableList

public class CircularList

extends AbstractList

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 SinglyLinkedListElement	tail A reference to tail of list.

Constructor Summary

CircularList()
Construct an empty circular list.

Method Summary

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

Methods inherited from class structure.AbstractList

get, remove

Methods inherited from class structure.AbstractStructure

elements, hashCode, values

Methods inherited from class java.lang.Object

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

Methods inherited from interface structure.Structure

elements, values

Field Detail

tail

protected SinglyLinkedListElement 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.

Method Detail

add

public void add(Object value)

Add an element to head of circular list.

Overrides:

add in class AbstractList

Parameters:

value - value to be added to list.

Postcondition:

adds value to beginning of list

addFirst

public void addFirst(Object value)

Add an element to head of list.

Overrides:

addFirst in class AbstractList

Parameters:

value - value added to head of list.

Precondition:

value non-null

Postcondition:

adds element to head of list

addLast

public void addLast(Object value)

Add a value to tail of circular list.

Overrides:

addLast in class AbstractList

Parameters:

value - value to be added.

Precondition:

value non-null

Postcondition:

adds element to tail of list

getFirst

public Object getFirst()

Determine if a list is empty.

Overrides:

getFirst in class AbstractList

Precondition:

!isEmpty()

Postcondition:

returns value at head of list

Returns:

True if there are no elements within list.

getLast

public Object getLast()

Peek at last element of list.

Overrides:

getLast in class AbstractList

Precondition:

!isEmpty()

Postcondition:

returns value at tail of list

Returns:

value of last element of list.

removeFirst

public Object removeFirst()

Remove a value from head of list.

Overrides:

removeFirst in class AbstractList

Precondition:

!isEmpty()

Postcondition:

returns and removes value from head of list

Returns:

value removed.

removeLast

public Object removeLast()

Remove a value from tail of list.

Overrides:

removeLast in class AbstractList

Precondition:

!isEmpty()

Postcondition:

returns and removes value from tail of list

Returns:

value removed.

contains

public boolean contains(Object value)

Check if a list contains an element.

Overrides:

contains in class AbstractList

Parameters:

value - value sought.

Precondition:

value != null

Postcondition:

returns true if list contains value, else false

Returns:

True iff value is within list.

remove

public Object remove(Object value)

Remove a value from a list.

Parameters:

value - value sought.

Precondition:

value != null

Postcondition:

removes and returns element equal to value, or null

Returns:

value removed from list.

size

public int size()

Determine size of list.

Postcondition:

returns number of elements in list

Returns:

number of elements in list.

get

public Object get(int i)

Get value at location i.

Parameters:

i - position of value to be retrieved.

Precondition:

0 <= i < size()

Postcondition:

returns object found at that location

Returns:

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

getTail

protected SinglyLinkedListElement getTail()

Accessor method for tail field

set

public Object set(int i,
                  Object o)

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

Parameters:

i - location of entry to be changed.

o - new value

Precondition:

0 <= i < size()

Postcondition:

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

Returns:

former value of ith entry of list.

add

public void add(int i,
                Object 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 Object remove(int i)

Remove and return value at location i.

Parameters:

i - position of value to be retrieved.

Precondition:

0 <= i < size()

Postcondition:

removes and returns object found at that location

Returns:

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

indexOf

public int indexOf(Object value)

Determine first location of a value in list.

Parameters:

value - value sought.

Precondition:

value is not null

Postcondition:

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

Returns:

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

lastIndexOf

public int lastIndexOf(Object value)

Determine last location of a value in list.

Parameters:

value - value sought.

Precondition:

value is not null

Postcondition:

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

Returns:

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

iterator

public Iterator iterator()

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

Postcondition:

returns iterator to traverse list elements

Returns:

iterator associated with list.

isEmpty

public boolean isEmpty()

Determine if a list is empty.

Overrides:

isEmpty in class AbstractList

Postcondition:

returns true if no elements in list

Returns:

True iff list is empty.

clear

public void clear()

Remove elements of list.

Postcondition:

removes all elements from list

toString

public String toString()

Generate a string representation of list.

Overrides:

toString in class Object

Postcondition:

returns a string representing list

Returns:

String representing list.