如何在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

AFAIU什么removeByIndex确实是

1. 如果指数为0，它工作正常。
2. 如果不是，它首先得到第n个链接。 （这是你想要删除的链接，但是实际上你需要以前的链接才能正确链接链接）
3. 然后迭代直到列表结束，并删除最后一个链接 - 错误。

忘记第3步，并获得与指数n中的链接 - 1在步骤2然后，你可以重新链接链，从列表中删除下一个元素：

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

Answer 3

东西如：

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

我不确定你想用removeByIndex方法中的while循环做什么。你想要做的与你在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 5

你只是在这里设置目标变量，而不是以任何方式改变它。想想它应该发生什么目标才能被删除。

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