How to implement Add and Delete methods using objects in a Linked List

Question

LinkedList

o void add(Train) – Create a new node containing the parametric object, and add the node to the list in such a way that the list stays in ascending, sorted order.

o Train delete(int) – Search the list for the train with the parametric train number. If it is found, delete it from the list and return the Train object. If it is not found, return 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;
}

My add and delete are not working as they should. I do not know how to delete the trainNumber. I don't know how to do it without using the index of the node.

Answer 1

You are not comparing the trains to each other to keep it sorted. I would go for something like:

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

Answer 2

Your delete method is returning the wrong train. Here is a visualisation. After your for loop, it looks like this:

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

So when you do tmp.next = tmp.next.next, you end up with this:

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

           [train 2]

But at the end of the method, you are doing return tmp.train, and as you can see, tmp is still pointing to train 1, which is not the one you deleted. What you will have to do is store the deleted node in a temporary variable, so that you can still access it once it is deleted from the list:

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

Of course, you are still going to have to add in some bounds checking to make sure index is within the list.