Как вставить строковые данные в отсортированный двусвязный список?

Question

У меня есть отсортированный двусвязный список, в котором первый и последний элементы равны нулю. Это означает, что когда я вставляю значения a, b, c. Результат должен выглядеть следующим образом: {null, a, b, c, null}

Пустой отсортированный двусвязный список должен выглядеть следующим образом: {null, null}, в котором первый и последний элементы всегда равны нулю.

Проблема в том, что когда я вставляю данные в отсортированный двусвязный список, данные сортируются некорректно, а 2 пустых значения всегда находятся в конце списка. Как я могу это исправить?

Вот мой текущий метод вставки:

    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

В зависимости от реализации, я думаю, вы просто делаете правильные вещи в неправильном месте.

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

Вместо того, чтобы проверять, меньше ли текущий выбранный узел, вам нужно проверить, больше ли узел после, потому что тогда вы можете разместить узел.И проверка того, является ли current.next нулевым, должна выполняться вне этого сравнения.

Answer 2

Не совсем понятно, что вы делаете в своем коде, поэтому я немного изменил его и сделал более стиль OO, поэтому вот оно:

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

Выход:

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

Answer 3

проблема начинается при первом вызове, когда размер == 0

вы толкаете первый ноль до конца .. и первый узел становится новым узлом.

затем, если выисправив это, вы получите исключение нулевого указателя в строке:

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

, потому что ток будет нулевым, а данные не будут.

, вы должны игнорировать первый нулевой в первой вставкеи каждая вставка после этого.