java如何删除linkedlist中特定索引处的对象？

Question

我看到有一些关于这个主题的问题，但这里的情况有点不同，而其他问题涉及Java链表类，这是一个自定义类，我从老师那里得到的，带有一些特定属性

因此，我需要做的是编写一个名为“removeAt”的方法，该方法获取一个“int k”，并删除“k”索引处的对象，然后返回删除对象的“data”项

我的问题是，在找到对象后，我想删除它（基本上删除指向下一个列表节点的指针…）感觉好像有一些缺失的属性，他没有说要添加新的属性

这是我的代码：

public class List {

    private ListNode firstNode;
    private ListNode lastNode;
    private String name;


    public List()
    {
        this("list");
    }


    public List(String listName)
    {
        name=listName;
        firstNode=lastNode=null;
    }


    //override 
    public String toString()
    {
        String stringToReturn = "";

        ListNode currentNode = firstNode;

        while (currentNode != null) {

            stringToReturn += currentNode.toString();
            currentNode = currentNode.getNext();

            if (currentNode != null) {
                stringToReturn += ", ";
            }
        }
        return stringToReturn;
    }


    public Object removeAt(int k) throws ListIndexOutOfBound
    {
        ListNode removedNode = this.firstNode;
        Object removedObject;
        int idx = 0;

        if (isEmpty())
            throw new EmptyListException(this.name);

        if (k < 0)
            throw new ListIndexOutOfBound();

        if (k == 0) {
            removedObject = this.removeFromFront();
        } else {

            while (idx != k) {
                removedNode = removedNode.getNext();
                idx++;

                if (removedNode == null)
                    throw new ListIndexOutOfBound();
            }

            if (removedNode == this.lastNode) {
                removedNode = (ListNode) this.removeFromBack();
            } else {
                removedObject = removedNode.data;
                //i'm stuck here...I want to remove this node from the list!

            }
        }
        return removedNode; 
    }

还有一个ListNode类如下所示：

public class ListNode {

    Object data;
    ListNode nextNode;


    public ListNode(Object o){
        this(o,null);
    }
    public ListNode(Object o,ListNode node){
        data=o;
        nextNode=node;
    }
    public Object getObject(){
        return data;
    }
    public ListNode getNext(){
        return nextNode;
    }

}

您建议如何实现这一目标

Answer 1

我建议您始终记住要删除的节点之前的节点，以便在删除所需节点后设置下一个节点：

    if (k == 0) {
        removedObject = this.removeFromFront();
    } else {

        ListNode prev = null;

        while (idx != k) {
            prev = removedNode;
            removedNode = removedNode.getNext();
            idx++;

            if (removedNode == null)
                throw new ListIndexOutOfBound();
        }

        if (removedNode == this.lastNode) {
            removedNode = (ListNode) this.removeFromBack();
        } else {
            removedObject = removedNode.data;
            prev.setNext(removedNode.getNext());
        }
    }

这意味着您必须向ListNode对象添加一个方法setNext(ListNode next)

    public void setNext(ListNode next){
        nextNode = next;
    }

它的作用是将prev的nextNode设置为removedNode.getNext()

|                |   prev.getNext()     | removedNode.getNext()    |
                                  
| prev           |   removedNode        | <any node> or null       |

之后：

|                |   prev.nextNode()    | (<any node>.nextNode())? |
                                  
| prev           |   <any node> or null | ...                      |