10 Replies Latest reply: Sep 11, 2007 7:19 AM by 807600 RSS

    Problems with add() and remove() in my Doubly Circular Linkedlist code

    807600
      I have been working on this code for 6 hours and some how it won't remove correctly when the list has 0,2,4 elements.

      It will attempt to remove element at index 0 but actually removed 4. I thought it was the reference problem at first, so i did something to my add() method so that it reference head to tail, tail to head. But still, the code doesn't work.

      The problem seem to be how to remove the element at index 0. If anyone has any ideas, please let me know.


      Add:
      public void add(T item) {
                if (isEmpty()){     
                     Node<T> n = new Node<T> (null,item,null);     
                     head = n;
                     tail = n;
                     head.setNext(tail);
                     head.setPrev(tail);
                     tail.setNext(head);
                     tail.setPrev(head);
                }
                else{
                     Node<T> n = new Node<T> (tail,item,head);
                     n.getPrev().setNext(n);
                     tail=n;
                     head.setPrev(tail);
                     tail.setNext(head);
                }
                size++;
           }
      Remove:
      public T removeAt(int index) {
                Node<T> target = getNode(index);
                //System.out.println(target.getValue());
                if (index>size()||index<0){
                     throw new IllegalArgumentException
                          ("Can't remove anything out of the list.");
                }
                
                if (isEmpty()){
                     throw new NoSuchElementException
                          ("Can't remove from empty list.");
                }else {
                     
                     if (target.getNext().equals(target.getPrev())){
                          target.getNext().setNext(null);
                          target.getPrev().setPrev(null);
                     }else{
                     System.out.println("target prev: "+ target.getPrev().getValue());
                     System.out.println("target: " + target.getValue());
                     System.out.println("target next: "+ target.getNext().getValue());
                     target.getPrev().setNext(target.getNext());
                     target.getNext().setPrev(target.getPrev());
                     }
                     size--;
                }          
                return target.getValue();
           }
        • 1. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
          807600
          by the way, add() has to add item to the end of the list.
          • 2. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
            807600
            What happens if you call removeAt() with index == size? If size > 0? (If index == size == 0, I suspect isEmpty() will be true and an exception thrown?)

            In this line:
            if (target.getNext().equals(target.getPrev())){
            What does your equals() method return? I suspect the condition will be true if there are 1 or 2 nodes in the list. Do you want to do the same in those two cases?

            What's in your getNode() method? How will it behave under abnormal conditions (index < 0 or index >= size)?
            • 3. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
              807600
              Here's how I did the getNode
              /**
                    * Since getAt() and removeAt() will share similar function, they all need the node at certain index
                    * it is more convienient to create one to get the node at a certain index
                    * @param index the index to find
                    * @return the node of type T at the index
                    */
                   public Node<T> getNode (int index){
                        Node<T> current=head;          
                        int counter=0;
                        
                        /**  if index is out of bound, throw exception. */
                        if (index>size()||index==size()||index<0){
                             throw new IllegalArgumentException
                                  ("Can't get anything beyond the bound of the list.");
                        }
                        
                        /**  iterate current down the list, catch the target index */
                        while (current!=null){//if current == null, we know we hit the end of list     
                             if (counter==index){ //if we find our target 
                                  return current;
                                  //break;
                             }
                             current=current.getNext();
                             counter++;
                        }
                        return current;
                   }
              • 4. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                807600
                Here's how I did the getNode
                Looks fine. That answered one or two of my many questions.

                index>size()||index==size() can be written as just index >= size() (assuming size() does not have side effects).

                I believe the exceptions in removeAt() will never be thrown since getNode() will throw an exception first. No harm done, though.

                Message was edited by:
                OleVV
                • 5. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                  807600
                  if (target.getNext().equals(target.getPrev())){
                  this equals() is a boolean method, used to compare any two objects. If they're reference same object, it will return true, if not, return false.

                  This can be changed to if (size()==2) since such circumstances only happen when there are only 2 nodes left.

                  isEmpty() is tested to be working properly.

                  I have correct printout for the Target, Target Prev and Target Next, but the program just doesn't remove properly when I have to remove index 0 element.

                  I also wonder when size()==2, how can i set target.getNext() to point to null?
                  It seems to trigger NullPointerException.
                  • 6. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                    807600
                    Is your list circular or not? Or more precisely, is it meant to be?

                    The forum thread title suggests it is.

                    The way I read your code, when you insert one node into an empty list, you make it refer to itself both ways, making a circular list. On the other hand, removing one element from a list of two elements, you set the remaining element to refer to null both ways, so the list is no longer circular.

                    Or am I mistaken?
                    • 7. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                      807600
                      public T removeAt(int index) {
                                Node<T> target = getNode(index);
                                if (isEmpty()){
                                     throw new NoSuchElementException
                                          ("Can't remove from empty list.");
                                }else if (size()==1){
                                     head=tail=null;
                                     size=0;     
                                     return null;
                                }else{
                                          System.out.println("target prev: "+ target.getPrev().getValue());
                                          System.out.println("target: " + target.getValue());
                                          System.out.println("target next: "+ target.getNext().getValue());
                                          target.getNext().setPrev(target.getPrev());
                                          target.getPrev().setNext(target.getNext());
                                }
                                     size--;          
                                return target.getValue();
                           }
                      Now i think i have to add two conditionals, when size == 2. 1) Remove when the target is at tail, not head. 2) Remove when the target is at head, not tail.
                      • 8. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                        807600
                        Looks better. :-)

                        Still one comment: When size() is 1, you first do inside the if/else:
                        size=0;
                        Next, after the last else:
                        size--;
                        Won't this leave size being -1? It's not what you intend, is it?

                        Is your original problem the same now?
                        • 9. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                          807600
                          size won't ever reach -1 since it won't -1 if isEmpty() returns true in getNode().
                          The procedure is, if I can get the node, i will try to remove it, if i can't even get it, nothing will run in removeAt (idx) except the first line.
                          public T removeAt(int index) {
                                    Node<T> target = getNode(index);
                                    
                                    if (size()==1){
                                         head=tail=null;
                                         size=0;     
                                         return null;
                                    }else if (size()==2){
                                         if (index==0)                      // first but not the last.
                                              target.getNext().setPrev(null);
                                              target.getNext().setNext(null);
                                         if (index==1)                   // last but not the first.
                                             target.getPrev().setPrev(null);
                                              target.getPrev().setNext(null);
                                    }else{
                                              System.out.println("target prev: "+ target.getPrev().getValue());
                                              System.out.println("target: " + target.getValue());
                                              System.out.println("target next: "+ target.getNext().getValue());
                                              target.getNext().setPrev(target.getPrev());
                                              target.getPrev().setNext(target.getNext());
                                    }
                                         size--;          
                                    return target.getValue();
                               }
                          • 10. Re: Problems with add() and remove() in my Doubly Circular Linkedlist code
                            807600
                            My bad. I failed to read the return null; that comes after size=0;. You're right, you're fine with the size.