Why does my method fail to sort my linked list alphabetically?

Question

public class doubleLinkedList {

    class Node {
      String value;
      Node prev;
      Node next;

      Node(String val, Node p, Node n) {
        value = val;
        prev = p;
        next = n;
      }

      Node(String val) {
        value = val;
        prev = null;
        next = null;
      }
    }

    Node first;
    Node last;

    public doubleLinkedList() {
      first = null;
      last = null;
    }

    public boolean isEmpty() {
      if (first == null)
        return true;
      else
        return false;
    }

    /**The size method returns the length of the linked list
     * @return the number of element in the linked list
    */
    public int size() {
      int count = 0;
      Node traverse = first;
      while (traverse != null) {
        count++;
        traverse = traverse.next;
      }
      return count;
    }


    public void add(String element) {

      if (isEmpty()) {
        first = new Node(element);
        last = first;
      } else {

        Node p = first;
        Node elementTobeAdded;
        while (((p.value).compareTo(element)) > 0 && p.next != null) {
          p = p.next;
        }

        if (p.next != null) {
          elementTobeAdded = new Node(element, p, p.next);
          p.next.prev = elementTobeAdded;
          p = elementTobeAdded.prev;
        } else {
          elementTobeAdded = new Node(element, p, null);
          p.next = elementTobeAdded;
          elementTobeAdded.next = null;
          last = elementTobeAdded;
        }

      }
    }

    public void printForward() {
      Node printNode = first;
      while (printNode != null) {
        System.out.print(printNode.value + ", ");
        printNode = printNode.next;
      }
    }
  }
  public class test {

    public static void main(String[] args) {
      doubleLinkedList car = new doubleLinkedList();
      car.add("Jeep");
      car.add("benz");
      car.add("Honda");
      car.add("Lexus");
      car.add("BMW");
      car.printForward();
    }
  }

My add method is trying to add nodes to a list in alphabetical order. My printForward method prints out each element in the list. In my main method, it prints out "Jeep, benz, Honda, BMW,", which is not in alphabetical order.

Answer 1

Change the not empty case for your add method from this

  Node p = first;

  Node elementTobeAdded;

  while(((p.value).compareTo(element)) > 0 && p.next != null)
  {
    p = p.next;
  }

  if(p.next != null)
  {
  elementTobeAdded = new Node(element,p,p.next);
  p.next.prev = elementTobeAdded;
  p = elementTobeAdded.prev;
  }

  else
  {
    elementTobeAdded = new Node(element, p, null);
    p.next = elementTobeAdded;
    elementTobeAdded.next = null;
    last = elementTobeAdded;
  }

to this:

  Node p = first;
  while (p.value.compareTo(element) < 0 && p.next != null) {
    p = p.next;
  }
  if (p.value.compareTo(element) > 0) {
    Node toAdd = new Node(element, p.prev, p);
    p.prev = toAdd;
    if (toAdd.prev != null) {
        toAdd.prev.next = toAdd;
    }else {
      first = toAdd;
    }
  }else {
    Node toAdd = new Node(element, p, p.next);
    p.next = toAdd;
    if (toAdd.next != null) {
        toAdd.next.prev = toAdd;
    }else {
      last = toAdd;
    }
  }

There were many errors here. The biggest one was that you never checked for the case where the new element should be inserted at the beginning of the list. A new element was always inserted after the first element even if it should have come first.

Note that "benz" comes at the end because the String.compareTo method treats capitals as coming before lower case letters.

Answer 2

It is not an a linked list... You wrote some sort of Queue (with optional possibility to make it Dequeue).

About your question - you have an error in your 'add' method - at least you don't check if it is necessary to move head forward. It is possible that you have another bugs, but it is too hard to read such styled sources (please fix your question formatting)...