8 Replies Latest reply: Oct 9, 2008 12:00 AM by 843785 RSS

    Deleting the ith node of a linked list.

    843785
      Hello all! First of all, thank you for taking the time to read my post. Hopefully my question could be answered :)

      So what I have is a linked list with a header node and a tail pointer node. The nodes have a next element and an info element. Of course the next element of a node points to the next node in the list. I have a method called isEmpty which returns true or false if the linked list is empty or not.

      So I tried to come up with a way to create a method that deletes the ith node of the list given the method's input is an integer named i.
      So the method header would be: public void delete_ith_node(int i)

      this is what I attempted:
      public void delete_ith_node(int i) {
                IntSLLNode tmp;
                if(i >= 1)
                     if(!isEmpty())
                          if(i = 1)
                               head = head.next;
                          else {
                               for (int c = 0,pred = head, tmp = head.next;  
                          tmp != null && c < i; 
                          pred = pred.next, tmp = tmp.next, c++);
                               
                               pred.next = tmp.next;
                          }                         
           }
      Is this approach efficient? And would it seem appropriate to do it this way? I haven't really had a chance to test it yet but I wanted some feedback on how I did it or if there is a better way to do so that is simplier. Thank you :)
        • 1. Re: Deleting the ith node of a linked list.
          843785
          Why waste time asking us? Test your code and you will find out if it works or not. My money is on not.
          • 2. Re: Deleting the ith node of a linked list.
            843785
            Ok well I tested it and I got a null pointer exception so I changed it a bit, but I still get this problem. So I have a list with 3 nodes. If I input 1, or 2 into the method it can delete those fine, but when I input 3 , it throws a null pointer. I stepped through it and I see why it throws it but I am not really quite sure how to solve it.

            This is the updated method, it is not that much different
            public void delete_ith_node(int i) {
                      IntSLLNode tmp = head.next;
                      IntSLLNode pred = head;
                      if(i >= 1)
                           if(!isEmpty())
                                if(i == 1)
                                     head = head.next;
                                else {
                                     for (int c =1; c<i && tmp !=null; c++)
                                     {
                                          pred = pred.next;
                                          tmp = tmp.next;
                                     }
                                     
                                     pred.next = tmp.next;
                                }                         
                 }
            • 3. Re: Deleting the ith node of a linked list.
              843785
              If you draw a bunches of boxes for your nodes on a piece of paper and some arrows from variables to boxes and boxes to boxes, then change those arrows as you trace through your code you can see what is happening. In my brief little test it appears that if I try to delete the second node then the third node is the one that actually gets deleted.

              A tip: I would change your first if statement to check that i is less than the size of the list as well. If your list only has 4 nodes not much point in trying to delete the 10th node. If you do that I imagine the isEmpty check would be unecessary.
              • 4. Re: Deleting the ith node of a linked list.
                843785
                I would have it check the size first, but I want this to work with any size list not just this one.

                So I drew out the nodes and I see what happens.
                When it goes through the for loop for the second time it sets pred to the second node in the list
                and tmp to the tail.next , but the tail.next is null so tmp becomes null.

                then after the loop it tries to do pred.next = tmp.next which throws a null pointer exception.
                I am not quite sure how to avoid this though... would I throw an extra condition in my for loop? I tried
                setting it to not just tmp != null, i set it to tmp.next != null and I thought it worked because when I typed in 3 it deleted the third node , but then
                when I put in 2, it deleted the third node again.

                So I am not really sure what's up with it. :\ I will keep trying at it but suggestions are greatly appreciated.
                • 5. Re: Deleting the ith node of a linked list.
                  843785
                  Ashgx47 wrote:
                  I would have it check the size first, but I want this to work with any size list not just this one.
                  I really don't understand this statement. Do you have an variable in the List class that keeps track of how many Nodes are in the List (ie the size)? This is what I would check i against and it will work for a List of any size.
                  So I drew out the nodes and I see what happens.
                  When it goes through the for loop for the second time it sets pred to the second node in the list
                  and tmp to the tail.next , but the tail.next is null so tmp becomes null.
                  This is the point I was making that the loop seems to be going one Node too far. I played around with it some and I discovered that what you want to do is start tmp at the head and pred to be null. Then inside the loop you advance pred by assigning it to tmp and then advance tmp as you are already. Try that.
                  • 6. Re: Deleting the ith node of a linked list.
                    843785
                    I actually got it to work in a different way. So I changed the condition in the loop. Where it said before c < i . I changed it to c < i-1 instead and it works fine now with a list of 3 nodes or a list of 6 nodes.

                    Also, the linked list class I am using doesn't have a method or counter to track how many nodes are in the list. It only has a printAll, addToHead, addToTail, deleteAll, deleteNode, the constructor, and a delete_ith_node.

                    I also tried what you suggested and that works too. Would that way be better than what I have done?
                    • 7. Re: Deleting the ith node of a linked list.
                      843785
                      Unless your instructions specifically state that your class can only have methods and variables mentioned in the specs and nothing else I would add a size variable. You will find it has many uses and can make some of your code neater.
                      • 8. Re: Deleting the ith node of a linked list.
                        843785
                        yeah I wanted to add one , but I have to stick to the given UML :(