Cosc241 - Java

Lab 12: Single and Double Linked Lists


SLL.java


package lab12;

/**
 * This class implements singly linked lists.
 *
 * @author Iain Hewson
 */
public class SLL<E> {

   /** Specifies the first node in this SLL. */
   private Node<E> first;

   /** Construct an empty SLL. */
   public SLL() {
      this.first = null;
   }

   /**
    * Return the first element in this list, or null if list empty.
    * 
    * @return the first element in this list, or null if list empty.
    */
   public E getFirst() {
      return first == null ? null : first.element;
   }

   /**
    * Add the element elem to the start of the list.
    * 
    * @param elem the element to add to the list.
    */
   public void addFirst(E elem) {
      insert(elem, null);
   }

   /**
    * Add elem to the end of the list.
    * 
    * @param elem an element to add to the list.
    */
   public void addLast(E elem) {
      if (first == null) {
         insert(elem, null);
      } else {
         Node<E> curr = first;
         while (curr.next != null) {
            curr = curr.next;
         }
         insert(elem, curr);
      }
   }
   
   /**
    * Add the element elem after the element prev.  If prev is not in the
    * list then add elem at the end.
    * 
    * @param elem the element to add to the list.
    * @param prev the element to add elem after.
    */
   public void addAfter(E elem, E prev) {
      if (first == null) {
         insert(elem, null);
      } else {
         Node<E> curr = first;
         while (curr.next != null && !curr.element.equals(prev)) {
            curr = curr.next;
         }
         insert(elem, curr);
      }
   }
     

   /**
    *  Delete the first occurence of the element target from this SLL.
    *
    * @param target an element to delete from this SLL.
    */
   public void delete(E target) {
      Node<E> node = search(target);
      if (node == null) {
         return;
      } else if (node == first) {
         first = node.next;
      } else {
         Node<E> tmp = first;
         while (tmp.next != null && tmp.next != node) {
            tmp = tmp.next;
         }
         tmp.next = node.next;
      }
   }

   /**
    *  Returns the number of nodes in this SLL.
    *
    * @return the number of nodes in this SLL.
    */
   public int size() {
      int size = 0;
      for (Node<E> curr = first; curr != null; curr = curr.next) {
         size++;
      }
      return size;
   }

   /**
    *  String representation of SLL to allow System.out.println(aList).
    *
    * @return    A String representing this SLL.
    */
   public String toString() {
      StringBuilder s = new StringBuilder("[");
      for (Node<E> curr = first; curr != null; curr = curr.next) {
         s.append(curr.element);
         if (curr.next != null) {
            s.append(", ");
         }
      }
      return s.append("]").toString();
   }

   /**
    *  Insert elem at a given point in this SLL, either after the node prev, or
    *  before the first node if prev is null. 
    *
    * @param  elem  The element to store in the new node.
    * @param  prev  The node to store the new node after.
    */
   private void insert(E elem, Node<E> prev) {
      Node<E> newNode = new Node<E>(elem, null);
      if (prev == null) {
         newNode.next = first;
         first = newNode;
      } else {
         newNode.next = prev.next;
         prev.next = newNode;
      }
   }
   
   /**
    *  Find which (if any) node of this SLL contains an element equal to target.
    *  Return a link to the matching node (or null if there is none).
    *
    * @param  target  The element to search this SLL for.
    * @return  The first node in this list containing target (or null if there
    *          is none).
    */
   private Node<E> search(E target) {
      for (Node<E> curr = first; curr != null; curr = curr.next) {
         if (target.equals(curr.element)) {
            return curr;
         }
      }
      return null;
   }   

   /**
    * A simple container class which holds an element, and a reference to
    * the next Node.
    */
   private static class Node<E> {

      /** The element this Node holds. */
      private E element;

      /** Holds the Node after this one. */
      private Node<E> next;


      /** Create a new Node with the given element, adjacent nodes.
       *
       * @param elem the element this Node holds.
       * @param next the Node which comes after this one.
       */
      public Node(E elem, Node<E> next) {
         this.element = elem;
         this.next = next;
      }

      /** Return a string representation of this Node.
       *
       * @return a string representation of this Node.
       */
      public String toString() {
         return element.toString();
      }

   } // end class Node
   
   
   
   
   
   
     public void searchAndInsert(E elem1, E elem2) {
    
    Node<E> node1 = search(elem1);
    
    insert(elem2, node1);
    
  }
   
   
   
   
   
   
   
   
   
   
   
   
   

}// end class SLL


