How do I implement a remove by index method for a singly linked list in Java?

Question

Hi, I'm a student in a programming class, and I need some help with this code I've written. So far I've written an entire linked list class (seen below), yet for some reason the "removeByIndex" method won't work. I can't seem to figure out why, the logic seems sound to me. Is there some problem I don't know about?

 public class List<T> {
 //private sub-class Link
 private class Link {
  private T value;
  private Link next;
  //constructors of Link:
  public Link (T val) {
   this.value = val;
   this.next = null;
  }

  public Link (T val, Link next) {
   this.value = val;
   this.next = next;
  }


  @SuppressWarnings("unused")
  public T getValue() {
   return value;
          }
 }
 private static final Exception NoSuchElementException = null;
 private static final Exception IndexOutOfBoundsException = null;
 private Link chain = null;
 //constructors of List:
 public List() {
  this.chain = null;
 }

 //methods of List:
 /**
  * Preconditions: none
  * Postconditions: returns true if list is empty
  */
 public boolean isEmpty() {
  return this.chain == null;
 }


 /**
  * Preconditions: none
  * Postconditions: A new Link is added via add-aux
  * @param element
  */
 public void add(T element) {
  this.add_aux(element, this.chain);
 }

 /**
  * Preconditions: none
  * Postconditions: A new Link is added to the current chain
  * @param element
  * @param chain
  */
 private void add_aux(T element, Link chain) {
  if (chain == null) {
   //if chain is null set chain to a new Link with a value of
                           //element
   this.chain = new Link(element);
  }
  else if (chain.next != null) {
   //if chain.next is not null, go to next item in chain and
                           //try 
                           //to add element
   add_aux(element, chain.next);
  }
  else {
   //if chain.next is null, set chain.next equal to a new Link
                           //with value of element.
   chain.next = new Link(element);
  }
 }

 /**
  * Preconditions: none
  * Postconditions: returns the link at the defined index via nthlink_aux
  * @param index
  * @return
  */
 private Link nthLink (int index) {
  return nthLink_aux(index, this.chain);

 }

 /**
  * Preconditions: none
  * Postconditions: returns the link at the defined index in the specified    
          *chain
  * @param i
  * @param c
  * @return
  */
 private Link nthLink_aux (int i, Link c) {
  if (i == 0) {
   return c;
  }

  else return nthLink_aux(i-1, c.next);
 }

 /**
  * Preconditions: the specified element is present in the list
  * Postconditions: the specified element is removed from the list
  * @param element
  * @throws Exception
  */
 public void removeElement(T element) throws Exception {
  if (chain == null) {
   throw NoSuchElementException;
  }
  //while chain's next is not null and the value of chain.next is not
                  //equal to element, 
  //set chain equal to chain.next
  //use this iteration to go through the linked list.
  else while ((chain.next != null) && !(chain.next.value.equals(element))){
   Link testlink = chain.next;
   if (testlink.next.value.equals(element)) {
    //if chain.next is equal to element, bypass the
                                    //element.
    chain.next.next = chain.next.next.next;
   }
   else if (testlink.next == null) {
    throw NoSuchElementException;
   }
  }
 }

 /**
  * Preconditions: none
  * Postsconditions: the Link at the specified index is removed
  * @param index
  * @throws Exception
  */
 public void removeByIndex(int index) throws Exception {
  if (index == 0) {
   //if index is 0, set chain equal to chain.next
   chain = chain.next;
  }

  else if (index > 0) {
   Link target = nthLink(index);
   while (target != null) {
    if (target.next != null) {
     target = target.next;
    }

    //if target.next is null, set target to null
    else {
     target = null;
    } 
   }
   return;
  }

  else throw IndexOutOfBoundsException;
 }

 /**
  * Preconditions: none
  * Postconditions: the specified link's value is printed
  * @param link
  */
 public void printLink (Link link) {
  if(link != null) {
           System.out.println(link.value.toString());
  }
 }

 /**
  * Preconditions: none
  * Postconditions: all of the links' values in the list are printed.
  */
 public void print() {
  //copy chain to a new variable
  Link head = this.chain;
  //while head is not null
  while (!(head == null)) {
   //print the current link
   this.printLink(head);
   //set head equal to the next link
   head = head.next;
  }
 }

 /**
  * Preconditions: none
  * Postconditions: The chain is set to null
  */
 public void clear() {
  this.chain = null;
 }

 /**
  * Preconditions: none
  * Postconditions: Places the defined link at the defined index of the list
  * @param index
  * @param val
  */
 public void splice(int index, T val) {
  //create a new link with value equal to val
  Link spliced = new Link(val);
  if (index <= 0) {
   //copy chain
   Link copy = chain;
   //set chain equal to spliced
   chain = spliced;
   //set chain.next equal to copy
   chain.next = copy;
  }
  else if (index > 0) {
   //create a target link equal to the link before the index
   Link target = nthLink(index - 1);
   //set the target's next equal to a new link with a next
   //equal to the target's old next
   target.next = new Link(val, target.next);
  }
 }

 /**
  * Preconditions: none
  * Postconditions: Check to see if element is in the list, returns true 
  * if it is and false if it isn't
  * @param element
  * @return
  */
 public boolean Search(T element) {
  if (chain == null) {
   //return false if chain is null
   return false;
   }
  //while chain's next is not null and the value of chain.next is not
                  //equal to element, 
  //set chain equal to chain.next
  //use this iteration to go through the linked list.
  else while ((chain.next != null) && !(chain.next.value.equals(element))) {
   Link testlink = chain.next;
   if (testlink.next.value.equals(element)) {
    //if chain.next is equal to element, return true
    return true;
   }
   else if (testlink.next == null) {
    return false;
   }
  }
  return false;
 }

 /**
  * Preconditions: none
  * Postconditions: order of the links in the list is reversed.
  */
 public void reverse() {
  //copy chain
  Link current = chain;
  //set chain equal to null
  chain = null;
  while (current != null) {
   Link save = current;
   current = current.next;
   save.next = chain;
   chain = save;
  }
 }
}'

