Comment implémenter une méthode remove by index pour une liste de liens simples en Java?

Question

Je suis étudiant en cours de programmation et j'ai besoin d'aide avec ce code que j'ai écrit. Jusqu'à présent, j'ai écrit une classe de liste liée entière (voir ci-dessous), mais pour une raison quelconque, la méthode "removeByIndex" ne fonctionnera pas. Je n'arrive pas à comprendre pourquoi, la logique me semble saine. Y a-t-il un problème que je ne connais pas?

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

Vous faire des commentaires mal:

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

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

Les commentaires devraient expliquer pourquoi vous faites quelque chose, pas décrire ce qui est fait. Le code le fait déjà. Le code indique clairement que quelque chose est fait alors que la tête n'est pas nulle, il est inutile de le répéter dans le commentaire.

Answer 2

AFAIU ce removeByIndex fait est

1. si l'indice est 0, il fonctionne très bien.
2. sinon, il obtient d'abord le nth lien. (Ceci est le lien que vous voulez supprimer Cependant, vous auriez en fait besoin du précédent lien afin de relier la chaîne correctement!)
3. alors il itère jusqu'à la fin de la liste, et supprime le dernier lien - faux .

Oublie étape 3 et obtenir le lien avec l'index n - 1 à l'étape 2. Ensuite, vous pouvez lier à nouveau la chaîne pour retirer le élément suivant de la liste:

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

Answer 3

Quelque chose comme:

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

Je ne sais pas ce que vous essayez de faire avec la boucle while dans la méthode removeByIndex. Ce que vous voulez faire est similaire à ce que vous avez fait dans la méthode removeElement. À savoir, vous souhaitez trouver l'objet Link approprié et modifier le prédécesseur pour pointer vers le successeur. Étant donné que la liste est une liste unidirectionnelle, vous ne pouvez pas extraire le prédécesseur directement du noeud en cours de suppression. Pour résoudre ce problème, vous devez rechercher le nœud index - 1 plutôt que le nœud 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; 
    } 

Je vais vous laisser le soin de trouver des indices trop petits ou trop grands.

Answer 5

Vous ne définissez ici que la variable cible, sans la modifier. Pensez à ce qu'il est censé arriver à cibler pour qu'il soit supprimé.

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