Как реализовать метод удаления по индексу для односвязного списка в Java?

Question

Я студент в классе программирования, и мне нужна помощь с этим кодом, который я написал. До сих пор я написал целый класс связанного списка (см. Ниже), но по какой-то причине метод removeByIndex не будет работать. Я не могу понять, почему, логика кажется мне здоровой. Есть какая-то проблема, о которой я не знаю?

 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

Вы делаете комментарии неправильно:

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

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

Комментарии должны объяснять, почему вы что-то делаете, а не описывать, что делается. Код уже делает это. В коде четко указано, что что-то сделано, пока head не равен null, и повторять это в комментарии бесполезно.

Answer 2

Вы только устанавливаете целевую переменную здесь, но никак не меняете ее. Подумайте, что именно должно произойти с целью удаления.

  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 3

Я не уверен, что вы пытаетесь сделать с помощью цикла while в методе removeByIndex. То, что вы хотите сделать, похоже на то, что вы сделали в методе removeElement. А именно, вы хотите найти соответствующий объект Link и изменить предшественника так, чтобы он указывал на преемника. Поскольку список представляет собой односвязный список, вы не можете получить предшественника непосредственно из удаляемого узла. Чтобы преодолеть это, вам нужно найти узел index - 1, а не узел index.

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

Я предоставлю вам решать, как обращаться с слишком маленькими или слишком большими индексами.

Answer 4

Что-то вроде:

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 5

AFAIU, что removeByIndex делает

1. если индекс равен 0, он работает нормально.
2. , если нет, сначала он получает ссылку nth . (Это ссылка, которую вы хотите удалить. Тем не менее, вам действительно понадобится ссылка предыдущая , чтобы правильно связать цепочку!)
3. затем выполняет итерацию до конца списка и удаляет последнюю ссылку - неправильно.

Забудьте о шаге 3 и получите ссылку с индексом n - 1 на шаге 2. Затем вы можете связать цепочку, чтобы удалить элемент следующий из списка:

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