Answer 1

You doing commenting wrong:

  if (index == 0) {
   //if index is 0, set chain equal to chain.next
   chain = chain.next;
  }

  //while head is not null
  while (!(head == null)) {

The comments should explain why you do something, not describe what is being done. The code already does that. The code clearly states that something is done while head is not null, it is no use saying it again in the comment.

Answer 2

AFAIU what removeByIndex does is

1. if the index is 0, it works fine.
2. if not, it first gets the nth link. (This is the link you want to remove. However, you would actually need the previous link in order to relink the chain properly!)
3. then it iterates until the end of the list, and removes the last link - wrong.

Forget about step 3 and get the link with index n - 1 in step 2. Then you can relink the chain to remove the next element from the list:

Link target = nthLink(index - 1);
if (target.next != null)
  target.next = target.next.next;

Answer 3

Something like:

public void removeByIndex(int index) throws Exception {
    if (index == 0) {
        //if index is 0, set chain equal to chain.next
        chain = chain.next;
    }
    else if (index > 0 && index < size()) {
        Link priorToRemove = nthLink_aux(index - 1);
        priorToRemove.next = priorToRemove.next.next;
    }
    else {
        throw IndexOutOfBoundsException;
    }
}

Answer 4

I am not sure what you are trying to do with the while loop in the removeByIndex method. What you want to do is similar to what you have done in the removeElement method. Namely, you want to find the appropriate Link object and modify the predecessor to point to the successor. Since the list is a singly-linked list, though, you cannot get the predecessor directly from the node being removed. To overcome this, you will want to you find the index - 1 node rather than the index node.

 public void removeByIndex(int index) throws Exception {
  if (index == 0) {
   //if index is 0, set chain equal to chain.next
   chain = chain.next;
  }

  else if (index > 0) {
   Link target = nthLink(index - 1);
   target.next = target.next.next;
   }
   return;
  }

I will leave it up to you to figure out how to deal with indices that are too small or too large.

Answer 5

You are only setting the target variable here, not altering it in any way. Think about what exactly it supposed to happen to target for it to be deleted.

  Link target = nthLink(index);
   while (target != null) {
    if (target.next != null) {
     target = target.next;
    }

    //if target.next is null, set target to null
    else {
     target = null;
    }