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

Thread: Remove at index in singly linked list?

  1. #1
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Remove at index in singly linked list?

    Okay so I've created a public E remove(int index) method, it works fine at removing. However, when it removes the node at index size-1, and then I try to add nodes at the end of the list afterwards, it increases the index but DOES NOT add the nodes. I think this is because I didn't made a condition if the index chosen is the tail then to adjust the tail. Here is my method without the tail condition:

    		 public E remove(int index) {
    			 Node<E> previous = null;
    			 Node<E> current = head;
    		    	if ( index < 0 || index >= size)
    					throw new IndexOutOfBoundsException();
    				if (index == 0){
    					head=head.next;
    				}
    				//remove item somewhere in the middle
    				else {
    					for(int i = 0; i < index; i++) {
    						previous = current;
    						current = current.next;
    					}
    					previous.next = current.next;
    				}
    		    	size--;
    		    	return current.data;
    		    }

    So then I tried to add this condition in if the index chosen is equaled to the tail (size-1).

    if(index == size-1) {
       for(int i=0; i<size-1; i++) {
           previous=current;
           current=current.next
         }
    previous.next=null;
    }

    But it gives me a null pointer exception! How can I fix this condition so that my code works properly and I am able to add new nodes to the end of the list after deleting and adjusting the tail?


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Remove at index in singly linked list?

    Can you make a small, complete program that compiles, executes and shows the problem? Be sure to include all the necessary input data for testing.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Remove at index in singly linked list?

    Here is what I got
     
    import java.util.Iterator;
     
    public class SinglyLinkedList<E> {
     
     private static class Node<E> {
     
         private E data;
     
         private Node<E> next = null;
     
         public Node(E data, Node<E> next) {
             this.data = data;
             this.next = next;
         }
         public Node(E data) {
             this(data, null);
         }
     }
     
     
     private Node<E> head = null;
     
     
     private Node<E> tail = null;
     
     private int size = 0;
     
     
     public void addFirst(E item) {
    		if (head == null)
    			head = tail = new Node<E>(item, null);
    	    else
    	        head = new Node<E>(item, head);
         size++;
     }
     
     
    	public void addLast(E item) {
    	   if (head == null)
    		  head = tail = new Node<E>(item, null);
    	   else {
    		  tail.next = new Node<E>(item, null);
    		  tail = tail.next;
        }
    	   size++;
     }
     
     
    	public boolean add(E item) {
    		addLast(item);
    		return true;
     }
     
    	public void add(int index, E item) {
    		if ( (index < 0) || (index > size))
    		  throw new IndexOutOfBoundsException();
    		if (index == 0) {
    			addFirst(item);
    			return;
    	    }
    		if (index == size) {
    			addLast(item);
    			return;
    	    }
     
    	    Node <E> temp = getNode(index -1);
    	    // temp points to the Node at position (index-1)
    	    Node <E> current = new Node <E>(item, temp.next);
    	    temp.next = current;
    	    size++;
     }
    		 public E remove(int index) {
    			 Node<E> previous = null;
    			 Node<E> current = head;
    		    	if ( index < 0 || index >= size)
    					throw new IndexOutOfBoundsException();
    				if (index == 0){
    					head=head.next;
    				}
    				//remove item somewhere in the middle
    				else {
    					for(int i = 0; i < index; i++) {
    						previous = current;
    						current = current.next;
    					}
    					previous.next = current.next;
    				}
    		    	size--;
    		    	return current.data;
    		    }
     
    		    public boolean removeFirstOccurrence(Object o){
    		    	E item = (E) o;
    		    	Node <E> previous = null;
    		    	Node <E> current = head;
    		    	int i = 0;
    		    	while(current != null && i < size) {
    		    		if(head.data.equals(item) && head == tail) {
    		    			head = tail = null;
    		    			size--;
    		    			return true;
    		    		}
    		    		if(head.data.equals(item)) {
    		    			head = head.next;
    		    			size--;
    		    			return true;
    		    		}
    		    		if(current.data.equals(item) && current == tail) {
    		    			previous.next = null;
    		    			size--;
    		    			return true;
    		    		}
    		    		if(current.data.equals(item)) {
    		    			previous.next = current.next;
    		    			size--;
    		    			return true;
    		    		}
    		    		else {
    		    			previous = current;
    		    			current = current.next;
    		    			i++;
    		    		}
     
    		    	}
    		    	return false;
    		    }
    }

    	public class Driver{
    	    public static void main(String[] args) {
    	        SinglyLinkedList <String> list = new SinglyLinkedList <String> ();
     
    	        list.addFirst("Gina");
    	        list.addFirst("Bryan");
    	        list.addFirst("Greg");
    	        list.addLast("Eric");
    			list.addLast("Sarah");
    			list.addLast("Heather");
     
    			System.out.println("The size of the list is " + list.size()
    		              + " and the list is given below");
    		        System.out.println(list);
     
    		    /*  Testing remove */
    			System.out.println("\nTesting remove(int index)");
    	        System.out.println("------------------------");
    	        System.out.println("\nTrying to remove " + list.get(0) + " from the list...");
    	        System.out.println(list.remove(0) + " is removed from the list ");
    			System.out.println("The size of the list is " + list.size()
    	              + " and the list is given below");
    	        System.out.println(list);
     
    	        System.out.println("\nTrying to remove " + list.get(3) + " from the list...");
    	        System.out.println(list.remove(3) + " is removed from the list ");
    	        System.out.println("The size of the list is " + list.size()
    	              + " and the list is given below");
    	        System.out.println(list);
     
    	        System.out.println("\nTrying to remove " + list.get(list.size() -1 ) + " from the list...");
    	        System.out.println(list.remove(list.size() - 1) + " is removed from the list ");
    	        System.out.println("The size of the list is " + list.size()
    	              + " and the list is given below");
    	        System.out.println(list);
     
     
    	        /* Testing removeFirstOccurence */
    	        System.out.println("\n\nTesting removeFirstOccurrence");
    	        System.out.println("-----------------------------");
    	        list.add("Nora");
    	        list.add(2, "Nora");
    	        list.addLast("Christian");
     
    	        System.out.println("The size of the list is " + list.size()
    	              + " and the list is given below");
    	        System.out.println(list);
     
    	        list.removeFirstOccurrence("Nora");
    	        System.out.println("\nTrying to remove the first occurrence of Nora...");
    	        System.out.println("The size of the list is " + list.size()
    	              + " and the list is given below");
    	        System.out.println(list);
     
    	        list.removeFirstOccurrence("Nora");
    			System.out.println("\nTrying to remove the first occurrence of Nora...");
    			System.out.println("The size of the list is " + list.size()
    	              + " and the list is given below");
    	        System.out.println(list);
     
    	        list.removeFirstOccurrence("Nora");
    		    System.out.println("\nTrying to remove the first occurrence of Nora...");
    		    System.out.println("The size of the list is " + list.size()
    			              + " and the list is given below");
    	        System.out.println(list);
    }

    As you can see, when removeFirstOccurence is tested, the list that is printed is not correct. The remove method works fine but then won't let you add new nodes properly.

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Remove at index in singly linked list?

    The posted code has many (13) compiler errors which makes it impossible to test.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Remove at index in singly linked list?

    Okay. Well I really don't have time to start a new project and try and write a smaller and simpler code so that you may see what my problem is here. I don't think I've been exposed to linked lists enough to just bang out a small program. I tried to post the part of my project that I was having issues with but I guess it's showing you errors.

    I believe I need an if statement when the index is tail. I believe that will solve my problem but I can't write it without it giving me a null pointer exception. I've been trying to draw pictures and figure it out but it just wont come to me.

    I think I'm just going to stare at it some more and hopefully I'll figure it out before midnight tomorrow. I appreciate your willingness to help.

  6. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Remove at index in singly linked list?

    Can you post the test program's output, add some comments to it saying what is wrong with the output and show what the output should be?
    If you don't understand my answer, don't ignore it, ask a question.

  7. #7
    Member
    Join Date
    Mar 2013
    Posts
    58
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Remove at index in singly linked list?

    Here is the output now:
    The size of the list is 6 and the list is given below
    [Donald ==> Brett ==> Issac ==> Dana ==> Dillon ==> Jonathan]

    Testing remove(int index)
    ------------------------

    Trying to remove Donald from the list... //here we are removing index 0
    Donald is removed from the list
    The size of the list is 5 and the list is given below
    [Brett ==> Issac ==> Dana ==> Dillon ==> Jonathan]

    Trying to remove Dillon from the list... //here we are removing index 3
    Dillon is removed from the list
    The size of the list is 4 and the list is given below
    [Brett ==> Issac ==> Dana ==> Jonathan]

    Trying to remove Jonathan from the list... //here we are removing size-1, which is the tail
    Jonathan is removed from the list
    The size of the list is 3 and the list is given below
    [Brett ==> Issac ==> Dana]
    // works fine.
    // now we add 3 more nodes as follows:
    // list.add("Nicole");
    // list.add(2, "Nicole");
    // list.addLast("Joe");

    Testing removeFirstOccurrence
    -----------------------------
    The size of the list is 6 and the list is given below //first Nicole and Joe are not present, however list size is incremented
    [Brett ==> Issac ==> Nicole ==> Dana]

    Trying to remove the first occurrence of Nicole... //works fine but nodes are missing
    The size of the list is 5 and the list is given below
    [Brett ==> Issac ==> Dana]

    Trying to remove the first occurrence of Nicole... //removes nothing because nodes that were added are missing
    The size of the list is 5 and the list is given below
    [Brett ==> Issac ==> Dana]

    Trying to remove the first occurrence of Nicole...
    The size of the list is 5 and the list is given below
    [Brett ==> Issac ==> Dana]



    This is what it is supposed to be:
    The size of the list is 6 and the list is given below
    [Donald ==> Brett ==> Issac ==> Dana ==> Dillon ==> Jonathan]

    Testing remove(int index)
    ------------------------

    Trying to remove Donald from the list...
    Donald is removed from the list
    The size of the list is 5 and the list is given below
    [Brett ==> Issac ==> Dana ==> Dillon ==> Jonathan]

    Trying to remove Dillon from the list...
    Dillon is removed from the list
    The size of the list is 4 and the list is given below
    [Brett ==> Issac ==> Dana ==> Jonathan]

    Trying to remove Jonathan from the list...
    Jonathan is removed from the list
    The size of the list is 3 and the list is given below
    [Brett ==> Issac ==> Dana]


    Testing removeFirstOccurrence
    -----------------------------
    The size of the list is 6 and the list is given below
    [Brett ==> Issac ==> Nicole ==> Dana ==> Nicole ==> Joe]

    Trying to remove the first occurrence of Nicole...
    The size of the list is 5 and the list is given below
    [Brett ==> Issac ==> Dana ==> Nicole ==> Joe]

    Trying to remove the first occurrence of Nicole...
    The size of the list is 4 and the list is given below
    [Brett ==> Issac ==> Dana ==> Joe]

    Trying to remove the first occurrence of Nicole...
    The size of the list is 4 and the list is given below
    [Brett ==> Issac ==> Dana ==> Joe]

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Remove at index in singly linked list?

    Here is the output now:
    That's not using the data that the posted code has.

    The number of tests posted is too long for showing an error.
    Short and direct would be better. Also the problem should be hi-lighted:
    >>>>THIS IS WRONG,
    and THE OUTPUT SHOULD BE ...

    Why doesn't the code save and report the boolean value returned by the method?
    If you don't understand my answer, don't ignore it, ask a question.

Similar Threads

  1. Creating methods in a singly linked list?
    By EDale in forum Collections and Generics
    Replies: 13
    Last Post: September 29th, 2013, 06:13 PM
  2. Remove at index method for singly linked list... what's wrong?
    By EDale in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2013, 09:12 PM
  3. Singly Linked List
    By koala711 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2012, 02:15 PM
  4. Singly-Linked list structure
    By blaster in forum Algorithms & Recursion
    Replies: 24
    Last Post: March 11th, 2012, 03:42 PM
  5. Singly Circular Linked List Error
    By clydefrog in forum Collections and Generics
    Replies: 7
    Last Post: March 5th, 2012, 08:17 PM