How to insert an element in a sorted list in Java

Question

i have to create my own list in java. the elements(Person element) to be inserted must be sorted(low to high). So i created a method compareTo to check the names of inserted Person. The problem is with insert method. I wrote this code:

public boolean insert(Person p){
    PersonListElement element = new PersonListElement(p);
    boolean inserted = false;
    if(containsElement(p) == true){
        inserted = false;
        return inserted;
    }
    if(head == null){
        head = element;
        size = size + 1;
        inserted = true;
        return inserted;
    }
    PersonListElement position = head;
    PersonListElement prev = null;
    while(position != null){
        if(position.getValue().compareTo(element.getValue()) < 0){
            if(prev != null){
                prev.setNext(element);
                element.setNext(position);
                inserted = true;
                position = null;
            }
            prev = position;
            position = position.getNext(); //here i get pointerException prob.
        }
    }
    if(inserted == false && prev != null){
        prev.setNext(element);
        inserted = true;
    }
    size = size + 1;
    return inserted;
}

this is my method but is not finished. can you help me?

EDIT:

I tried to make a method for deleting elements too. I think that my code works for empty list, 1 size list and if the element is not in the end of list. But i dont know if my method deletes the last element:

public boolean delete(Person p){
    boolean deleted = false;
    if(size == 0){
        deleted = false;
        return deleted;
    }
    if(size == 1 && head.getValue().compareTo(p) == 0){
        head = null;
        deleted = true;
        return deleted;
    }
    PersonListElement current = head;
    PersonListElement prev = null;
    PersonListElement next = head;
    next = next.getNext();
    while(next != null){
        if(current.getValue().compareTo(p) == 0){
            prev.setNext(next);
            deleted = true;
            return deleted;
        }
        prev = current;
        current.getNext();
        next.getNext();
    }
    return deleted;
}

with this class i tested my code:

class SortList
{
    public static void main(String args[]){
        SortedList list = new SortedList();
        Person a = new Person("Alice", 10);
        list.insert(a);
        a = new Person("Al", 20);
        list.insert(a);
        a = new Person("Bo", 90);
        list.insert(a);
        p = new Person("Cin", 3);
        list.insert(a);     
        System.out.println(list);
        }
}

Answer 1

You need to complete the iteration as well as the insertion. Assuming you are implementing a linked list and you have a public next attribute at you ListElement class.

public boolean insert(Person p){
        ListElement element = new StackElement(p);
        boolean inserted = false;
        if(head == null){
            head = element;
            size = size + 1;
            inserted = true;
            return inserted;
        }
        ListElement temp = head;
        ListElement prev = null;
        while(temp != null){
            if(temp.compareTo(element) < 0) {
                    if(prev != null) prev.next = element; //Keep the chain connected
                    element.next = temp; //Insert you element before temp
                    inserted = true;
                    break; 
                }
                prev = temp;
                temp = temp.next;
            }
        }
        if(!inserted && temp == null && prev != null) { //You may want to insert it at the end of the list if no upper element is found.
                 prev.next = element; //Put it at the end.
                 inserted = true;
        }
       if(inserted) size = size + 1;
       return inserted; //This should be true in any case but I left it for the case you want to avoid inserting the element at the end if its place is not found.
    }

ListElement.next could also be a private or protected attribute and be accessed through a getter like getNext().

I think you shouldn't return the inserted value since if the element can't be place before any other it should be placed at the end of the list and therefore always being inserted. That is, this code is a better implementation of a sorted list:

public void insert(Person p){
        ListElement element = new StackElement(p);

        if(head == null){
            head = element;
            size = size + 1;
            return;
        }

        ListElement temp = head;
        ListElement prev = null;

        boolean inserted = false;
        while(temp != null){
            if(temp.compareTo(element) < 0) {
                    if(prev != null) prev.next = element; //Keep the chain connected
                    element.next = temp; //Insert you element before temp
                    inserted = true;
                    temp = null;
                } else {
                    prev = temp;
                    temp = temp.next;
                }
            }
        }
        if(!inserted && prev != null)
        { 
                 prev.next = element; //Put it at the end.
        }
       size = size + 1;
    }

Concerning your delete method, I think you are making things too complicated. In your iteration you only have to keep two references: one for the previous element and another to the current. If your first element is the one to be deleted then your prev reference will be null and you will have to update head. Otherwise, you will need to update prev next reference making it reference the element after current:

public boolean delete(Person p){
    boolean deleted = false;
    PersonListElement current = head;
    PersonListElement prev = null;
    while(current != null && !deleted){
        if(current.getValue().compareTo(p) == 0){
            if(prev != null) 
                prev.setNext(current.getNext());
            else
                head = current.getNext();
            deleted = true;
        } else {
        prev = current;
        current = current.getNext();
       }
    }
    if(deleted) size--;
    return deleted;
}