LinkedCollection

//---------------------------------------------------------------------------
// LinkedCollection.java          by Dale/Joyce/Weems               Chapter 5
//
// Implements the CollectionInterface using a linked collection.
// Null elements are not allowed. Duplicate elements are allowed.
// One constructor is provided, one that creates an empty collection.
//---------------------------------------------------------------------------

public class LinkedCollection implements CollectionInterface {
   protected LLNode head;       // head of the linked list
   protected int numElements = 0;  // number of elements in this collection

   // set by find method
   protected boolean found;        // true if target found, else false
   protected LLNode location;   // node containing target, if found
   protected LLNode previous;   // node preceding location

   public LinkedCollection() {
      numElements = 0;
      head = null;
   }

   public boolean add(T element) {
   // Adds element to this collection.
      LLNode newNode = new LLNode(element);
      newNode.setLink(head);
      head = newNode;
      numElements++;
      return true;
   }

   protected void find(T target) {
   // Searches the collection for an occurence of an element e such that
   // e.equals(target). If successful, sets instance variables
   // found to true, location to node containing e, and previous
   // to the node that links to location. If not successful, sets
   // found to false.
      location = head;
      found = false;

      while (location != null) {
         if (location.getInfo().equals(target)) {  // if they match
            found = true;
            return;
         }
         else {
            previous = location;
            location = location.getLink();
         }
      }
   }

   public int size() {
   // Returns the number of elements on this collection.
      return numElements;
   }

   public boolean contains (T target) {
   // Returns true if this collection contains an element e such that
   // e.equals(target); otherwise, returns false.
      find(target);
      return found;
   }

   public boolean remove (T target) {
   // Removes an element e from this collection such that e.equals(target)
   // and returns true; if no such element exists, returns false.
      find(target);
      if (found) {
         if (head == location)
            head = head.getLink();    // remove first node
         else
            previous.setLink(location.getLink());  // remove node at location

         numElements--;
      }
      return found;
   }

   public T get(T target) {
   // Returns an element e from this collection such that e.equals(target);
   // if no such element exists, returns null.
      find(target);
      if (found)
          return location.getInfo();
      else
          return null;
   }

   public boolean isEmpty() {
   // Returns true if this collection is empty; otherwise, returns false.
      return (numElements == 0);
   }

   public boolean isFull() {
   // Returns true if this collection is full; otherwise, returns false.
      return false;  // Linked implementation is never full
   }
}

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page