All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class rpi.goldsd.container.LinkedList 

java.lang.Object
   |
   +----rpi.goldsd.container.LinkedList
public class LinkedList
extends Object
The LinkedList class provides a generic linked list container by managing a doubly linked list of ListNode objects.

Version:
1.3, 4/16/98
Author:
David Goldschmidt
See Also:
ListNode, Comparable

Variable Index

o head
A reference to the first element of this linked-list.
o numElements
The number of elements in this linked-list.
o tail
A reference to the last element of this linked-list.

Constructor Index

o LinkedList()
The default constructor simply sets the protected data elements of this linked-list to values indicating an empty list.

Method Index

o addAfter(ListNode, ListNode)
Adds a new ListNode object to this linked-list after the given ListNode object existingNode.
o addToHead(ListNode)
Adds a new ListNode object to this linked-list at the beginning of the list.
o addToTail(ListNode)
Adds a new ListNode object to this linked-list at the end of the list.
o contains(Comparable)
Tests whether the given Comparable object exists in this linked-list by using the isEqualTo() method.
o containsReferenceTo(ListNode)
Tests whether the given ListNode object exists in this linked-list by comparing the references of the objects (using the == operator).
o elements()
Provides an enumeration or traversal of this linked-list starting at the beginning of the list.
o find(Comparable)
Traverses this linked-list to find the given Comparable object by using the isEqualTo() method.
o getSize()
Returns the number of elements in this linked-list.
o isEmpty()
Returns true if this linked-list contains no elements.
o remove(Comparable)
Removes and returns a reference to the first occurrence of the given ListNode or Comparable object.
o removeFromHead()
Removes and returns a reference to the ListNode object that is currently the head of this list.
o removeFromTail()
Removes and returns a reference to the ListNode object that is currently the tail of this list.
o toString()
The toString() is the default method used to display this linked-list in the form of a String object.

Variables

o head 
 protected ListNode head
A reference to the first element of this linked-list.

o numElements 
 protected int numElements
The number of elements in this linked-list.

o tail 
 protected ListNode tail
A reference to the last element of this linked-list.

Constructors

o LinkedList 
 public LinkedList()
The default constructor simply sets the protected data elements of this linked-list to values indicating an empty list.

This method performs in constant time O(1).

Methods

o addAfter 
 public synchronized void addAfter(ListNode existingNode,
                                   ListNode newNode)
Adds a new ListNode object to this linked-list after the given ListNode object existingNode.

This method performs in constant time O(1); however, this method assumes that the existingNode does indeed exist in this linked-list.

Parameters:
existingNode - the element after which newNode will be added to this linked-list.
newNode - the element to be added to this linked-list.
o addToHead 
 public synchronized void addToHead(ListNode newNode)
Adds a new ListNode object to this linked-list at the beginning of the list.

This method performs in constant time O(1).

Parameters:
newNode - the element to be added to the beginning of this linked-list.
o addToTail 
 public synchronized void addToTail(ListNode newNode)
Adds a new ListNode object to this linked-list at the end of the list.

This method performs in constant time O(1).

Parameters:
newNode - the element to be added to the end of this linked-list.
o contains 
 public synchronized boolean contains(Comparable node)
Tests whether the given Comparable object exists in this linked-list by using the isEqualTo() method.

This method performs in linear time O(n).

Parameters:
node - the ListNode or Comparable object to be found in this linked-list.
Returns:
true if node is in this linked-list; false otherwise.
o containsReferenceTo 
 public synchronized boolean containsReferenceTo(ListNode node)
Tests whether the given ListNode object exists in this linked-list by comparing the references of the objects (using the == operator).

This method performs in linear time O(n).

Parameters:
node - the ListNode object to be found in this linked-list.
Returns:
true if node is in this linked-list; false otherwise.
o elements 
 public synchronized Enumeration elements()
Provides an enumeration or traversal of this linked-list starting at the beginning of the list. The nextElement() method of the instantiated Enumeration object returns the next ListNode object in this list.

This method performs in constant time O(1); however, note that an algorithm making use of the resulting Enumeration will likely be linear O(n).

Returns:
an Enumeration object representing a traversal of this linked-list from head to tail.
o find 
 public ListNode find(Comparable node)
Traverses this linked-list to find the given Comparable object by using the isEqualTo() method.

This method performs in linear time O(n).

Parameters:
node - the ListNode or Comparable object to be found in this linked-list.
Returns:
a reference to the ListNode that was found; or null if not found.
o getSize 
 public synchronized int getSize()
Returns the number of elements in this linked-list.

This method performs in constant time O(1).

Returns:
the number of elements in this linked-list.
o isEmpty 
 public synchronized boolean isEmpty()
Returns true if this linked-list contains no elements.

This method performs in constant time O(1).

Returns:
true if this linked-list contains no elements; false otherwise.
o remove 
 public synchronized ListNode remove(Comparable node)
Removes and returns a reference to the first occurrence of the given ListNode or Comparable object. To find the given object in this linked-list, the isEqualTo() method is applied to the given argument and each node of this linked-list. Note that the reference that is returned refers to the ListNode object that is removed (or null if not found).

This method performs in linear time O(n).

Parameters:
node - the ListNode or Comparable object to be removed from this linked-list.
Returns:
the removed ListNode object; or null if no object is removed from this linked-list.
o removeFromHead 
 public synchronized ListNode removeFromHead()
Removes and returns a reference to the ListNode object that is currently the head of this list.

This method performs in constant time O(1).

Returns:
the removed ListNode object; or null if the list contains no elements.
o removeFromTail 
 public synchronized ListNode removeFromTail()
Removes and returns a reference to the ListNode object that is currently the tail of this list.

This method performs in constant time O(1).

Returns:
the removed ListNode object; or null if the list contains no elements.
o toString 
 public synchronized String toString()
The toString() is the default method used to display this linked-list in the form of a String object.

Returns:
a String representing this linked-list.
Overrides:
toString in class Object 
All Packages  Class Hierarchy  This Package  Previous  Next  Index