Page 1 of 2 12 LastLast
Results 1 to 20 of 22
  1. #1
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default LinkedList question

    Hi, I need to test the methods in this code. In the Main method I need to create a list of strings of however many I want, ex 5, and then test the methods in the code provided, except the iterator one. I also need to be able to print the list, iteratively somehow? I just can't figure out how to start the main, would someone be able to give me an example of how to test one of the methods? I could probably figure the rest out then. Thanks!

    Java Code:
    package edu.nps.util;
    
    public class NPSLinkedList<E> implements NPSList<E> {
    
        public static final int NOT_FOUND = -1;
    
        private ListNode head;
    
        private ListNode tail;
    
        private int count;
    
        public static void main(String [] args){
        	
        	
        }
    
        public NPSLinkedList(  ) {
            
            clear( );
        }
    
    
        public void add(E item) {
            
            //creates a new ListNode
            ListNode newNode = new ListNode(item);
    
            if (count == 0) {
    
                head = tail = newNode;
                
            } else {
    
                tail.next = newNode;
                tail = newNode;
            }
    
            count++;
        }
    
    
        public void add(int index, E item) throws IndexOutOfBoundsException {
            
            checkInsertPosition(index);
            
            ListNode ptr = head;
    
            ListNode newNode = new ListNode(item);
    
            if (index == 0) { //adding the new node as the first node
    
                newNode.next = head;
                head = newNode;
                
            } else {
    
                for (int i = 1; i < index; i++) {
                    ptr = ptr.next;
                }
    
                newNode.next = ptr.next;
                ptr.next     = newNode;
            }
    
            //adjust tail if the new node added is
            //the last node in the list
            if (index == count) {
                tail = newNode;
            }
    
            count++;
        }
    
        
        public void clear(  ) {
            
            head = tail = null;
    
            count = 0;
        }
    
    
        public boolean contains(E item) {
            
            boolean result = true;
    
            int loc  = indexOf(item);
    
            if (loc == NOT_FOUND) {
                result = false;
            }
    
            return result;
        }
    
    
        public E get(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
            
            E item = null;
    
            ListNode ptr = head;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
    
            item = ptr.item;
    
            return item;
        }
    
    
        public int indexOf(E item) {
            
            int loc = 0;
    
            ListNode ptr = head;
    
            while (loc < count && !ptr.item.equals(item)) {
                
                loc++;
                ptr = ptr.next;
            }
    
            if (loc == count) {
                loc = NOT_FOUND;
            }
    
            return loc;
        }
    
        public NPSIterator<E> iterator( ) {
            return new MyIterator();
        }
    
        public boolean isEmpty(  ) {
            
            return (count == 0);
        }
    
    
        public E remove(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
            
            ListNode deleteNode;
            
            ListNode ptr = head;
            
            if (index == 0) { //removing the first node
            
                deleteNode = ptr;
            
                head = head.next;
                
                if (head == null) { //removed first node is the only node
                    tail = null;
                }
            
            } else {
        
                for (int i = 1; i < index; i++) {
                    ptr = ptr.next;
                }
                
                deleteNode = ptr.next;
        
                ptr.next = deleteNode.next;
                
                if (ptr.next == null) { //very last node was removed
                    tail = ptr;         //we have a new last node
                }
            }
    
            count--;
            
            return deleteNode.item;
        }
    
    
        public boolean remove(E item) {
            
            boolean result = false;
    
            ListNode ptr = head;
            ListNode trail = null;
    
            while (ptr != null && !ptr.item.equals(item)) {
    
                trail = ptr;
                ptr   = ptr.next;
            }
    
            if (ptr != null) { //found item
    
                if (trail == null) { //removing the first node
                    
                    head = head.next;
                    
                    if (head == null) { //removed first node is the only node
                        tail = null;
                    }
                    
                } else {
                    
                    trail.next = ptr.next;
                    
                    if (trail.next == null) { //very last node was removed, so
                        tail = trail;       //set tail points to a new last node
                    }
                }
                
                result = true;   
                
                count--;
            }
            
            return result;
        }
    
    
        public E set(int index, E item) {
            
            checkAccessPosition(index);
            
            ListNode ptr = head;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
            
            E old = ptr.item;
    
            ptr.item = item;
            
            return old;
        }
    
    
        public int size(  ) {
            
            return count;
        }
    
    
        /**
         * Checks the passed index position is a valid index that refers
         * to a non-empty position
         *
         * @param index  value to check for valid position
         * 
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid access positions
         */
        private void checkAccessPosition(int index) {
    
            if (size() == 0) {
                
                throw new IndexOutOfBoundsException(
                            "Index " + index + " is invalid. List is empty.");
                    
            } else if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()-1) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + (size()-1));
            }
        }
        
        
        /**
         * Checks the passed index position is a valid insertion point in 
         * the array.
         *
         * @param index   value to check for insertion position
         *
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid insertion positions
         */
        private void checkInsertPosition(int index) {
    
            if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + size());
            }
        }
    
        // Inner Class: ListNode
    
        class ListNode {
    
            private E  item;
    
            private ListNode next;
    
            public ListNode(E item) {
                this.item = item;
                this.next = null;
            }
        }
        
       ///---------- Inner Class :  MyIterator -------------////
        private class MyIterator implements NPSIterator<E> {
            
            private ListNode current;
            
            public MyIterator( ) {
                current = head;           
            }
            
            public boolean hasNext( ) {
                
                return (current != null) ;
            }
            
            public E next( ) throws NPSNoSuchElementException {
                
                if (current == null) {
                    throw new NPSNoSuchElementException();
                    
                } else {
                    
                    E item = current.item;
                    current = current.next;
                    
                    return item;
                }           
            }
        }
    }

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,610
    Rep Power
    5

    Default Re: LinkedList question

    The top or first node in a linked list is referred to as the root. It may or may not be an active node (i.e. contain data). However, it always has a link to the next node in the list. So you simply set the current node to the root and then iterate thru the list, substituting current node for the next node (however the next node is represented). This is usually done until current node is null.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    how to start the main
    Hard to see what the problem is. How many classes have you defined where the code defines an instance of a class and uses the reference to that instance to call its methods. Do the same here. Define an instance and call its methods.
    If you don't understand my response, don't ignore it, ask a question.

  4. #4
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    Quote Originally Posted by jim829 View Post
    The top or first node in a linked list is referred to as the root. It may or may not be an active node (i.e. contain data). However, it always has a link to the next node in the list. So you simply set the current node to the root and then iterate thru the list, substituting current node for the next node (however the next node is represented). This is usually done until current node is null.

    Regards,
    Jim
    How would I create the node in the main? I can't seem to find much on this.

  5. #5
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    How would I create the node in the main?
    Are you asking about the ListNode class? It helps if you are more specific when you ask questions.
    The ListNode class is an inner class of the NPSLinkedList class. Normally you do NOT create instances of the ListNode class outside of the NPSLinkedList class. Its for internal usage only.
    If you don't understand my response, don't ignore it, ask a question.

  6. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,610
    Rep Power
    5

    Default Re: LinkedList question

    Have you searched the web for linked list? There should be lots of info on it. Here is one ---> Linked list - Wikipedia, the free encyclopedia

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  7. #7
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    Quote Originally Posted by Norm View Post
    Are you asking about the ListNode class? It helps if you are more specific when you ask questions.
    The ListNode class is an inner class of the NPSLinkedList class. Normally you do NOT create instances of the ListNode class outside of the NPSLinkedList class. Its for internal usage only.
    I could be thinking totally wrong, maybe I don't have to use nodes? I basically have to test the two add methods, clear method, contains, E get, indexOf, E remove, remove, E set, checkAccessPosition, and checkInsertPosition methods from the NPSLinkedList class. I have to do it in the empty main method in the NPSLinkedList class.

    Thanks for your patience.

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    I assume that the main() method is for testing the NPSLinkedList class. It won't be used for anything else. I often add a main() method to utility classes I write that are strictly for testing the class by calling its methods. Being in the class it is testing is a way to document/demonstrate how to use the class's method.

    The testing code should be very similar to the code a user would write to use the class. In the main() method:
    Define the class and call the methods to be tested. Print out the results often to verify the results. Adding a toString() method to the node class often helps.
    If you don't understand my response, don't ignore it, ask a question.

  9. #9
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    I think I've figured some of it out, though I'm not sure how to get the public void add(int index, E item) throws IndexOutOfBoundsException method to work.

    Here's what I've done

    Java Code:
    public static void main(String [] args){
        	
        	LinkedList list = new LinkedList();
        	list.add("one");
        	list.add("two");
        	list.add("three");
        	list.add("four");
        	list.add("five");
        	list.add("six");
        	list.add("seven");
        	
        	System.out.println(list);
        	System.out.println(list.contains("one"));
        	System.out.println(list.indexOf("two"));
        	System.out.println(list.get(2));
        	
        	list.remove(3);
        	System.out.println(list);
        	
        	list.remove("three");
        	System.out.println(list);
        	
        	list.set(2, "Dog");
        	System.out.println(list);
        	
        	System.out.println(list.size());
        	
        	System.out.println(list.isEmpty());
        	
        	list.clear();    
        	
        	System.out.println(list);
        }
    This is what it prints,

    [one, two, three, four, five, six, seven]
    true
    1
    three
    [one, two, three, five, six, seven]
    [one, two, five, six, seven]
    [one, two, Dog, six, seven]
    5
    false
    []

    Thanks for your help Norm.
    Last edited by clerd; 11-18-2013 at 09:11 PM.

  10. #10
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    Visualize the problem with paper and pencil, make a design, write some code, compile, execute for testing. Iterate through those steps as necessary.
    If you don't understand my response, don't ignore it, ask a question.

  11. #11
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,798
    Rep Power
    7

    Default Re: LinkedList question

    Java Code:
    LinkedList list = new LinkedList();
    You are using the class in the Java API and not your own custom class.

  12. #12
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    Good catch.

    There isn't an import pointing to the java.util package.

    Is there a LinkedList class on the classpath when the code is compiled and executed?
    If you don't understand my response, don't ignore it, ask a question.

  13. #13
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    Quote Originally Posted by Norm View Post
    Good catch.

    There isn't an import pointing to the java.util package.

    Is there a LinkedList class on the classpath when the code is compiled and executed?
    Im not sure what you mean, here is a list of all the files that I have to work with. Though my professor made it seem like I only needed the NPSLinkedList class. I would upload them all individually but it would be quite a few posts or a huge wall of text.

    Do you guys think any of them need to be used? I can post the code from them if you think it would help.

    Here is the NPSList class but it doesn't seem to be much help.
    Java Code:
    /*
         Introduction to OOP with Java (Comprehensive Version 1st Ed), McGraw-Hill
        
         Wu/Otani
        
         Chapter 18 Sample Program: Java Interface for the List ADT
        
         File: edu/nps/util/NPSList.java
    */
    
    package edu.nps.util;
    
    /**
     * The List ADT.
     *
     */
    public interface NPSList<E> {
        
        public void add(E item);
        
        public void add(int index, E item) throws IndexOutOfBoundsException;
        
        public void clear(  );
        
        public boolean contains(E item);
        
        public E get(int index) throws IndexOutOfBoundsException;
        
        public int indexOf(E item);
        
        public NPSIterator<E> iterator();
        
        public boolean isEmpty(  );
        
        public E remove(int index) throws IndexOutOfBoundsException;
    
        public boolean remove(E item);
        
        public E set(int index, E item) throws IndexOutOfBoundsException;
        
        public int size(   );
    }
    I just found this, am I supposed to use this somehow?

    Java Code:
    /*
         Introduction to OOP with Java (Comprehensive Version 1st Ed), McGraw-Hill
        
         Wu/Otani
        
         Chapter 18 Sample Program: Linked-list implementation of the List ADT
                                    with a dummy header node
        
         File: edu/nps/util/NPSLinkedListWithHeader.java
    */
    package edu.nps.util;
    
    public class NPSLinkedListWithHeader<E> implements NPSList<E> {
        
        
        public static final int NOT_FOUND = -1;
    
        private ListNode head;
    
        private ListNode tail;
    
        private int count;
    
    
        public NPSLinkedListWithHeader(  ) {
            
            ListNode headNode = new ListNode(null);
    
            head    = headNode;
            tail    = headNode;
    
            count   = 0;
        }
    
    
        public void add(E item) {
            
            //creates a new ListNode
            ListNode newNode = new ListNode(item);
    
            tail.next = newNode;
            tail = newNode;
    
            count++;
        }
    
    
        public void add(int index, E item) throws IndexOutOfBoundsException {
            
            checkInsertPosition(index);
            
            ListNode ptr = head;
    
            ListNode newNode = new ListNode(item);
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
    
            newNode.next = ptr.next;
            ptr.next     = newNode;
    
            //adjust tail if the new node added is
            //the last node in the list
            if (index == count) {
                tail = newNode;
            }
    
            count++;
        }
    
        
        public void clear(  ) {
            
            head.next = null; //don’t remove the dummy head node
            tail = head;
    
            count = 0;
        }
    
        public boolean contains(E item) {
            
            boolean result = true;
    
            int loc  = indexOf(item);
    
            if (loc == NOT_FOUND) {
                result = false;
            }
    
            return result;
        }
        
        public E get(int index) {
            
            checkAccessPosition(index);
            
            ListNode ptr = head.next;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
    
            return ptr.item;
        }
    
        public int indexOf(E item) {
            
            int loc = 0;
    
            ListNode ptr = head.next;
    
            while ( loc < count && !ptr.item.equals( item ) ) {
                loc++;
                ptr = ptr.next;
            }
    
            if (loc == count) {
                loc = NOT_FOUND;
            }
    
            return loc;
        }
    
        public NPSIterator<E> iterator( ) {
            return new MyIterator();
        }
        
        
        public boolean isEmpty(  ) {
            
            return (count == 0);
        }
    
        public E remove(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
    
            ListNode deleteNode;
            
            ListNode trail = head;
    
            for (int i = 0; i <= index; i++) {
                trail = trail.next;
            }
           
            deleteNode = trail.next;
            trail.next = deleteNode.next;
           
            if (deleteNode.next == null) { //very last node was removed
                tail = trail;              //so set tail to the new last node
            }
    
            count--;
            
            return deleteNode.item;        
        }
    
    
        public boolean remove(E item) {
            
            boolean result = false;
    
            ListNode ptr   = head.next;
            ListNode trail = head;
    
            while (ptr != null && !ptr.item.equals(item)) {
    
                trail = ptr;
                ptr   = ptr.next;
            }
    
            if (ptr != null) {
                trail.next = ptr.next;
                
                if (trail.next == null){ //very last node was removed
                     tail = trail;       //we have a new last node
                }
                
                result = true;
                
                count--;
            }
            
            return result;
        }
        
    
        public E set( int index, E item  ) {
            
            checkAccessPosition(index);
            
            ListNode ptr = head.next;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
            
            E old = ptr.item;
    
            ptr.item = item;
            
            return old;
        }
        
        
        public int size(  ) {
            
            return count;
        }
        
        /**
         * Checks the passed index position is a valid index that refers
         * to a non-empty position
         *
         * @param index  value to check for valid position
         * 
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid access positions
         */
        private void checkAccessPosition(int index) {
    
            if (size() == 0) {
                
                throw new IndexOutOfBoundsException(
                            "Index " + index + " is invalid. List is empty.");
                    
            } else if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()-1) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + (size()-1));
            }
        }
        
        
        /**
         * Checks the passed index position is a valid insertion point in 
         * the array.
         *
         * @param index   value to check for insertion position
         *
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid insertion positions
         */
        private void checkInsertPosition(int index) {
    
            if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + size());
            }
        }   
        
    //  Inner Class: ListNode
    
        class ListNode {
    
            private E  item;
    
            private ListNode next;
    
            public ListNode(E item) {
                this.item = item;
                this.next = null;
            }
        }
        
    //  /---------- Inner Class :  MyIterator -------------////
        private class MyIterator implements NPSIterator<E> {
            
            private ListNode current;
            
            public MyIterator( ) {
                current = head.next;           
            }
            
            public boolean hasNext( ) {
                
                return (current != null);
            }
            
            public E next( ) throws NPSNoSuchElementException {
                
                if (current == null) {
                    throw new NPSNoSuchElementException();
                    
                } else {
                    
                    E item = current.item;
                    current = current.next;
                    
                    return item;
                }           
            }
        }
    }
    LinkedList question-npspic.png
    Last edited by clerd; 11-19-2013 at 12:18 AM.

  14. #14
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    That is the problem with only posting bits and pieces of code. I assumed that the main() method posted in post#11 was in the class: NPSLinkedList shown in post#1

    If that was not what you were testing, there are too many variables here to be able to say what is happening. You need to post all of the code that is being tested and post the output from when the code is execute. Isolate the code being tested by moving it to its own folder or delete other classes not involved in the tests.
    If you don't understand my response, don't ignore it, ask a question.

  15. #15
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    Quote Originally Posted by Norm View Post
    That is the problem with only posting bits and pieces of code. I assumed that the main() method posted in post#11 was in the class: NPSLinkedList shown in post#1

    If that was not what you were testing, there are too many variables here to be able to say what is happening. You need to post all of the code that is being tested and post the output from when the code is execute. Isolate the code being tested by moving it to its own folder or delete other classes not involved in the tests.
    Ahh, the main in post 11 is in the code in post 1, sorry. Here's what I've done so far.

    Java Code:
    package edu.nps.util;
    
    import java.util.*;
    
    import edu.nps.util.NPSLinkedListWithHeader.ListNode;
    
    /*
         Introduction to OOP with Java (Comprehensive Version 1st Ed), McGraw-Hill
        
         Wu/Otani
        
         Chapter 18 Sample Program: Linked-list implementation of the List ADT
        
         File: edu/nps/util/NPSLinkedList.java
    */
    
    
    public class NPSLinkedList<E> implements NPSList<E> {
    
        public static final int NOT_FOUND = -1;
    
        private ListNode head;
    
        private ListNode tail;
    
        private int count;
        
    
        public static void main(String [] args){
        	
        	LinkedList list = new LinkedList();
        	list.add("one");
        	list.add("two");
        	list.add("three");
        	list.add("four");
        	list.add("five");
        	list.add("six");
        	list.add("seven");
        	
        	System.out.println(list);
        	System.out.println(list.contains("one"));
        	System.out.println(list.indexOf("two"));
        	System.out.println(list.get(2));
        	
        	list.remove(3);
        	System.out.println(list);
        	
        	list.remove("three");
        	System.out.println(list);
        	
        	list.set(2, "Dog");
        	System.out.println(list);
        	
        	System.out.println(list.size());
        	
        	System.out.println(list.isEmpty());
        	
        	list.clear();    
        	
        	System.out.println(list);
        }
    
        public NPSLinkedList(  ) {
            
            clear( );
        }
    
    
        public void add(E item) {
            
            //creates a new ListNode
            ListNode newNode = new ListNode(item);
    
            if (count == 0) {
    
                head = tail = newNode;
                
            } else {
    
                tail.next = newNode;
                tail = newNode;
            }
    
            count++;
        }
    
    
        public void add(int index, E item) throws IndexOutOfBoundsException {
            
            checkInsertPosition(index);
            
            ListNode ptr = head;
    
            ListNode newNode = new ListNode(item);
    
            if (index == 0) { //adding the new node as the first node
    
                newNode.next = head;
                head = newNode;
                
            } else {
    
                for (int i = 1; i < index; i++) {
                    ptr = ptr.next;
                }
    
                newNode.next = ptr.next;
                ptr.next     = newNode;
            }
    
            //adjust tail if the new node added is
            //the last node in the list
            if (index == count) {
                tail = newNode;
            }
    
            count++;
        }
    
        
        public void clear(  ) {
            
            head = tail = null;
    
            count = 0;
        }
    
    
        public boolean contains(E item) {
            
            boolean result = true;
    
            int loc  = indexOf(item);
    
            if (loc == NOT_FOUND) {
                result = false;
            }
    
            return result;
        }
    
    
        public E get(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
            
            E item = null;
    
            ListNode ptr = head;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
    
            item = ptr.item;
    
            return item;
        }
    
    
        public int indexOf(E item) {
            
            int loc = 0;
    
            ListNode ptr = head;
    
            while (loc < count && !ptr.item.equals(item)) {
                
                loc++;
                ptr = ptr.next;
            }
    
            if (loc == count) {
                loc = NOT_FOUND;
            }
    
            return loc;
        }
    
        public NPSIterator<E> iterator( ) {
            return new MyIterator();
        }
    
        public boolean isEmpty(  ) {
            
            return (count == 0);
        }
    
    
        public E remove(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
            
            ListNode deleteNode;
            
            ListNode ptr = head;
            
            if (index == 0) { //removing the first node
            
                deleteNode = ptr;
            
                head = head.next;
                
                if (head == null) { //removed first node is the only node
                    tail = null;
                }
            
            } else {
        
                for (int i = 1; i < index; i++) {
                    ptr = ptr.next;
                }
                
                deleteNode = ptr.next;
        
                ptr.next = deleteNode.next;
                
                if (ptr.next == null) { //very last node was removed
                    tail = ptr;         //we have a new last node
                }
            }
    
            count--;
            
            return deleteNode.item;
        }
    
    
        public boolean remove(E item) {
            
            boolean result = false;
    
            ListNode ptr = head;
            ListNode trail = null;
    
            while (ptr != null && !ptr.item.equals(item)) {
    
                trail = ptr;
                ptr   = ptr.next;
            }
    
            if (ptr != null) { //found item
    
                if (trail == null) { //removing the first node
                    
                    head = head.next;
                    
                    if (head == null) { //removed first node is the only node
                        tail = null;
                    }
                    
                } else {
                    
                    trail.next = ptr.next;
                    
                    if (trail.next == null) { //very last node was removed, so
                        tail = trail;       //set tail points to a new last node
                    }
                }
                
                result = true;   
                
                count--;
            }
            
            return result;
        }
    
    
        public E set(int index, E item) {
            
            checkAccessPosition(index);
            
            ListNode ptr = head;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
            
            E old = ptr.item;
    
            ptr.item = item;
            
            return old;
        }
    
    
        public int size(  ) {
            
            return count;
        }
    
    
        /**
         * Checks the passed index position is a valid index that refers
         * to a non-empty position
         *
         * @param index  value to check for valid position
         * 
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid access positions
         */
        private void checkAccessPosition(int index) {
    
            if (size() == 0) {
                
                throw new IndexOutOfBoundsException(
                            "Index " + index + " is invalid. List is empty.");
                    
            } else if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()-1) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + (size()-1));
            }
        }
        
        
        /**
         * Checks the passed index position is a valid insertion point in 
         * the array.
         *
         * @param index   value to check for insertion position
         *
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid insertion positions
         */
        private void checkInsertPosition(int index) {
    
            if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + size());
            }
        }
    
        // Inner Class: ListNode
    
        class ListNode {
    
            private E  item;
    
            private ListNode next;
    
            public ListNode(E item) {
                this.item = item;
                this.next = null;
            }
        }
        
       ///---------- Inner Class :  MyIterator -------------////
        private class MyIterator implements NPSIterator<E> {
            
            private ListNode current;
            
            public MyIterator( ) {
                current = head;           
            }
            
            public boolean hasNext( ) {
                
                return (current != null) ;
            }
            
            public E next( ) throws NPSNoSuchElementException {
                
                if (current == null) {
                    throw new NPSNoSuchElementException();
                    
                } else {
                    
                    E item = current.item;
                    current = current.next;
                    
                    return item;
                }           
            }
        }
    }

  16. #16
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    As Junky said in post#9, the main() is NOT testing the class that it is in.
    You need to Change that code to test your class not the Java SE class.

    And I notice the code now has this:
    import java.util.*;

    Another problem: The code the OP is testing with is different from the code that was originally posted. Makes for a lot of wasted time.
    Last edited by Norm; 11-19-2013 at 01:34 AM.
    If you don't understand my response, don't ignore it, ask a question.

  17. #17
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    Quote Originally Posted by Norm View Post
    As Junky said in post#9, the main() is NOT testing the class that it is in.
    You need to Change that code to test your class not the Java SE class.

    And I notice the code now has this:
    import java.util.*;

    Another problem: The code the OP is testing with is different from the code that was originally posted. Makes for a lot of wasted time.
    I don't know how to change it to test the class :[

  18. #18
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    What is the name of the class you want to test? That is what should be used in the main().

    Also posted at:
    LinkedList question - Dev Shed
    LinkedList question (Beginning Java forum at JavaRanch)
    LinkedList Main Method - Java | Dream.In.Code
    If you don't understand my response, don't ignore it, ask a question.

  19. #19
    clerd is offline Member
    Join Date
    Apr 2013
    Posts
    15
    Rep Power
    0

    Default Re: LinkedList question

    Quote Originally Posted by Norm View Post
    What is the name of the class you want to test? That is what should be used in the main().

    Also posted at:
    LinkedList question - Dev Shed
    LinkedList question (Beginning Java forum at JavaRanch)
    LinkedList Main Method - Java | Dream.In.Code
    This class, public class NPSLinkedList<E> implements NPSList<E>

    I change the main to this

    Java Code:
    package edu.nps.util;
    
    import java.util.*;
    
    import edu.nps.util.NPSLinkedListWithHeader.ListNode;
    
    /*
         Introduction to OOP with Java (Comprehensive Version 1st Ed), McGraw-Hill
        
         Wu/Otani
        
         Chapter 18 Sample Program: Linked-list implementation of the List ADT
        
         File: edu/nps/util/NPSLinkedList.java
    */
    
    
    public class NPSLinkedList<E> implements NPSList<E> {
    
        public static final int NOT_FOUND = -1;
    
        private ListNode head;
    
        private ListNode tail;
    
        private int count;
        
    
        public static void main(String [] args){
        	
        	NPSLinkedList list = new NPSLinkedList();
        	list.add("one");
        	list.add("two");
        	list.add("three");
        	list.add("four");
        	list.add("five");
        	list.add("six");
        	list.add("seven");
        	
        	System.out.println(list);
        	System.out.println(list.contains("one"));
        	System.out.println(list.indexOf("two"));
        	System.out.println(list.get(2));
        	
        	list.remove(3);
        	System.out.println(list);
        	
        	list.remove("three");
        	System.out.println(list);
        	
        	list.set(2, "Dog");
        	System.out.println(list);
        	
        	System.out.println(list.size());
        	
        	System.out.println(list.isEmpty());
        	
        	list.clear();    
        	
        	System.out.println(list);
        }
    
        public NPSLinkedList(  ) {
            
            clear( );
        }
    
    
        public void add(E item) {
            
            //creates a new ListNode
            ListNode newNode = new ListNode(item);
    
            if (count == 0) {
    
                head = tail = newNode;
                
            } else {
    
                tail.next = newNode;
                tail = newNode;
            }
    
            count++;
        }
    
    
        public void add(int index, E item) throws IndexOutOfBoundsException {
            
            checkInsertPosition(index);
            
            ListNode ptr = head;
    
            ListNode newNode = new ListNode(item);
    
            if (index == 0) { //adding the new node as the first node
    
                newNode.next = head;
                head = newNode;
                
            } else {
    
                for (int i = 1; i < index; i++) {
                    ptr = ptr.next;
                }
    
                newNode.next = ptr.next;
                ptr.next     = newNode;
            }
    
            //adjust tail if the new node added is
            //the last node in the list
            if (index == count) {
                tail = newNode;
            }
    
            count++;
        }
    
        
        public void clear(  ) {
            
            head = tail = null;
    
            count = 0;
        }
    
    
        public boolean contains(E item) {
            
            boolean result = true;
    
            int loc  = indexOf(item);
    
            if (loc == NOT_FOUND) {
                result = false;
            }
    
            return result;
        }
    
    
        public E get(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
            
            E item = null;
    
            ListNode ptr = head;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
    
            item = ptr.item;
    
            return item;
        }
    
    
        public int indexOf(E item) {
            
            int loc = 0;
    
            ListNode ptr = head;
    
            while (loc < count && !ptr.item.equals(item)) {
                
                loc++;
                ptr = ptr.next;
            }
    
            if (loc == count) {
                loc = NOT_FOUND;
            }
    
            return loc;
        }
    
        public NPSIterator<E> iterator( ) {
            return new MyIterator();
        }
    
        public boolean isEmpty(  ) {
            
            return (count == 0);
        }
    
    
        public E remove(int index) throws IndexOutOfBoundsException {
            
            checkAccessPosition(index);
            
            ListNode deleteNode;
            
            ListNode ptr = head;
            
            if (index == 0) { //removing the first node
            
                deleteNode = ptr;
            
                head = head.next;
                
                if (head == null) { //removed first node is the only node
                    tail = null;
                }
            
            } else {
        
                for (int i = 1; i < index; i++) {
                    ptr = ptr.next;
                }
                
                deleteNode = ptr.next;
        
                ptr.next = deleteNode.next;
                
                if (ptr.next == null) { //very last node was removed
                    tail = ptr;         //we have a new last node
                }
            }
    
            count--;
            
            return deleteNode.item;
        }
    
    
        public boolean remove(E item) {
            
            boolean result = false;
    
            ListNode ptr = head;
            ListNode trail = null;
    
            while (ptr != null && !ptr.item.equals(item)) {
    
                trail = ptr;
                ptr   = ptr.next;
            }
    
            if (ptr != null) { //found item
    
                if (trail == null) { //removing the first node
                    
                    head = head.next;
                    
                    if (head == null) { //removed first node is the only node
                        tail = null;
                    }
                    
                } else {
                    
                    trail.next = ptr.next;
                    
                    if (trail.next == null) { //very last node was removed, so
                        tail = trail;       //set tail points to a new last node
                    }
                }
                
                result = true;   
                
                count--;
            }
            
            return result;
        }
    
    
        public E set(int index, E item) {
            
            checkAccessPosition(index);
            
            ListNode ptr = head;
    
            for (int i = 0; i < index; i++) {
                ptr = ptr.next;
            }
            
            E old = ptr.item;
    
            ptr.item = item;
            
            return old;
        }
    
    
        public int size(  ) {
            
            return count;
        }
    
    
        /**
         * Checks the passed index position is a valid index that refers
         * to a non-empty position
         *
         * @param index  value to check for valid position
         * 
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid access positions
         */
        private void checkAccessPosition(int index) {
    
            if (size() == 0) {
                
                throw new IndexOutOfBoundsException(
                            "Index " + index + " is invalid. List is empty.");
                    
            } else if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()-1) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + (size()-1));
            }
        }
        
        
        /**
         * Checks the passed index position is a valid insertion point in 
         * the array.
         *
         * @param index   value to check for insertion position
         *
         * @exception IndexOutOfBoundsException if the passed index
         *              is outside of the range of valid insertion positions
         */
        private void checkInsertPosition(int index) {
    
            if (index < 0) {
                
                throw new IndexOutOfBoundsException(
                            "Negative index of " + index + " is invalid");    
                                                                  
            } else if (index > size()) {
                
                throw new IndexOutOfBoundsException(index +  
                            " is larger than valid upper bound" + size());
            }
        }
    
        // Inner Class: ListNode
    
        class ListNode {
    
            private E  item;
    
            private ListNode next;
    
            public ListNode(E item) {
                this.item = item;
                this.next = null;
            }
        }
        
       ///---------- Inner Class :  MyIterator -------------////
        private class MyIterator implements NPSIterator<E> {
            
            private ListNode current;
            
            public MyIterator( ) {
                current = head;           
            }
            
            public boolean hasNext( ) {
                
                return (current != null) ;
            }
            
            public E next( ) throws NPSNoSuchElementException {
                
                if (current == null) {
                    throw new NPSNoSuchElementException();
                    
                } else {
                    
                    E item = current.item;
                    current = current.next;
                    
                    return item;
                }           
            }
        }
    }
    But now it prints this, I have no idea why.

    edu.nps.util.NPSLinkedList@57425f38
    true
    1
    three
    edu.nps.util.NPSLinkedList@57425f38
    edu.nps.util.NPSLinkedList@57425f38
    edu.nps.util.NPSLinkedList@57425f38
    5
    false
    edu.nps.util.NPSLinkedList@57425f38

  20. #20
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,412
    Rep Power
    25

    Default Re: LinkedList question

    edu.nps.util.NPSLinkedList@57425f38
    That is the String returned by the default (Object class) toString() method.
    You should override all the class's toString() methods to return the String you want to see when the linked list is printed.

    You should add ID Strings in all the println()s so you can easily recognize what was printed. For example:
    Java Code:
    System.out.println("an ID "+ THEVARIABLENAMEHERE);
    Change "an ID" to be the message you want to see, for example the name of the variable.
    Last edited by Norm; 11-19-2013 at 02:59 AM.
    If you don't understand my response, don't ignore it, ask a question.

Page 1 of 2 12 LastLast

Similar Threads

  1. Quick question to do with LinkedList exercise
    By SAH101 in forum New To Java
    Replies: 3
    Last Post: 08-27-2012, 06:35 PM
  2. linkedlist question
    By stuckonjava in forum New To Java
    Replies: 2
    Last Post: 05-06-2012, 04:37 AM
  3. Question about LinkedList Iterator
    By kraigballa in forum New To Java
    Replies: 7
    Last Post: 02-10-2012, 05:10 PM
  4. Java newbie question on linkedlist index search
    By Mjall in forum New To Java
    Replies: 5
    Last Post: 03-25-2011, 10:54 PM
  5. Quick LinkedList question
    By mac in forum New To Java
    Replies: 7
    Last Post: 05-31-2010, 01:27 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •