Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 1 of 1

Thread: Duplicating Elements through Recursion

  1. #1
    Junior Member
    Join Date
    Feb 2011
    Posts
    6
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Exclamation Duplicating Elements through Recursion

    /** 
      * A list implemented using a singly-linked list and using recursive methods
      * @author         Edo Biagioni
      * @lecture        ICS 211 Jan 27 (or later)
      * @date           January 26, 2010
      */
     
    public class LinkedListRec<E> {
     
      // here, include the LinkedNode definition
     
              /** 
                * A node in a singly-linked list
                * @author         Edo Biagioni
                * @lecture        ICS 211 Jan 27 or later
                * @date           January 26, 2010
                */
     
              private static class LinkedNode<T> {
                private T item;
                private LinkedNode<T> next;
     
     
              /** 
                * constructor to build a node with no successor
                * @param the value to be stored by this node
                */
                private LinkedNode(T value) {
                  item = value;
                  next = null;
                }
     
     
              /** 
                * constructor to build a node with specified (maybe null) successor
                * @param the value to be stored by this node
                * @param the next field for this node
                */
                private LinkedNode(T value, LinkedNode<T> reference) {
                  item = value;
                  next = reference;
                }
              }
      // end of the LinkedNode definition
     
     
      // this is the start of the linked list.  If the list is empty, it is null
      protected LinkedNode<E> head;
     
      /** 
        * initializes an empty linked list
        */
      public LinkedListRec() {
        head = null;
      }
     
      /** recursive private method, called by the public wrapper method 
        * @param the head of the list (may be null if we are at the end)
        * @return the size of the list
        */
      private int size(LinkedNode<E> current) {
        if (current == null) {
          return 0;  // an empty list has size 0
        }  // a non-empty list has size 1 more than the rest of the list:
        return 1 + size (current.next);
      }
     
      /** public wrapper method, calls the private recursive method 
      public int size() {
        return size(head);
      }
     
      /** recursive private method, called by the public wrapper method 
        * @param the head of the list (may be null if we are at the end)
        * @param the value to be added
        * @return the list, with the value added
        */
      private LinkedNode<E> addAtEnd(LinkedNode<E> node, E value) {
        if (node == null) {
          return new LinkedNode<E>(value);
        }
        node.next = addAtEnd(node.next, value);
        return node;
      }
     
      /** public wrapper method, calls the private recursive method 
        * @param the value to be added at the end of the linked list
        */
      public void add(E value) {
        head = addAtEnd(head, value);
      }
     
      /** recursive private method, called by the public wrapper method 
        * @param the head of the list (may be null if we are at the end)
        * @param the number of nodes to skip before inserting
        * @param the value to be added
        * @return the list, with the value added
        */
      private LinkedNode<E> addAtPosition(LinkedNode<E> node, int skip, E value) {
        if (skip == 0) {
          return new LinkedNode<E>(value, node);
        }
        if (node == null) {  // node is null but skip > 0 -- bad index
          throw new IndexOutOfBoundsException("bad index for add");
        }
        node.next = addAtPosition(node.next, skip - 1, value);
        return node;
      }
     
      /** public wrapper method, calls the private recursive method 
        * @param the position at which to add: 0 to add at the start
        * @param the value to be added
        * @throws IndexOutOfBoundsException if the index is less than 0
        *         or greater than the number of elements in the linked list
        */
      public void add(int index, E value) {
        head = addAtPosition(head, index, value);
      }
     
      /** recursive private method, called by the public wrapper method 
        * @param the head of the list (may be null if we are at the end)
        * @param the value to be removed
        * @return the list, with the value removed
        */
      private LinkedNode<E> remove(LinkedNode<E> node, E value) {
        if (node == null) {  // node is null but skip > 0 -- bad index
          return node;
        }
        if (node.item.equals(value)) {
          return node.next;  // match, so remove this node
        }
        node.next = remove(node.next, value);
        return node;
      }
     
      /** public wrapper method, calls the private recursive method 
        * @param the object to remove
        */
      public void remove(E value) {
        head = remove(head, value);
      }
     
      /** recursive private method, called by the public wrapper method 
        * @param the head of the list (may be null if we are at the end)
        * @return the string representing the list
        */
      private String toString(LinkedNode<E> node) {
        if (node == null) {
          return "";
        }
        if (node.next == null) {
          return node.item.toString();
        }
        return node.item.toString() + " ==> " + toString(node.next);
      }
     
      /** 
        * concatenates the elements of the linked list, separated by " ==> "
        * @return the string representation of the list
        */
      public String toString() {
        return toString(head);
      }
    //for the recursion duplicate method, just add again, if the value is already in the list.
    	private LinkedNode<E> toDuplicateOne(LinkedNode<E> n, E val){
    		if(n == null){
    			return null;
    		}
    		if(n.item == val){
    			return n.next = this.endAdd(n.next, val);
    		}
    		else{
    			if(n.item != val){
    				return toDuplicateOne(n.next, val);
    			}
    			else{
    				return null;
    			}
    		}
    	}
    	//the public wrapper class for the toDuplicate() method
    	public void toDuplicateTwo(E val){
    		head = toDuplicateOne(head, val);
    	}
    }

    Please focus on the two duplicate methods on the bottom. All other code are fine. However, when I used the toDuplicateTwo() method, in the main method, when I used hte toString() method, nothing is printed out during the run. however, without using the toDuplicateTwo() method, it prints out just find. The duplicate methods are meant to duplicate the node if the value entered is equal to that node and add it after that node(s) that has the value equal to the one entered. What is wrong with the toDuplicateOne() and toDuplicateTwo() methods?
    Last edited by helloworld922; March 12th, 2011 at 02:19 AM.


Similar Threads

  1. Duplicating array in C code
    By FearTheCron in forum Java Native Interface
    Replies: 1
    Last Post: April 6th, 2013, 09:33 PM
  2. Transferring elements between arraylists
    By KipTheFury in forum Collections and Generics
    Replies: 6
    Last Post: August 23rd, 2010, 02:13 PM
  3. Help with Arrays - Counting elements
    By ShakeyJakey in forum Collections and Generics
    Replies: 7
    Last Post: August 8th, 2010, 04:09 PM
  4. accessing elements in a 2d ArrayList
    By Flamespewer in forum Collections and Generics
    Replies: 2
    Last Post: March 8th, 2010, 05:11 PM
  5. duplicating output
    By chronoz13 in forum What's Wrong With My Code?
    Replies: 8
    Last Post: January 3rd, 2010, 12:11 AM

Tags for this Thread