Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on May 5th, 2013  |  syntax: None  |  size: 6.74 KB  |  views: 46  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /**
  2.    The LinkedList1 class implements a Linked list.
  3. */
  4.  
  5. class LinkedList1
  6. {
  7.     /**
  8.        The Node class stores a list element
  9.        and a reference to the next node.
  10.     */
  11.    
  12.     private class Node
  13.     {
  14.         String value;  
  15.         Node next;      
  16.        
  17.         /**
  18.            Constructor.            
  19.            @param val The element to store in the node.
  20.            @param n The reference to the successor node.
  21.         */
  22.        
  23.         Node(String val, Node n)
  24.         {
  25.             value = val;
  26.             next = n;
  27.         }
  28.        
  29.         /**
  30.            Constructor.
  31.            @param val The element to store in the node.
  32.         */
  33.        
  34.         Node(String val)
  35.         {
  36.            // Call the other (sister) constructor.
  37.            this(val, null);            
  38.         }
  39.     }  
  40.          
  41.     private Node first;  // list head
  42.     private Node last;   // last element in list
  43.              
  44.     /**
  45.        Constructor.
  46.     */
  47.    
  48.     public LinkedList1()
  49.     {
  50.         first = null;
  51.         last = null;        
  52.     }
  53.    
  54.     /**
  55.        The isEmpty method checks to see
  56.                  if the list is empty.
  57.                  @return true if list is empty,
  58.                  false otherwise.
  59.     */
  60.    
  61.     public boolean isEmpty()
  62.     {        
  63.         return first == null;      
  64.     }
  65.    
  66.     /**
  67.        The size method returns the length of the list.
  68.        @return The number of elements in the list.
  69.     */
  70.    
  71.     public int size()
  72.     {
  73.        int count = 0;
  74.        Node p = first;    
  75.                  while (p != null)
  76.        {
  77.            // There is an element at p
  78.            count ++;
  79.            p = p.next;
  80.        }
  81.        return count;
  82.     }
  83.    
  84.     /**
  85.        The add method adds an element to
  86.                  the end of the list.
  87.        @param e The value to add to the
  88.                  end of the list.      
  89.     */
  90.    
  91.     public void add(String e)
  92.     {
  93.       if (isEmpty())
  94.       {
  95.           first = new Node(e);
  96.           last = first;
  97.       }
  98.       else
  99.       {
  100.           // Add to end of existing list
  101.           last.next = new Node(e);
  102.           last = last.next;
  103.       }      
  104.     }
  105.    
  106.     /**
  107.        The add method adds an element at a position.
  108.        @param e The element to add to the list.
  109.        @param index The position at which to add
  110.                  the element.
  111.        @exception IndexOutOfBoundsException When
  112.                  index is out of bounds.  
  113.     */
  114.    
  115.     public void add(int index, String e)
  116.     {
  117.          if (index < 0  || index > size())
  118.          {
  119.              String message = String.valueOf(index);
  120.              throw new IndexOutOfBoundsException(message);
  121.          }
  122.          
  123.          // Index is at least 0
  124.          if (index == 0)
  125.          {
  126.              // New element goes at beginning
  127.              first = new Node(e, first);
  128.              if (last == null)
  129.                  last = first;
  130.              return;
  131.          }
  132.          
  133.          // Set a reference pred to point to the node that
  134.          // will be the predecessor of the new node
  135.          Node pred = first;        
  136.          for (int k = 1; k <= index - 1; k++)        
  137.          {
  138.             pred = pred.next;          
  139.          }
  140.          
  141.          // Splice in a node containing the new element
  142.          pred.next = new Node(e, pred.next);  
  143.          
  144.          // Is there a new last element ?
  145.          if (pred.next.next == null)
  146.              last = pred.next;        
  147.     }
  148.    
  149.     /**
  150.        The toString method computes the string
  151.        representation of the list.
  152.        @return The string form of the list.
  153.     */
  154.    
  155.     public String toString()
  156.     {
  157.       StringBuilder strBuilder = new StringBuilder();
  158.      
  159.       // Use p to walk down the linked list
  160.       Node p = first;
  161.       while (p != null)
  162.       {
  163.          strBuilder.append(p.value + "\n");
  164.          p = p.next;
  165.       }      
  166.       return strBuilder.toString();
  167.     }
  168.    
  169.     /**
  170.        The remove method removes the element at an index.
  171.        @param index The index of the element to remove.
  172.        @return The element removed.  
  173.        @exception IndexOutOfBoundsException When index is
  174.                   out of bounds.    
  175.     */
  176.    
  177.     public String remove(int index)
  178.     {
  179.        if (index < 0 || index >= size())
  180.        {  
  181.            String message = String.valueOf(index);
  182.            throw new IndexOutOfBoundsException(message);
  183.        }
  184.        
  185.        String element;  // The element to return    
  186.        if (index == 0)
  187.        {
  188.           // Removal of first item in the list
  189.           element = first.value;    
  190.           first = first.next;
  191.           if (first == null)
  192.               last = null;            
  193.        }
  194.        else
  195.        {
  196.           // To remove an element other than the first,
  197.           // find the predecessor of the element to
  198.           // be removed.
  199.           Node pred = first;
  200.          
  201.           // Move pred forward index - 1 times
  202.           for (int k = 1; k <= index -1; k++)
  203.               pred = pred.next;
  204.          
  205.           // Store the value to return
  206.           element = pred.next.value;
  207.          
  208.           // Route link around the node to be removed
  209.           pred.next = pred.next.next;  
  210.          
  211.           // Check if pred is now last
  212.           if (pred.next == null)
  213.               last = pred;              
  214.        }
  215.        return element;        
  216.     }  
  217.    
  218.     /**
  219.        The remove method removes an element.
  220.        @param element The element to remove.
  221.        @return true if the remove succeeded,
  222.                  false otherwise.
  223.     */
  224.    
  225.     public boolean remove(String element)
  226.     {
  227.        if (isEmpty())
  228.            return false;      
  229.      
  230.        if (element.equals(first.value))
  231.        {
  232.           // Removal of first item in the list
  233.           first = first.next;
  234.           if (first == null)
  235.               last = null;      
  236.           return true;
  237.        }
  238.      
  239.       // Find the predecessor of the element to remove
  240.       Node pred = first;
  241.       while (pred.next != null &&
  242.              !pred.next.value.equals(element))
  243.       {
  244.           pred = pred.next;
  245.       }
  246.  
  247.       // pred.next == null OR pred.next.value is element
  248.       if (pred.next == null)
  249.           return false;
  250.      
  251.       // pred.next.value  is element
  252.       pred.next = pred.next.next;    
  253.      
  254.       // Check if pred is now last
  255.       if (pred.next == null)
  256.           last = pred;
  257.      
  258.       return true;      
  259.     }
  260.    
  261.     public static void main(String [] args)
  262.     {
  263.         LinkedList1 ll = new LinkedList1();
  264.         ll.add("Amy");
  265.         ll.add("Bob");
  266.         ll.add(0, "Al");
  267.         ll.add(2, "Beth");
  268.         ll.add(4, "Carol");
  269.         System.out.println("The members of the list are:");
  270.         System.out.print(ll);
  271.     }
  272. }
clone this paste RAW Paste Data