SLLApp.java


package lab12;

import java.util.*;

/**
 * @author Mike
 *
 */

import java.util.Scanner;


public class SLLApp {
  
  /**
   * @param args
   */
  public static void main(String[] args) {  // main method does stuff
    Scanner input = new Scanner(System.in);  // as input from user 
    SLL<String> sList = new SLL<String>();
    while (input.hasNextLine()) {  
      handleLine(input.nextLine(), sList);
    }
  }
  
  
  public static void handleLine(String line, SLL sList) {
    Scanner tokens = new Scanner(line);
    if (tokens.hasNext("[aesdpr]")) { //if next token is a, r or p
      char command = tokens.next().charAt(0);
      switch (command) {
        case 'a':   // if next token is a, insert elem1 after elem2
          while (tokens.hasNext()){ 
          Object elem1 = tokens.next();
          Object elem2 = tokens.next();
          sList.searchAndInsert(elem1, elem1);
        }
          break;
        case 'e': // if e, insert element at end of list
          while (tokens.hasNext()){ 
          Object elem = tokens.next();
          sList.addLast(elem);
        }
          break;
        case 's': // if s, insert element at start of list
          while (tokens.hasNext()){ 
          sList.addFirst(tokens.next());
        }
          break;
        case 'd': // if d, delete given element if it's there
          while (tokens.hasNext()){ 
          Object elem = tokens.next();
          sList.delete(elem);
        }
          break;
        case 'p': // if p, print out result of toString method
          System.out.println(sList.toString());
          break;
      }
    }
  }
}

DLL.java


package lab12;

/**
 * This class implements doubly linked lists, as covered in Cosc241 lectures.
 *
 * @author  Iain Hewson
 */
public class DLL<E> {
  
  /** A reference to the first node in this DLL. */
  private Node<E> first;
  
  /** A reference to the last node in this DLL. */
  private Node<E> last;
  
//  private Node<E> next;
  /**
   * Construct an empty DLL.
   */
  public DLL() {
    first = null;
    last = null;
  }
  
  /**
   * Return the first element in this DLL, or null if DLL empty.
   *
   * @return  The first element in this DLL, or null if DLL empty.
   */
  public E getFirst() {
    return first != null ? first.element : null;
  }
  
  /**
   * Return the last element in this DLL, or null if DLL empty.
   *
   * @return  The last element in this DLL, or null if DLL empty.
   */
  public E getLast() {
    return last != null ? last.element : null;
  }
  
  /**
   * Return the number of nodes in this DLL.
   *
   * @return  The number of nodes in this DLL.
   */
  public int size() {  // implement this method
    int size = 0;
    for (Node<E> curr = first; curr != null; curr = curr.next) {
      size++;
    }
    return size;
  }
  
  /**
   * Add an element to the start of this DLL.
   *
   * @param elem  An element to add to the start of this DLL.
   */
  public void addFirst(E elem) {
    insert(elem, null);
  }
  
  /**
   * Add an element to the end of this DLL.
   *
   * @param elem  An element to add to the end of this DLL.
   */
  public void addLast(E elem) {
    // implement this method (only takes one line of code)
    addAfter(elem, getLast()); // changed from insert
  }
  
  /**
   * Add a new element after the element 'prev' (or at the end of this DLL if
   * 'prev' isn't found).
   *
   * @param elem  A new element to add to this DLL.
   * @param prev  An element to add 'elem' after.
   */
  public void addAfter(E elem, E prev) {
    // implement this method (start by searching for prev)
    
  Node<E> node = search(prev);
  System.out.println(node);//////////////////////////////////////////////
    
  insert(elem, node);
  
  /*
    if (first == null) {
      insert(elem, null);
    } else {
      Node<E> curr = first;
      while (curr.next != null && !curr.element.equals(node)) {
        curr = curr.next;
         System.out.println(curr);///////////////////////////////////////
      }
      insert(elem, node);
      System.out.println(curr);///////////////////////////////////////
    }
    */
  }
  
  /**
   * Delete a given element from this DLL.
   *
   * @param elem  An element to delete from this DLL.
   */
  public void delete(E elem) {
    // implement this method
    Node<E> node = search(elem);
    if (node == null) {
      return;
    } else if (node == first) {
      first = node.next;
    } else {
      Node<E> tmp = first;
      while (tmp.next != null && tmp.next != node) {
        tmp = tmp.next;
      }
      tmp.next = node.next;
    }
  }
  
