How to insert String data in a sorted doubly linked list?

Question

I have a sorted doubly linked list in which the first and last elements are null. This means when I insert the values a, b, c. The result should look as follows: {null, a, b, c, null}

The empty sorted doubly linked list should look like this: {null, null} in which the first and last elements are always are null.

The problem is that when I insert data in the sorted doubly linked list, the data is not sorted correctly and the 2 null values are always at the end of the list. How can I fix this?

Here is my current insert method:

    public void addElement(String element) {
    // new node which will be inserted in the list
    Node newNode = new Node();
    newNode.data = element;

    // if the list is empty
    if (size == 0) {
        last = newNode;
        newNode.next = first;
        first = newNode;

        size++;

    } else {
        Node current = first;

        // if the element should be at the beginning of the list
        if (current.data.compareTo(element) > 0) {
            newNode.next = current;
            newNode.previous = null;
            current.previous = newNode;

            first = newNode;
        } else {

            while (current != null) {
                if (current.data.compareTo(element) <= 0) {
                    if (current.next == null) {
                        newNode.next = current.next;
                        newNode.previous = current;
                        current.next = newNode;

                        break;
                    }

                    newNode.next = current.next;
                    newNode.previous = current;
                    current.next.previous = newNode;
                    current.next = newNode;

                    break;

                } else {
                    current = current.next;
                }
            }
        }
        size++;
    }
}

Answer 1

It is not so clear what you are doing in your code, so I modified it a bit and made more OO style, so here it is:

class Node {

  String data;
  Node next, previous;
}

public class SortedDLL {

  private Node first;
  private Node last;
  private int size = 0;

  public SortedDLL() {
    size = 0;
    first = new Node();
    last = new Node();
    first.next = last;
    last.previous = first;
  }

  public void addElement(String element) {
    Node newNode = new Node();
    newNode.data = element;

    if (size == 0) {
      first.next = newNode;
      newNode.previous = first;
      newNode.next = last;
      last.previous = newNode;
    } else {
      Node node = first;
      while (node.next.data != null && node.next.data.compareTo(newNode.data) < 0) {
        node = node.next;
      }
      newNode.next = node.next;
      node.next.previous = newNode;
      node.next = newNode;
      newNode.previous = node;
    }

    size++;
  }

  public void print() {
    Node node = first;
    while (node != null) {
      System.out.print(node.data != null ? node.data + " " : "null ");
      node = node.next;
    }
  }

  public void printReverse() {
    Node node = last;
    while (node != null) {
      System.out.print(node.data != null ? node.data + " " : "null ");
      node = node.previous;
    }

  }

  public static void main(String[] args) {
    SortedDLL sortedDLL = new SortedDLL();
    sortedDLL.addElement("c");
    sortedDLL.addElement("a");
    sortedDLL.addElement("b");
    sortedDLL.addElement("c");

    System.out.println("list: ");
    sortedDLL.print();

    System.out.println("\nlist reverse: ");
    sortedDLL.printReverse();
  }

Output:

list: 
null a b c c null 
list reverse: 
null c c b a null

Answer 2

the problem starts at the first call when size == 0

you push the first null to the end.. and the first node becomes the new node.

then, if you fix this you will get null pointer exception at the row :

if (current.data.compareTo(element) > 0) {

because the current will be null and the will not have data.

you should ignore the first null in the first insert and every insert after that.

Answer 3

Depending on implementation I think you're just doing the right thing in the wrong place.

        while (current != null) {
            if (current.next == null) {
                newNode.next = null;
                newNode.previous = current;
                current.next = newNode;

                break;
            }

            if (current.next.data.compareTo(element) > 0) {
                newNode.next = current.next;
                newNode.previous = current;
                current.next.previous = newNode;
                current.next = newNode;
                break;

            } else {
                current = current.next;
            }
        }

Instead of checking if the currently selected node is smaller you need to check if the node after is bigger because then you can place the node. And checking if current.next is null needs to be done outside of that comparison.