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

Question

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;
 }
 }
}'

• Grundlefleck: Could you provide more detail on what "doesn't work" means? Exception, incorrect behaviour, no effect? Should make it easier for us to help you.
• bakkal: You are not supposed to throw exceptions that way either, it's more like throw new IndexOutOfBoundsException(); than throwing a class field that you have explicitly set to null.
• Gabriel Ščerbák: Too much code to look at for such a question, comments are not much helping and BTW. it is called nested class, not sub class, that is something different.

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

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 3

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;
 } 

Answer 4

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 5

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;
 }
}

• FRotthowe: This still throws an IndexOutOfBoundsException only if the list index is negative. The exception should also be thrown if index >= size()