Сортировка списка вставки продолжает создавать новую голову?

Question

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

static class TreeNode{ 
    int frequency; 
    boolean isLeftChild; 
    TreeNode parent; 
    TreeNode next; 

    /** 
    * TreeNode class constructor to initialize the variables and also 
    * takes a frequency as the parameter. 
    * @param f Frequency of a certain character. 
    */ 
    TreeNode(int f){ 
     frequency = f; 
     isLeftChild = true; 
     parent = null; 
     next = null; 
    } 
} 

// Class used to store information for the linked list. 
static class List{ 
    TreeNode head; 
    int numItems; // number of nodes in the list 

    List(){ 
     head = null; 
     numItems = 0; 
     // initialize head and numItems 
    } 

    /** 
    * Inserts a node into the TreeNode linked list according to its frequencies 
    * position as it will be in a SORTED list. 
    * @param freq Frequency of a specific character. 
    * @return Returns the new TreeNode object that has been inserted. 
    */ 
    TreeNode insert(int freq){ 
     TreeNode previous, current, newNode; 
     int newFreq = freq; 
     numItems++; 

     previous = null; 
     current = head; 
     while((current != null) && (Integer.valueOf(newFreq).compareTo(Integer.valueOf(current.frequency)) > 0)){ 
      previous = current; 
      current = current.next; 
     } 
     if(previous == null){ 
      head = new TreeNode(newFreq); 
      return head; 

     } 
     else{ 
      newNode = new TreeNode(newFreq); 
      previous.next = newNode; 
      return newNode; 
     } 

    } 

Answer 1

Если голова должна быть создана только один раз, для этого нужен конструктор!

List() { 
    // initialize head here 
    head = new Node(); 
    head.next = head; 
    head.previous = head; 
} 

Кроме того, я думаю, что вы должны думать немного больше о том, что вы хотите узлы вашего списка, чтобы выглядеть. Правильно ли я понимаю, что вы пытаетесь создать двусвязный отсортированный список? Если это так, это, вероятно, наиболее полезно, если его узлы содержат объекты данных типа Comparabe, так что вы можете повторно использовать список для других целей. (Даже любитель должен был сделать свой тип данных общим Comparable<T>.)

Наконец, если вы пытаетесь сохранить частоты букв в списке, тогда тип данных должен иметь два поля: один для частоты буквы и один для письма, который он подсчитывает. И вам придется решить, какой из двух вы хотите использовать для сортировки: символ или частота. Я бы ожидал этого персонажа.

В любом случае попробуйте сделать снимок сначала из того, что вы хотели бы сделать, прежде чем начинать кодирование.

Answer 2

Позвольте мне принять удар на это:

Скажите, что вы сначала вставить TreeNode сек частот 5 и 4, в таком порядке. Как вы сказали, первая вставка будет проходить по назначению. Когда вы пытаетесь вставить TreeNode с частотой 4, while(...) будет обходить немедленно, что означает, что ток по-прежнему равен TreeNode с частотой 5, а предыдущий по-прежнему null. Согласно вашему коду, это приведет к тому, что связанный список создаст новый заголовок и перезапишет предыдущий.

Короче говоря, вы не назначаете правильно, если TreeNode с установленной вами частотой меньше частоты головы. Чтобы это исправить, что-то подобное должно быть добавлено после времени цикла:

if(current == head) { 
    newNode = new TreeNode(newFreq); 
    newNode.next = head; 
    head = newNode; 
} 

Кроме того, в «другой» части, если ваш, если/другое заявление, вы не назначая «следующее» поле newNode, так это заявление должно быть добавлено:

newNode.next = current;