如何使用链表中的对象实现添加和删除方法

Question

链接列表

o void add（Train）-创建一个包含参数对象的新节点，并将该节点添加到列表中，使列表保持升序排序。

o Train delete（int）-在列表中搜索带有参数车次的列车。如果找到它，从列表中删除它，并返回Train对象。如果找不到，则返回NULL。

public void add(Train myTrain) 
{            
        if (myTrain == null) {   
            currentPosition.setNext=new ListNode(myTrain);
        }   
        currentPosition.setNext(new ListNode(myTrain)); 
        currentPosition = currentPosition.getNext();    
        count++;
}

public Train delete(int index)
{                     
        ListNode tmp = head;    
        for (int  i = 0; i < index; i++)        
        {                                
            tmp = tmp.next;     
        }       
        tmp.next = tmp.next.next;             
        count--;
        return tmp.train;
}

我的添加和删除没有正常工作。我不知道如何删除车次。不使用节点的索引不知道怎么做。

Answer 1

您的delete方法返回了错误的列车。这是一个图像。在for循环之后,它看起来如下所示：

tmp        tmp.next   tmp.next.next
  v          v          v
[train 1]->[train 2]->[train 3]

因此，当您执行tmp.next=tmp.next.next时，将得到以下结果：

tmp        tmp.next
  v          v
[train 1]->[train 3]

           [train 2]

但是在该方法的末尾，您正在执行return tmp.train，并且您可以看到，tmp仍然指向train1，它不是您删除的那个。您将不得不做的是将已删除的节点存储在临时变量中，这样，一旦它从列表中删除，您仍然可以访问它：

public Train delete(int index)
{                     
        ListNode tmp = head;    
        for (int  i = 0; i < index; i++)        
        {                                
            tmp = tmp.next;     
        }
        ListNode deleted = tmp.next;       
        tmp.next = tmp.next.next;             
        count--;
        return deleted.train;
}

当然，您仍然需要添加一些边界检查，以确保index在列表中。

Answer 2

你不是在互相比较火车来保持排序。我会选这样的东西：

public void add(Train myTrain) {
    add(myTrain, head);
}

private void add(Train myTrain, ListNode head) {
    if (head.getNext() == null) {
        // End of list
        head.setNext(new ListNode(myTrain));
        count++;
    } else if (head.getNext().getTrain().getTrainNumber() < myTrain.getTrainNumber()) {
        // We found the spot.
        ListNode newNode = new ListNode(myTrain);
        newNode.setNext(head.getNext());
        head.setNext(newNode);
        count++;
    } else {
        // This was not the spot, try next position.
        add(myTrain, head.getNext());
    }
}


public Train delete(int trainNumber) {
    if (head == null) {
        // There is no list at all.
        return null;
    }
    return delete(trainNumber, head);
}

public Train delete(int trainNumber, ListNode currentNode) {
    if (currentNode.getNext() == null) {
        // No train found.
        return null;
    } else if (currentNode.getNext().getTrain().getTrainNumber() == trainNumber) {
        // The next train should be deleted.
        ListNode tmp = currentNode.getNext();
        currentNode.setNext(currentNode.getNext().getNext());
        return tmp.getTrain();
    } else {
        return delete(trainNumber, currentNode.getNext());
    }
}