Vfrdtyky

I'm trying to make a sorted linkedlist. The addElement and removeElement methods works almost as they should except that the addElement method don't always insert the elements in the correct order.

Here's my code so far:

public class SortedLinkedList {



// Node class

class Node {

    public String data;

    public Node next;

}



// attributes

private Node first;

private int size;



public SortedLinkedList() {

    first = null;

}



public void addElement(String element) {

    if (first == null) {

        Node newNode = new Node();

        newNode.data = element;

        newNode.next = null;

        first = newNode;



        size++;



    } else if (first.toString().compareTo(element) > 0) {

        Node newNode = new Node();

        newNode.data = element;

        newNode.next = first;

        first = newNode;



        size++;



    } else {

        Node before = first;

        Node after = first.next;



        while (first.next != null) {

            Node newNode = new Node();

            newNode.data = element;



            if (after.toString().compareTo(element) > 0) {



                before.next = newNode;

                newNode.next = after;

            }



            before = after;

            after = after.next;

        }



        size++;

    }

}



public boolean removeElement(String element) {

    boolean removed = false;



    try {

        if (first.data.toString().equals(element)) {

            first = first.next;

            removed = true;



        } else {

            Node before = first;

            Node after = first.next;



            while (first.next != null) {

                if (after.data.toString().compareTo(element) == 0) {



                    before.next = after.next;

                    break;

                }



                before = after;

                after = after.next;

            }



            size--;

            removed = true;

        }

    } catch (NullPointerException e) {

        removed = false;

    }

    return removed;

}



public int countElements() {

    return size;

}



@Override

public String toString() {



String result = "{";

Node current = this.first;



while (current != null) {

    if (current.next != null) {

        result = result + current.data.toString() + ", ";

    } else {

        result = result + current.data.toString();

    }

    current = current.next;

}



result = result + "}";



return result;

}

For example, I have tried to insert the values: 'b, a, d, c' and the output is: 'c, d, a, b' but it should be 'a, b, c, d'.
I really can't see what I'm doing wrong.

Any help would be appreciated!

You have various small issues.

1. You are comparing the Node instead of the Node's data.


2. Your while loop is looping while (first.next != null). Shouldn't this be checking before or after?


3. Why are you creating the new Node inside the while loop?

You could change the Node like this:

class Node implements Comparable<Node> {

    private final String data; //once initialised shouldn't change

    private Node next; //this can change



    public Node(String data) {

       this.data = data;

    }



    public Node getNext() {

      return next;

    }



    public void setNext(Node next) {

      this.next = next;

    }



    public int  compareTo(Node that) {

      return this.data.compareTo(that.data);

    }

}

In your addElement(String element) I would immediately do the following before the if conditions, it is all the same:

Node newNode = new Node(element);

size++;

Your while loop in the last case can then be:

 Node after = first;



 while ((after != null) && (after.compareTo(newNode) <= 0)) {

     //we traverse to the next 

     before = after;

     after = after.getNext();

 }



 //either we found the spot, or it is the last element in the list

 before.setNext(newNode);

 newNode.setNext(after);

You can probably also include the case of when the new node should be inserted at the head of the list too... but I leave it to you.

If you want a sorted linked list, you can use the normal LinkedList library and call List#sort(Comparator) on it.

For example, if we want to sort Strings by alphabetical order:

LinkedList<String> list = new LinkedList<>();

list.addAll(Arrays.asList("b","d","c","a"));

System.out.println(list);  // ["b","d","c","a"]

list.sort(new Comparator<String>() {

    //This sorts the values by unicode value. In most cases, this results in sorting by alphabetical order

    @Override

    public int compare(String s1, String s2){

        return s1.compareToIgnoreCase(s2);

    }

});

System.out.println(list);  // ["a","b","c","d"]