structure
Class SinglyLinkedList

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

All Implemented Interfaces:

List, Structure

public class SinglyLinkedList

extends AbstractList

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

This class is a basic implementation of the List interface. Operations accessing or modifying the head of the list execute in constant time. Operations accessing or modifying the tail of the list execute in a time proportional to the length of the list. Singly linked lists are space-efficient, but tail-related operations may be more costly than with doubly linked lists.

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

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

See Also:

DoublyLinkedList, CircularList

Field Summary

protected int	count The number of elements in list.
protected SinglyLinkedListElement	head The head of the list.

Constructor Summary

SinglyLinkedList()
Construct an empty list.

Method Summary

void	add(int i, Object o) Insert value at location.
void	add(Object value) Add an object to tail of list.
void	addFirst(Object value) Add a value to head of list.
void	addLast(Object value) Add a value to tail of list.
void	clear() Remove all values from list.
boolean	contains(Object value) Check to see if a value is in list.
Object	get(int i) Get value at location i.
Object	getFirst() Fetch first element of list.
Object	getLast() Fetch last element of list.
int	indexOf(Object value) Determine first location of a value in list.
Iterator	iterator() Returns an iterator traversing list from head to tail.
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 list.
Object	removeFirst() Remove a value from first element of list.
Object	removeLast() Remove last value from list.
Object	set(int i, Object o) Set value stored at location i to object o, returning old value.
int	size() Determine number of elements in list.
String	toString() Construct a string representing list.

Methods inherited from class structure.AbstractList

get, isEmpty, 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

count

protected int count

The number of elements in list.

head

protected SinglyLinkedListElement head

The head of the list. A reference to a singly linked list element.

Constructor Detail

SinglyLinkedList

public SinglyLinkedList()

Construct an empty list.

Method Detail

add

public void add(Object value)

Add an object to tail of list.

Overrides:

add in class AbstractList

Parameters:

value - The value to be added to tail of list.

Postcondition:

value is added to end of list (see addLast)

addFirst

public void addFirst(Object value)

Add a value to head of list.

Overrides:

addFirst in class AbstractList

Parameters:

value - The value to be added to head of list.

Postcondition:

value is added to beginning of list

removeFirst

public Object removeFirst()

Remove a value from first element of list.

Overrides:

removeFirst in class AbstractList

Precondition:

list is not empty

Postcondition:

removes and returns value from beginning of list

Returns:

The value actually removed.

addLast

public void addLast(Object value)

Add a value to tail of list.

Overrides:

addLast in class AbstractList

Parameters:

value - The value to be added to tail of list.

Postcondition:

adds value to end of list

removeLast

public Object removeLast()

Remove last value from list.

Overrides:

removeLast in class AbstractList

Precondition:

list is not empty

Postcondition:

removes last value from list

Returns:

The value actually removed.

getFirst

public Object getFirst()

Fetch first element of list.

Overrides:

getFirst in class AbstractList

Precondition:

list is not empty

Postcondition:

returns first value in list

Returns:

A reference to first element of list.

getLast

public Object getLast()

Fetch last element of list.

Overrides:

getLast in class AbstractList

Precondition:

list is not empty

Postcondition:

returns last value in list

Returns:

A reference to last element of list.

contains

public boolean contains(Object value)

Check to see if a value is in list.

Overrides:

contains in class AbstractList

Parameters:

value - The value sought.

Precondition:

value is not null

Postcondition:

returns true iff value is found in list

Returns:

True if value is within list.

remove

public Object remove(Object value)

Remove a value from list. At most one value will be removed.

Parameters:

value - The value to be removed.

Precondition:

value is not null

Postcondition:

removes first element with matching value, if any

Returns:

The actual value removed.

size

public int size()

Determine number of elements in list.

Postcondition:

returns number of elements in list

Returns:

The number of elements in list.

clear

public void clear()

Remove all values from list.

Postcondition:

removes all elements from 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)

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 the (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 the (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()

Returns an iterator traversing list from head to tail.

Postcondition:

returns enumeration allowing traversal of list

Returns:

An iterator to traverse list.

toString

public String toString()

Construct a string representing list.

Overrides:

toString in class Object

Postcondition:

returns a string representing list

Returns:

A string representing list.