java - 为什么我的方法无法按字母顺序对链接列表进行排序？

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();
    }
  }

我的添加方法正在尝试按字母顺序将节点添加到列表中。我的 printForward 方法打印出列表中的每个元素。在我的主要方法中，它打印出“Jeep，benz，Honda，BMW”，这不是按字母顺序排列的。

Answer 1

从此更改添加方法的非空情况

  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;
  }

对此:

  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;
    }
  }

这里有很多错误。最大的一个是您从未检查过应将新元素插入到列表开头的情况。新元素总是插入在第一个元素之后，即使它应该排在最前面。

请注意，“benz”出现在末尾，因为 String.compareTo 方法将大写字母视为在小写字母之前。