I am tasked to write an List find and insertInOrder method. But the insertInOrder is not correctly inserting elements into the list in sorted order. Correct behavior is essential to ensure that the list remains sorted after each insertion.

The code is in jack and the syntax is a bit more primitive than python, which I am used to.

Upon insertion:

• If the list is empty or the new element is smaller than the first element, it should be placed at the beginning. (2)
• If the new element is larger than all existing elements, it should be appended at the end. (2,4)
• Otherwise, it should be inserted at the appropriate position within the list. (2,3,4)

I also have a main file where i test to insert values into the list.

The correct output in the VMemulator should be:

-> 3 -> 5 -> 6

-> 2 -> 3 -> 5 -> 6

-> 2 -> 3 -> 4 -> 5 -> 6

-> 2 -> 3 -> 4 -> 5 -> 6 -> 10

-> 5 -> 6 -> 10

Not Found!

-> 2 -> 3 -> 4 -> 5 -> 6 -> 10

but i get:

-> 3 -> 5 -> 6

-> 3 -> 2 -> 5 -> 6

-> 3 -> 2 -> 4 -> 5 -> 6

-> 3 -> 2 -> 4 -> 5 -> 6 -> 10

-> 5 -> 6 -> 10

Not Found!

-> 2 -> 3 -> 4 -> 5 -> 6 -> 10

so the problem is probably something relating to how i handle the head of the list but i have a hard time figuring out where my code is incorrect.

Any help or input would be great!

    field int data;
    field List next;

    /* Creates a new List object. */
    constructor List new(int car, List cdr) {
        let data = car;
        let next = cdr;
        return this;
    }

    /* Disposes this List by recursively disposing its tail. */
    method void dispose() {
        if (~(next =  null)) {          //if the nezt node is not null
            do next.dispose();          //dispose recursively
        }
        do Memory.deAlloc(this);        // Use an OS routine to recycle the memory held by this object.
        return;
    }

    /* Prints the list recursively*/
    method void print() {
        do Output.printString(" -> ");
        do Output.printInt(data);      // Print the current node's data.
        if (~(next =  null)) {
            do next.print();
        }
        return;
    }

    /* Inserts the argument in the right position of the list (ascending order) */
    method void insertInOrder(int ins) {
        var List prev, curr, insert;

        let prev = this;                             //Start with the current node 
        let curr = prev.getnext();                   //Get the next node
        
        while ((~(curr = null)) & (ins > prev.getdata())){               // Loop until we find where to insert
            if (ins < curr.getdata()){
                let insert = List.new(ins, curr);
                do prev.setnext(insert);
                return;
            }
            let prev = prev.getnext();
            let curr = prev.getnext();
        }
        let insert = List.new(ins, curr);   // Handle insertion at end or in empty list
        do prev.setnext(insert);
        return;
    }

    /* Searches the argument in the list, if found, it returns the corresponding List object */
    method List find(int toFind) {
        var List temp;
        var boolean found;
        let temp = this;
        let found = false;

        while ((~(temp = null))) {              // Corrected loop condition
            if (toFind = temp.getdata()) { // Corrected comparison
                let found = true;
                return temp;                // Return immediately if found
            }
            let temp = temp.getnext();      // Move to the next node
        }
        return null;                        // Return null if not found
    }

    /* Helper method to get the next node */
    method List getnext(){
        return next;
    }

    /* Helper method to set the next node */
    method void setnext(List object){
        let next = object;
        return;
    }

    /* Helper method to get the data of this node */
    method int getdata(){
        return data;
    }

}

    function void main(){
        var List v, w, x;
        let v = List.new(3,null);    // Create a new List v object with data 3 and set the next pointer to null (empty list)
        do v.insertInOrder(6);       // Insert elements into the list in order
        do v.insertInOrder(5); 
        
        do v.print();                //v=3,5,6
        do Output.println();

        do v.insertInOrder(2);       // Insert (2)
        
        do v.print();                //v=2,3,5,6
        do Output.println();

        do v.insertInOrder(4);      // Insert(4)
        
        do v.print();               //v=2,3,4,5,6
        do Output.println();

        do v.insertInOrder(10);     // Insert another element (10)
        
        do v.print();               //v=2,3,4,5,6,10
        do Output.println();


        let w = v.find(5);          // Try to find element with value 5
        if (~ (w = null)){
            do w.print();           //w=5,6,10
        }
        else{
            do Output.printString("Not Found!");
        }
        do Output.println();

        let x = v.find(7);          // Try to find element with value 7 (not in the list)
        if (~ (x = null)){
            do x.print();
        }
        else{
            do Output.printString("Not Found!");
        }
        do Output.println();

        let x = v.find(2);      // Try to find element with value 2
        if (~ (x = null)){
            do x.print();       //x=2,3,4,5,6,10
        }
        else{
            do Output.printString("Not Found!");
        }
        do Output.println();

        return; 
    }
}