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 10 of 10

Thread: Having trouble writing insert method for Ordered LinkList.

  1. #1
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Having trouble writing insert method for Ordered LinkList.

    We are supposed to write an insert method for an ordered link list. I'm working on the method and have most of it written in my OrderedLL class. However, I can't seem to understand how to deal with case 3b. Any help is appreciated!

    public class OrderedLL extends UnorderedLinkedList{
     
    	public OrderedLL(){
    		super();
    	}
     
    	public OrderedLL(OrderedLL list){
    		super(list);
    	}
     
    public boolean search(DataElement searchItem){
     
        LinkedListNode pointer = new LinkedListNode();
        pointer = first;
        boolean foundData = false;
     
        while(pointer != null && !foundData){
        	if(pointer.info.equals(searchItem) == true || pointer.info.compareTo(searchItem) == 1){
        		foundData = true;
        	}
        	else{
        		pointer = pointer.link;
        	}
     
        }
        return foundData;	
     
        }
     
        public boolean insert(DataElement insertItem){
        	LinkedListNode pointer = new LinkedListNode();
     
        	pointer = first;
     
        	boolean inserted = false;
        	boolean smallest = false;
        	boolean largest = false;
     
        	while(pointer!=null){
        		if(pointer.info.compareTo(insertItem) == 1){
        			smallest = true;
        			break;
        		}
        		else{
        			pointer = pointer.link;
        		}
     
     
        	}
     
        	while(pointer!=null){
        		if(pointer.info.compareTo(back()) == -1){
        			largest = true;
    pointer = null;
     
        		}
        		else{
        			pointer = pointer.link;
        		}
     
     
        	}
     
     
        	pointer = first; //resets pointer back to default first
     
     
        	if(count == 0){
        	insertFirst(insertItem);
        	inserted = true;
        	}
     
        else if(count!= 0 && smallest == true){
        	insertFirst(insertItem);
        	inserted = true;
        }
     
        else if(count!= 0 && pointer.info.compareTo(insertItem) == -1){
        	if(largest == true){
        		insertLast(insertItem);
        		inserted = true;
        	}
        	else{
     
        	}
        }
     
        	}
     
     
     
     
     
     
        }
    }

     
    public class UnorderedLinkedList extends LinkedList{
     
     
    	public UnorderedLinkedList(){
    		super();
    	}
     
    	public UnorderedLinkedList(UnorderedLinkedList list){
    		super(list);
    	}
     
    	//Method to determine whether searchItem is in the list.
            //Postcondition: Returns true if searchItem is found
            //in the list; false otherwise.
        public boolean search(DataElement searchItem){
     
        LinkedListNode pointer = new LinkedListNode();
        pointer = first;
        boolean foundData = false;
     
        while(pointer != null && !foundData){
        	if(pointer.info.equals(searchItem) == true || pointer.info.compareTo(searchItem) == 1){
        		foundData = true;
        	}
        	else{
        		pointer = pointer.link;
        	}
     
        }
        return foundData;	
     
        }
     
     
        //Method to delete deleteItem from the list.
            //Postcondition: If found, the node containing
            //deleteItem is deleted from the
            //list. Also first points to the first
            //node, last points to the last
            //node of the updated list, and count
            //is decremented by 1.
        public void deleteNode(DataElement deleteItem){
     
        	if(count == 0)
        		System.out.println("The list is empty.");
        		else{
        			if(first.info.equals(deleteItem) == true)
        			{
        				if(first.link == null){
        					first = null;
        					last = null;
        					count = 0;
        				}
        				else{
        					first = first.link;
        					count--;
        					if(count == 1){
        						first.link = null;
        						last = first;
        					}
        				}
        			}
     
        			else{
        			LinkedListNode pointer = new LinkedListNode();
        			pointer = first;
     
        			while(pointer.info.equals(deleteItem) != true){
        				pointer = pointer.link;
        				pointer.link = pointer.link.link; //inception
     
        				if(pointer.link == null){
        					last = pointer;
        					count--;
        				}
     
        			}	
     
     
        			}
        			}
     
     
     
     
        }
     
    }

    public abstract class LinkedList{
     
     
    	protected class LinkedListNode{   // inner class node definition
    		protected DataElement info;
    		protected LinkedListNode link;
    	}
     
    	protected LinkedListNode first; //variable to store the address of the first node of the list
    	protected LinkedListNode last;  // variable to store the address of the last node of the list
     
    	protected int count; //variable to store the number of nodes in the list
     
    	//default constructor
    	//initializes the list to an empty state.
    	//postcondition: first = null, last = null, count = 0
     
    	public LinkedList(){
    		first = null;  //
    		last = null;  //empty list
    		count = 0;   //
    	}
     
    	public LinkedList(LinkedList list)
        {
             copy(list);
        }
     
        private void copy(LinkedList list)
        {
            LinkedListNode pointer;
            LinkedListNode newNode;
     
            if(list.first == null)
            {
                first = null;
                last = null;
                count = 0;
            }
            else
            {
                count = list.count;
                pointer = list.first;
                first = new LinkedListNode();
                first.info = pointer.info.getCopy();
                first.link = null;
                last = first;
                pointer = pointer.link;
     
                while(pointer != null)
                {
                    newNode = new LinkedListNode();
                    newNode.info = pointer.info.getCopy();
                    newNode.link = null;
                    last.link = newNode;
                    last = newNode;
                    pointer = pointer.link;
                }
            }
        }
     
     
     
    	//method to determine whether the list is empty
    	//postcondition: returns true if the list is empty; false otherwise
     
     
    	public boolean isEmptyList(){
    		return (count == 0);
    	}
     
     
     
    	//method to initialize the list to an empty state
    	//postcondition: first = null, last = null, count = 0
     
    	public void initializeList(){
    		first = null;
    		last = null;
    		count = 0;
    	}
     
     
    	//method to output the data contained in each node
     
    	public void print(){
     
    	if(count == 0){
    		System.out.println("Cannot print an empty list.");
    	}
    	else{
     
    			LinkedListNode pointer = new LinkedListNode();
    		pointer = first;
    		while(pointer != null){
     
     
    		System.out.println(pointer.info.toString());
    		pointer=pointer.link;
    		}
     
    	}
     
    	}
     
     
    	//method to return the number of nodes in the list.
    	//postcondition: the value of count is returned
     
    	public int length(){
    		return count;
    	}
     
    	//method to return a reference of the object 
    	//containing the data of the first node of the list
    	//precondition: the list must exist and must not be empty.
    	//postcondition: the reference of the object that contains
    	//the info of the first node is returned
     
    	public DataElement front(){
     
     
    				return first.info.getCopy();
    		}
     
     
    	//Method to return a reference of object containing
            //the data of the last node of the list.
            //Precondition: The list must exist and must not be empty.
            //Postcondition: The reference of the object that
            //contains the info of the last node
            //is returned.
        public DataElement back(){
        	return last.info.getCopy();
        }
     
        //Method to insert newItem in the list.
            //Postcondition: first points to the new list
            //               and newItem is inserted at the
            //               beginning of the list. Also,
            //               last points to the last node and
            //               count is incremented by 1.
        public void insertFirst(DataElement newItem){
        	LinkedListNode newNode = new LinkedListNode();
        newNode.info = newItem.getCopy();
        newNode.link = first;
        first = newNode;
     
        if(last == null){
     
        last = newNode;
        count++;
        }
     
     
        }
     
        //Method to insert newItem at the end of the list.
            //Postcondition: first points to the new list and
            //newItem is inserted at the end
            //of the list. Also, last points to
            //the last node and
            //count is incremented by 1.
        public void insertLast(DataElement newItem){
     
     LinkedListNode newNode = new LinkedListNode();   
        	newNode.info = newItem.getCopy();
        	newNode.link = null;
        	if(first == null){
        		first = newNode;
        		last = newNode;
        	}
        	else{
     
        	last.link = newNode;
        	last = newNode;
        	count++;
        	}
        }
     
        		public void deleteFront()
        {
            if(first.link != null) 
            {
                first = first.link;
                count--;
            }
            else
            {
                first = null;
                last = null;
                count = 0;
            }
        }
     
        public void deleteLast()
        {
            LinkedListNode pointer = first;
            if(pointer.link == null)
            {
                first = null;
                last = null;
                count = 0;
            }
            else 
            {
                while(pointer.link.link != null) pointer = pointer.link;
                pointer.link = null;
                last = pointer;
                count--;
            }
        }
     
         public void splitMid(LinkedList list)
        {
            int stopPoint = list.count / 2;
            LinkedListNode pointer = null;
            pointer = list.first.link;
            for(int i = 0; i < stopPoint; i++)
            {
                pointer = pointer.link;
            }
            LinkedListNode secondFirst = pointer.link;
     
            pointer.link.link = null;
     
        }
     
     
            public double average(){
     
     
        			double sum=0;
        			LinkedListNode pointer = new LinkedListNode();
     
     
        			pointer = first;
     
        			while(first != null){
     
        		pointer = first;
        			IntElement temp = (IntElement)pointer.info.getCopy();
     
        			sum = sum + temp.getNum();
        			first = pointer.link; 
     
     
        			}
     
        		double average = (sum/59.0);
        		return average;
     
        		}
     
        		public double stdDev(double avg){
        			double stdAvg = avg;
        			double variance = 0;
        			LinkedListNode pointer = new LinkedListNode();
     
        			while(first!= null){
     
        				pointer = first;
        				IntElement temp = (IntElement)pointer.info.getCopy();
        				variance = (variance + ((temp.getNum() - stdAvg)*(temp.getNum() - stdAvg)));
        				first = pointer.link;
     
     
        				}
     
        			return (Math.sqrt(variance/59));
        		}
     
     
        //Method to determine whether searchItem is in the list.
        //Postcondition: Returns true if searchItem is found
        //in the list; false otherwise.
        public abstract boolean search(DataElement searchItem);	
     
    		//Method to delete deleteItem from the list.
            //Postcondition: If found, the node containing
            //deleteItem is deleted from the
            //list. Also first points to the first
            //node, last points to the last
            //node of the updated list, and count
            //is decremented by 1.
        public abstract void deleteNode(DataElement deleteItem);
     
     
     
     
      	}

    This is what the powerpoint says...

    Approach
     
    We first find the place where the new item is
    supposed to go and then insert it in the list.
    We use the search algorithm go past the item
    value to be inserted. We need a current pointer
    to point to the current node and a previous
    pointer that points to the node just before
    current. 
    We have three cases to consider:
     
     
    Case 1
     
    The list is initially empty.
     
    The node containing the new item is the only
    item in the list and thus the first in the list.
     
    Use insertFirst method.
     
     
    Case 2
     
    The list is not empty and the new item is
    smaller than the smallest item in the list.
    The new item goes at the beginning of the list.
     
    Use insertFirst method.
     
     
    Case 3
     
    The list is not empty and the item to be
    inserted is larger than the first item in the list.
    The item is to be inserted somewhere in the list.
     
    We need to consider two sub cases.
     
    Case 3a
     
    New item is larger than all items in the list.
    Then new item is inserted at end of list.
    Current pointer is null and previous pointer
    point to last node.  Insert after previous,  or
    use insertLast method. 
     
    Case 3b
     
    New item is to be inserted somewhere in the
    middle of the list.  That is insert new item
    between previous and current pointers.


    I feel like I've gotten most of it, but I don't understand how to deal with case 3b?
    Last edited by orbin; October 25th, 2012 at 03:30 PM.


  2. #2
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    I feel like I've gotten most of it, but I don't understand how to deal with case 3b?

    If you don't understand by reading the instructions, try to compare the rules to a test case.

    Case 1: Insert 'D' into an empty list. Easy, D goes on the front of the empty list and becomes the only item in the list.

    Case 2: Insert 'D' into a list of elements greater than 'D' , for example {'E' 'F' 'G' 'H'}. D again becomes the first, just this time not the only item in the list. What extra work is required for this step compared to case 1?

    Case 3:
    a: Insert 'D' into a list of elements smaller than 'D', for example {'A' 'B' 'C'}. This time D becomes the last element but is really like the opposite of case 2 if you think about it.

    b: Insert 'D' into a list of elements that has items smaller than 'D" and greater than 'D' also, for example {'A' 'B' 'C' 'E' 'F' 'G' 'H'}. Now you have to find the point in the list where D belongs. Consider, after the point where 'D' belongs is discovered, the list would be 2 lists so to speak, a left and a right half. D to the right half is case 2, and D to the left half is case 3a.

  3. #3
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    Quote Originally Posted by jps View Post
    I feel like I've gotten most of it, but I don't understand how to deal with case 3b?

    If you don't understand by reading the instructions, try to compare the rules to a test case.

    Case 1: Insert 'D' into an empty list. Easy, D goes on the front of the empty list and becomes the only item in the list.

    Case 2: Insert 'D' into a list of elements greater than 'D' , for example {'E' 'F' 'G' 'H'}. D again becomes the first, just this time not the only item in the list. What extra work is required for this step compared to case 1?

    Case 3:
    a: Insert 'D' into a list of elements smaller than 'D', for example {'A' 'B' 'C'}. This time D becomes the last element but is really like the opposite of case 2 if you think about it.

    b: Insert 'D' into a list of elements that has items smaller than 'D" and greater than 'D' also, for example {'A' 'B' 'C' 'E' 'F' 'G' 'H'}. Now you have to find the point in the list where D belongs. Consider, after the point where 'D' belongs is discovered, the list would be 2 lists so to speak, a left and a right half. D to the right half is case 2, and D to the left half is case 3a.

    I tried to read it like that but I think I'm over complicating my program. I updated my code, but still stuck on 3b case.

        public boolean insert(DataElement insertItem){
        	LinkedListNode pointer = new LinkedListNode();
        	boolean inserted = false;
        	pointer = first;
     
     
        if(count == 0){
        	insertFirst(insertItem);
        	inserted = true;
        }
        if(count!=0 && first.info.compareTo(insertItem) == 1 ){
        	insertFirst(insertItem);
        	inserted = true;
        }
     
        if(count!= 0 && first.info.compareTo(insertItem) == -1){
     
        		if(last.info.compareTo(insertItem) == -1){
        			insertLast(insertItem);
        			inserted = true;
        		}
        		else{
     
        		}
     
       }
     
        	}

  4. #4
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    I updated my code, but still stuck on 3b case.
    Does it compile? Does it run? Does it appear to work correctly?

    If you are stuck on 3b, I see 3b as several parts. About 3 major chunks anyway. First is to figure out where in the list the new element will go. Have you tried getting just this to work and do a println on the element to be previous to the new, and the element to be after the new? Does it work that far? If so where are you stuck?

  5. #5
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    Thank you for your help. It helped me rethink the problem. I managed to figure out a lot since the other day. However, now I'm having trouble insert a UNIQUE number into a list. I made two methods, one to see if the number exists in the list, and the other to insert the Dataelement if it is not found. (seqSearch and insertUnique are the new methods.)

    public class OrderedLL extends UnorderedLinkedList
    {
     
        public OrderedLL()
        {
            super();
        }
     
        public OrderedLL(OrderedLL list)
        {
            super(list);
        }
     
        public boolean search(DataElement searchItem)
        {
     
            LinkedListNode pointer = new LinkedListNode();
            pointer = first;
            boolean foundData = false;
     
            while (pointer != null && !foundData)
            {
                if (pointer.info.equals(searchItem) == true ||
                    pointer.info.compareTo(searchItem) == 1)
                {
                    foundData = true;
                }
                else
                {
                    pointer = pointer.link;
                }
     
            }
            return foundData;
     
        }
     
        public boolean insert(DataElement insertItem)
        {
            LinkedListNode pointer = new LinkedListNode();
            boolean inserted = false;
            pointer = first;
     
     
            if (count == 0)
            {
                //case 1
                insertFirst(insertItem);
                inserted = true;
            }
            else if (count != 0 && first.info.compareTo(insertItem) == 1)
            {
                //case 2
                insertFirst(insertItem);
                inserted = true;
            }
     
            else if (count != 0 && first.info.compareTo(insertItem) ==  - 1)
            {
                //case 3
     
                if (last.info.compareTo(insertItem) ==  - 1)
                {
                    //case3a
                    insertLast(insertItem);
                    inserted = true;
                }
                else if (last.info.compareTo(insertItem) == 1 &&
                    first.info.compareTo(insertItem) ==  - 1)
                {
                    //case 3b
                    LinkedListNode firstPointer = first;
                    LinkedListNode secondPointer = first.link;
     
                    while (secondPointer.info.compareTo(insertItem) ==  - 1)
                    {
                        firstPointer = secondPointer;
                        secondPointer = secondPointer.link;
     
                    }
     
                    LinkedListNode newNode = new LinkedListNode();
                    newNode.info = insertItem;
                    newNode.link = secondPointer;
                    firstPointer.link = newNode;
                    inserted = true;
                }
     
            }
            return inserted;
        }
     
     
        //Method to delete deleteItem from the list.
        //Postcondition: If found, the node containing
        //deleteItem is deleted from the
        //list. Also first points to the first
        //node, last points to the last
        //node of the updated list, and count
        //is decremented by 1.
        public void deleteNode(DataElement deleteItem)
        {
     
            if (count == 0)
                System.out.println("The list is empty.");
            else
            {
                if (first.info.equals(deleteItem) == true)
                {
                    if (first.link == null)
                    {
                        first = null;
                        last = null;
                        count = 0;
                    }
                    else
                    {
                        first = first.link;
                        count--;
                        if (count == 1)
                        {
                            first.link = null;
                            last = first;
                        }
                    }
                }
     
                else
                {
                    LinkedListNode pointer = new LinkedListNode();
                    pointer = first;
     
                    while (pointer.info.equals(deleteItem) != true)
                    {
                        pointer = pointer.link;
                        pointer.link = pointer.link.link; //inception
     
                        if (pointer.link == null)
                        {
                            last = pointer;
                            count--;
                        }
     
                    }
     
     
                }
            }
     
        }
     
       public OrderedLL mergeLists(OrderedLL list1, OrderedLL list2){
       	OrderedLL newList = new OrderedLL();
     
       	LinkedListNode temp1 = new LinkedListNode();
       	LinkedListNode temp2 = new LinkedListNode();
     
     
       	temp1.info = list1.first.info;
       	temp1.link = list1.first.link;
     
       	while(temp1 != null){
     
       		newList.insert(temp1.info);
       		temp1 = temp1.link;
       	}
     
       	temp2.info = list2.first.info;
       	temp2.link = list2.first.link;
     
       	while(temp2 != null){
       		newList.insert(temp2.info);
       		temp2 = temp2.link;
       	}
     
       	return newList;
       }
     
           public int seqSearch(DataElement searchItem){
     
     
        	if (count == 0){
        		return -1;
        	}
        	else{
        	LinkedListNode pointer = new LinkedListNode();
     
        	pointer = first;
     
     
        	while(pointer != null){
        	 if(pointer.info.equals(searchItem)){
        	 	return 1; //number found
     
        	 									}
     
    							  }
        	}
        		return -1; //not found
        	}
     
        	public boolean insertUnique(DataElement insertItem){
        		boolean inserted = false;
     
        		int num = seqSearch(insertItem);
     
        		if(num == 1){
        		 return inserted;
        		}
        		else{
        			inserted = true;
        			insert(insertItem);
        				return inserted;
        		}
     
        		}
     
        	}

    import java.util.Random;
     
    public class TestOrderedLinkedList{
     
    	public static void main(String[] args){
    		OrderedLL list = new OrderedLL();  //list 1
    		OrderedLL list2 = new OrderedLL();  //list 2
    		OrderedLL mList = new OrderedLL();  //merged list
    		boolean inserted = false;
     
    		Random num = new Random();
     
     
     
    for(int i =0; i <=9; i++){
     
    	int randomNumber = num.nextInt(100)+1;
    		inserted = list.insertUnique(new IntElement(randomNumber));
    		System.out.println(inserted);
    }
     
    System.out.println("List 1: ");
    list.print();
     
    for(int i =0; i <=9; i++){
     
    	int randomNumber = num.nextInt(100)+1;
    		list2.insertUnique(new IntElement(randomNumber));
     
    }
     
    System.out.println("List 2: ");
    list2.print();
     
     
    mList = mList.mergeLists(list, list2);
     
    System.out.println("Merged List: ");
     
    mList.print();
     
     
     
    }
    }


    However, I'm not sure why it's not working. When I try to run the test, it returns back a true that it inserted the first number, but then it stalls and never finishes running. Why is it only putting in the first number and stalling? I tried to do a couple println's but I can't find anything wrong.

  6. #6
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    Why is it only putting in the first number and stalling?
    Stalling.. could be a sign of a loop never ending and doing nothing each cycle. Throw in some printlns and try to determine what is going on as the code runs.

  7. #7
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    Quote Originally Posted by jps View Post
    Stalling.. could be a sign of a loop never ending and doing nothing each cycle. Throw in some printlns and try to determine what is going on as the code runs.
    I noticed after a bit of tinkering with the code that it always gets a true on the first insertUnique run through, but the second time it runs through it stalls.

        public int seqSearch(DataElement searchItem){
     
        	System.out.println("makes it to seqSearch method");
        	System.out.println("Count: " + count);
        	if (count == 0){
        		return -1;
        	}
        	else{
        	LinkedListNode pointer = new LinkedListNode();
        	System.out.println("Makes it to else condition.");
        	pointer = first;
        	System.out.println("First: " + first + "   pointer: " + pointer);
     
        	while(pointer != null){
        	 if(pointer.info.equals(searchItem) == true){
        	 	return 1; //number found
     
        	 									}
     
    							  }
        	}
        		return -1; //not found
        	}
     
        	public boolean insertUnique(DataElement insertItem){
        		boolean inserted = false;
        		System.out.println("Before insertion: "  + inserted);
     
        		int num = seqSearch(insertItem);
        		System.out.println(num);
     
        		if(num == 1){
        		 return inserted;
        		}
        		else{
        			inserted = true;
        			insert(insertItem);
        				return inserted;
        		}
     
        		}

    This is the output that I get after using some printlns.

    --------------------Configuration: <Default>--------------------
    Before insertion: false
    makes it to seqSearch method
    Count: 0
    -1
    true
    Before insertion: false
    makes it to seqSearch method
    Count: 1
    Makes it to else condition.
    First: LinkedList$LinkedListNode@1833955   pointer: LinkedList$LinkedListNode@1833955

    It obviously returns a -1 which means the number is not found within the list, but I notice on the second run through it stalls in the seqSearch method.
    Last edited by orbin; October 27th, 2012 at 07:24 PM.

  8. #8
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    I solved the problem by adding an else method and it does work now. However, I keep running into more problems! I need to generate two lists of 10 DataElements each, and none of the numbers can be duplicates. I use a for loop i =0; i<=9; i++ to generate 10 numbers, but the problem I'm having is that it omits numbers that duplicate so I'm left with 8 numbers instead of the 10 unique ones that I want. Then to go a step further, I need to merge those two lists into one list, which I've already written a method for, and still have no duplicates exist. How should i go about editing the insertUnique method, so that it always keeps trying until it successfully inserts a number?

  9. #9
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    Start with 0 elements in some set.
    while the number of elements in the set is less than the number of elements I want the set to have {
    ---add another element to the set;
    }

  10. #10
    Member
    Join Date
    Jun 2012
    Posts
    59
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Having trouble writing insert method for Ordered LinkList.

    Quote Originally Posted by jps View Post
    Start with 0 elements in some set.
    while the number of elements in the set is less than the number of elements I want the set to have {
    ---add another element to the set;
    }
    I managed to fix the problem. I just had it keep generating a random number between 1 and 100 until it got a successful insertion. However, on the merged list, if it found a duplicate I'd just have it randomly generate a unique number to put in instead.

    import java.util.Random;
     
    public class OrderedLL extends UnorderedLinkedList
    {
     
        public OrderedLL()
        {
            super();
        }
     
        public OrderedLL(OrderedLL list)
        {
            super(list);
        }
     
        public boolean search(DataElement searchItem)
        {
     
            LinkedListNode pointer = new LinkedListNode();
            pointer = first;
            boolean foundData = false;
     
            while (pointer != null && !foundData)
            {
                if (pointer.info.equals(searchItem) == true ||
                    pointer.info.compareTo(searchItem) == 1)
                {
                    foundData = true;
                }
                else
                {
                    pointer = pointer.link;
                }
     
            }
            return foundData;
     
        }
     
        public boolean insert(DataElement insertItem)
        {
            LinkedListNode pointer = new LinkedListNode();
            boolean inserted = false;
            pointer = first;
     
     
            if (count == 0)
            {
                //case 1
                insertFirst(insertItem);
                inserted = true;
            }
            else if (count != 0 && first.info.compareTo(insertItem) == 1)
            {
                //case 2
                insertFirst(insertItem);
                inserted = true;
            }
     
            else if (count != 0 && first.info.compareTo(insertItem) ==  - 1)
            {
                //case 3
     
                if (last.info.compareTo(insertItem) ==  - 1)
                {
                    //case3a
                    insertLast(insertItem);
                    inserted = true;
                }
                else if (last.info.compareTo(insertItem) == 1 &&
                    first.info.compareTo(insertItem) ==  - 1)
                {
                    //case 3b
                    LinkedListNode firstPointer = first;
                    LinkedListNode secondPointer = first.link;
     
                    while (secondPointer.info.compareTo(insertItem) ==  - 1)
                    {
                        firstPointer = secondPointer;
                        secondPointer = secondPointer.link;
     
                    }
     
                    LinkedListNode newNode = new LinkedListNode();
                    newNode.info = insertItem;
                    newNode.link = secondPointer;
                    firstPointer.link = newNode;
                    inserted = true;
                }
     
            }
            return inserted;
        }
     
     
        //Method to delete deleteItem from the list.
        //Postcondition: If found, the node containing
        //deleteItem is deleted from the
        //list. Also first points to the first
        //node, last points to the last
        //node of the updated list, and count
        //is decremented by 1.
        public void deleteNode(DataElement deleteItem)
        {
     
            if (count == 0)
                System.out.println("The list is empty.");
            else
            {
                if (first.info.equals(deleteItem) == true)
                {
                    if (first.link == null)
                    {
                        first = null;
                        last = null;
                        count = 0;
                    }
                    else
                    {
                        first = first.link;
                        count--;
                        if (count == 1)
                        {
                            first.link = null;
                            last = first;
                        }
                    }
                }
     
                else
                {
                    LinkedListNode pointer = new LinkedListNode();
                    pointer = first;
     
                    while (pointer.info.equals(deleteItem) != true)
                    {
                        pointer = pointer.link;
                        pointer.link = pointer.link.link; //inception
     
                        if (pointer.link == null)
                        {
                            last = pointer;
                            count--;
                        }
     
                    }
     
     
                }
            }
     
        }
     
       public OrderedLL mergeLists(OrderedLL list1, OrderedLL list2){
       	OrderedLL newList = new OrderedLL();
     
       	LinkedListNode temp1 = new LinkedListNode();
       	LinkedListNode temp2 = new LinkedListNode();
     
     
       	temp1.info = list1.first.info;
       	temp1.link = list1.first.link;
     
       	while(temp1 != null){
     
       		newList.insertUnique(temp1.info);
       		temp1 = temp1.link;
       	}
     
       	temp2.info = list2.first.info;
       	temp2.link = list2.first.link;
     
       	while(temp2 != null){
       		newList.insertUnique(temp2.info);
       		temp2 = temp2.link;
       	}
     
       	return newList;
       }
     
           public int seqSearch(DataElement searchItem){
     
     
        	if (count == 0){
        		return -1;
        	}
        	else{
        	LinkedListNode pointer = new LinkedListNode();
     
        	pointer = first;
     
     
        	while(pointer != null){
        	 if(pointer.info.equals(searchItem) == true){
        	 	return 1; //number found
     
        	 									}
     
        	 									else{
        	 										pointer = pointer.link;
        	 									}
     
    							  }
        	}
        		return -1; //not found
        	}
     
        	public boolean insertUnique(DataElement insertItem){
        		boolean inserted = false;
        		Random numb = new Random();
        		int randomNum = 0;
     
        		int num = seqSearch(insertItem);
        		IntElement temp = (IntElement)insertItem.getCopy();
     
        		 while(num == 1){
     
        		 	//keeps trying to add a number until a unique one is found
        		 	randomNum = numb.nextInt(100)+1;
        		 	temp.setNum(randomNum);
        		 	num = seqSearch(temp);
        		 }
     
     
        			inserted = true;
        			insert(temp);
        				return inserted;
     
     
     
        		}
     
        		public boolean clearList(){
        			LinkedListNode pointer = first;
        			while(pointer.link != null){
        			pointer.info = null;
        			pointer = pointer.link;
     
     
        			}
     
        		}
     
        	}

    I have one more issue and then I am done with the assignment. It's more of a question though. It wants me to generate a clearList method that recovers all memory.


    Does that mean I can just set the first and last to null and set the count to 0 and it's cleared? The memory part is whats throwing me off. Thanks again for your continued help!

Similar Threads

  1. Trouble with writing/reading array to/from file
    By MaximusPrime in forum What's Wrong With My Code?
    Replies: 2
    Last Post: March 4th, 2012, 08:41 PM
  2. Linklist Question
    By NeedzABetterSN in forum Java Theory & Questions
    Replies: 2
    Last Post: December 18th, 2010, 08:11 PM
  3. Trouble with Binary Search on Insert Method
    By EricSt in forum Algorithms & Recursion
    Replies: 1
    Last Post: February 17th, 2010, 10:34 PM
  4. Trouble writing some code...help?
    By bChEos in forum File I/O & Other I/O Streams
    Replies: 1
    Last Post: February 7th, 2010, 08:54 PM
  5. Having trouble insert/sorting array values w/ binary searching.
    By bh-chobo in forum Collections and Generics
    Replies: 4
    Last Post: October 8th, 2009, 02:38 AM