structure5
Class SinglyLinkedList<E>

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

All Implemented Interfaces:

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

public class SinglyLinkedList<E>
extends AbstractList<E>

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 Node<E>	head The head of the list.

Constructor Summary

SinglyLinkedList()
Construct an empty list.

Method Summary

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

Methods inherited from class structure5.AbstractList

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

count

protected int count

The number of elements in list.

head

protected Node<E> head

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

Constructor Detail

SinglyLinkedList

public SinglyLinkedList()

Construct an empty list.

Postcondition:

generates an empty list

Method Detail

add

public void add(E value)

Add an object to tail of list.

Specified by:

add in interface List<E>

Specified by:

add in interface Structure<E>

Overrides:

add in class AbstractList<E>

Parameters:

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

See Also:

AbstractList.addLast(E)

Postcondition:

value is added to end of list (see addLast)

addFirst

public void addFirst(E value)

Add a value to head of list.

Specified by:

addFirst in interface List<E>

Overrides:

addFirst in class AbstractList<E>

Parameters:

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

Postcondition:

value is added to beginning of list

removeFirst

public E removeFirst()

Remove a value from first element of list.

Specified by:

removeFirst in interface List<E>

Overrides:

removeFirst in class AbstractList<E>

Returns:

The value actually removed.

Precondition:

list is not empty

Postcondition:

removes and returns value from beginning of list

addLast

public void addLast(E value)

Add a value to tail of list.

Specified by:

addLast in interface List<E>

Overrides:

addLast in class AbstractList<E>

Parameters:

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

Postcondition:

adds value to end of list

removeLast

public E removeLast()

Remove last value from list.

Specified by:

removeLast in interface List<E>

Overrides:

removeLast in class AbstractList<E>

Returns:

The value actually removed.

Precondition:

list is not empty

Postcondition:

removes last value from list

getFirst

public E getFirst()

Fetch first element of list.

Specified by:

getFirst in interface List<E>

Overrides:

getFirst in class AbstractList<E>

Returns:

A reference to first element of list.

Precondition:

list is not empty

Postcondition:

returns first value in list

getLast

public E getLast()

Fetch last element of list.

Specified by:

getLast in interface List<E>

Overrides:

getLast in class AbstractList<E>

Returns:

A reference to last element of list.

Precondition:

list is not empty

Postcondition:

returns last value in list

contains

public boolean contains(E value)

Check to see if a value is in list.

Specified by:

contains in interface List<E>

Specified by:

contains in interface Structure<E>

Overrides:

contains in class AbstractList<E>

Parameters:

value - The value sought.

Returns:

True if value is within list.

Precondition:

value is not null

Postcondition:

returns true iff value is found in list

remove

public E remove(E value)

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

Parameters:

value - The value to be removed.

Returns:

The actual value removed.

Precondition:

value is not null

Postcondition:

removes first element with matching value, if any

size

public int size()

Determine number of elements in list.

Returns:

The number of elements in list.

Postcondition:

returns number of elements in list

clear

public void clear()

Remove all values from list.

Postcondition:

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

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 the (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 the (0-origin) index of value, or -1 if value is not found

iterator

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

Returns an iterator traversing list from head to tail.

Returns:

An iterator to traverse list.

See Also:

AbstractIterator, Iterator, Enumeration, Structure.elements()

Postcondition:

returns enumeration allowing traversal of list

toString

public java.lang.String toString()

Construct a string representing list.

Overrides:

toString in class java.lang.Object

Returns:

A string representing list.

Postcondition:

returns a string representing list