  /**
   * Return a string representation of DLL to allow System.out.println(aList).
   *
   * @return  A String representation of this DLL.
   */
  public String toString() {
    String result = "[";
    for (Node<E> curr = first; curr != null; curr = curr.next) {
      result += curr;
      if (curr != getLast()) {
        result += ", ";
      }
    }
    return result + "]";
  }
  
  /**
   * Return a string representation of all the elements in this DLL, in 
   * last-to-first order.
   *
   * @return  A String representation of this DLL in reverse order.
   */
  public String reverseString() {
    // implement this method (very similar to the toString method)
    String result = "[";
    for (Node<E> curr = last; curr != null; curr = curr.prev) {
      result += curr;
      if (curr != first) {
        result += ", ";
      }
    }
    return result + "]";
  }
  
  /**
   * Find the first Node which contains the given element.
   *
   * @param elem  The element to search for.
   * @return The first Node containing the given element, or null if no Node
   *         contains the element.
   */
  
     private Node<E> search(E elem) {
       // implement this method (use a for loop like in the toString)
      for (Node<E> curr = first; curr != null; curr = curr.next) {
         if (elem.equals(curr.element)) {
           System.out.println(curr);////////////////////////////////////////
            return curr;
         }
      }
      return null;
   }   
  
  /**
   * Insert a new element after the element 'prev'.  If 'prev' is null then
   * insert 'elem' at the front of this DLL.
   *
   * @param elem  A new element to insert into this DLL.
   * @param prev  An element to insert 'elem' after. If 'prev' is null insert
   * 'elem' at the start of this DLL.
   */
  private void insert(E elem, Node<E> prev) {
    // implement this method
    
    Node<E> newNode = new Node<E>(elem, prev, null);
      if (prev == null) {
         newNode.next = first;
         first = newNode;
         newNode.prev = last;
      } else {
         newNode.next = prev.next;
         prev.next = newNode;
      }      
    }
    
    /**
     * A simple container class which holds an element, and references to
     * previous and next Nodes.
     */
    private static class Node<E> {
      
      /** The element this Node holds. */
      private E element;
      
      /** A reference to the Node before this one. */
      private Node<E> prev;
      
      /** A reference to the Node after this one. */
      private Node<E> next;
      
      
      /** 
       * Create a new Node with the given element, adjacent nodes.
       *
       * @param elem  The element this Node holds.
       * @param prev  The Node which comes before this one.
       * @param next  The Node which comes after this one.
       */
      public Node(E elem, Node<E> prev, Node<E> next) {
        this.element = elem;
        this.prev = prev;
        this.next = next;
      }
      
      /** 
       * Return a string representation of this Node.
       *
       * @return A string representation of this Node.
       */
      public String toString() {
        return element.toString();
      }
      
    } // end class Node
    
  } // end class DLL

DLLApp.java


package lab12;

import java.util.*;

/**
 * @author Mike
 *
 */

import java.util.Scanner;


public class DLLApp {
  
  /**
   * @param args
   */
  public static void main(String[] args) {  // main method does stuff
    Scanner input = new Scanner(System.in);  // as input from user 
    DLL<String> dList = new DLL<String>();
    while (input.hasNextLine()) {  
      handleLine(input.nextLine(), dList);
    }
  }
  
  
  public static void handleLine(String line, DLL dList) {
    Scanner tokens = new Scanner(line);
    if (tokens.hasNext("[aesdpr]")) { //if next token is a, r or p
      char command = tokens.next().charAt(0);
      switch (command) {
        case 'a':   // if next token is a, insert elem1 after elem2
          while (tokens.hasNext()){ 
          Object elem1 = tokens.next();
          Object elem2 = tokens.next();
          dList.addAfter(elem1, elem1);
        }
          break;
        case 'e': // if e, insert element at end of list
          while (tokens.hasNext()){ 
          Object elem = tokens.next();
          dList.addLast(elem);
        }
          break;
        case 's': // if s, insert element at start of list
          while (tokens.hasNext()){ 
          dList.addFirst(tokens.next());
        }
          break;
        case 'd': // if d, delete given element if it's there
          while (tokens.hasNext()){ 
          Object elem = tokens.next();
          dList.delete(elem);
        }
          break;
        case 'p': // if p, print out result of toString method
          System.out.println(dList.toString());
          break;
        case 'r': // if p, print out result of toString method
          System.out.println(dList.reverseString());
          break;
      }
    }
  }
}