net.datastructures
Class NodeList

java.lang.Object
  net.datastructures.NodeList

All Implemented Interfaces:

List

Direct Known Subclasses:

NodeSequence

public class NodeList

extends Object

implements List

Realization of a List using a doubly-linked list of nodes.

Author:

Michael Goodrich, Natasha Gelfand, Roberto Tamassia, Eric Zamore

Field Summary

protected DNode	header
protected int	numElts
protected DNode	trailer

Constructor Summary

NodeList()
Constructor that creates an empty list; O(1) time

Method Summary

protected DNode	checkPosition(Position p) Checks if position is valid for this list and converts it to DNode if it is valid; O(1) time
Iterator	elements() Returns an iterator of all the elements in the list.
Position	first() Returns the first position in the list; O(1) time
Position	insertAfter(Position p, Object element) Insert the given element after the given position, returning the new position; O(1) time
Position	insertBefore(Position p, Object element) Insert the given element before the given position, returning the new position; O(1) time
Position	insertFirst(Object element) Insert the given element at the beginning of the list, returning the new position; O(1) time
Position	insertLast(Object element) Insert the given element at the end of the list, returning the new position; O(1) time
boolean	isEmpty() Returns whether the list is empty; O(1) time
boolean	isFirst(Position p) Returns whether a position is the first one; O(1) time
boolean	isLast(Position p) Returns whether a position is the last one; O(1) time
Position	last() Returns the last position in the list; O(1) time
Position	next(Position p) Returns the position after the given one; O(1) time
Iterator	positions() Returns an iterator of all the nodes in the list.
Position	prev(Position p) Returns the position before the given one; O(1) time
Object	remove(Position p) Remove the given position from the list; O(1) time
Object	replace(Position p, Object element) Replace the element at the given position with the new element and return the old element; O(1) time
int	size() Returns the number of elements in the list; O(1) time
void	swapElements(Position a, Position b) Swap the elements of two give positions; O(1) time
String	toString() Returns a textual representation of the list

Methods inherited from class java.lang.Object

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

Field Detail

numElts

protected int numElts

header

protected DNode header

trailer

protected DNode trailer

Constructor Detail

NodeList

public NodeList()

Constructor that creates an empty list; O(1) time

Method Detail

checkPosition

protected DNode checkPosition(Position p)
                       throws InvalidPositionException

Checks if position is valid for this list and converts it to DNode if it is valid; O(1) time

Throws:

InvalidPositionException

size

public int size()

Returns the number of elements in the list; O(1) time

Specified by:

size in interface List

isEmpty

public boolean isEmpty()

Returns whether the list is empty; O(1) time

Specified by:

isEmpty in interface List

first

public Position first()
               throws EmptyListException

Returns the first position in the list; O(1) time

Specified by:

first in interface List

Throws:

EmptyListException

last

public Position last()
              throws EmptyListException

Returns the last position in the list; O(1) time

Specified by:

last in interface List

Throws:

EmptyListException

prev

public Position prev(Position p)
              throws InvalidPositionException,
                     BoundaryViolationException

Returns the position before the given one; O(1) time

Specified by:

prev in interface List

Throws:

InvalidPositionException

BoundaryViolationException

next

public Position next(Position p)
              throws InvalidPositionException,
                     BoundaryViolationException

Returns the position after the given one; O(1) time

Specified by:

next in interface List

Throws:

InvalidPositionException

BoundaryViolationException

insertBefore

public Position insertBefore(Position p,
                             Object element)
                      throws InvalidPositionException

Insert the given element before the given position, returning the new position; O(1) time

Specified by:

insertBefore in interface List

Throws:

InvalidPositionException

insertAfter

public Position insertAfter(Position p,
                            Object element)
                     throws InvalidPositionException

Insert the given element after the given position, returning the new position; O(1) time

Specified by:

insertAfter in interface List

Throws:

InvalidPositionException

insertFirst

public Position insertFirst(Object element)

Insert the given element at the beginning of the list, returning the new position; O(1) time

Specified by:

insertFirst in interface List

insertLast

public Position insertLast(Object element)

Insert the given element at the end of the list, returning the new position; O(1) time

Specified by:

insertLast in interface List

remove

public Object remove(Position p)
              throws InvalidPositionException

Remove the given position from the list; O(1) time

Specified by:

remove in interface List

Throws:

InvalidPositionException

replace

public Object replace(Position p,
                      Object element)
               throws InvalidPositionException

Replace the element at the given position with the new element and return the old element; O(1) time

Specified by:

replace in interface List

Throws:

InvalidPositionException

positions

public Iterator positions()

Returns an iterator of all the nodes in the list.

Specified by:

positions in interface List

elements

public Iterator elements()

Returns an iterator of all the elements in the list.

Specified by:

elements in interface List

isFirst

public boolean isFirst(Position p)
                throws InvalidPositionException

Returns whether a position is the first one; O(1) time

Throws:

InvalidPositionException

isLast

public boolean isLast(Position p)
               throws InvalidPositionException

Returns whether a position is the last one; O(1) time

Throws:

InvalidPositionException

swapElements

public void swapElements(Position a,
                         Position b)
                  throws InvalidPositionException

Swap the elements of two give positions; O(1) time

Throws:

InvalidPositionException

toString

public String toString()

Returns a textual representation of the list