Подсчет частоты слов - связанный список

Question

Я пытаюсь вставить слова в связанный список, потому что я хочу подсчитать, сколько раз слово появляется в списке, а затем вернуть слова в порядке наивысшей частоты на наименьшую. Тем не менее, я продолжаю получать ошибку утверждения. Вот мои insert, getCount и getWords методы. Кажется, insert и getCount доставляют мне проблемы.

public class Frequency<E extends Comparable<E>> implements Iterable<E>{
    private Node first; //starting node
    private Node parent;    //parent of currently processed node
    private int N;  //number of words


    /**
     * Linked List Node
     */
    private class Node{
        private E key;
        private int count;
        private Node next;

        Node(E e){
           key = e;
           count = 1;
           next = null;
        }

        Node(E e, Node r){
            key = e;
            count = 1;
            next = r;
         }

        @Override 
        public String toString(){
            return "("+key +","+count+")";
        }
    }

   /**
    * Inserts a word into linked list
    * @param key to be inserted 
    * @return true if the key is inserted successfully.
    */
    public boolean insert(E key){
        if (first == null || first.key != key) {
            first = new Node(key, first);
        } else {
            Node curr = first;
            while (curr.next != null) {
                curr.next = new Node(key, first.next);
            }
            curr = curr.next;
            N++;
        }
        return true;
    }

/**
     * 
     * @param key is the key to be searched for
     * @return frequency of the key. Returns -1 if key does not exist
     * 
     */
    public int getCount(E key){
        // go through the linked list and count the number of times each word appears
        // return the count of the word that is being called.
        if (key == null) {
            return -1;
        }
        int N = 0;
        Node curr = first;
        while (curr != null) {
            if (curr.key.equals(key)) {
                N++;
            }
            curr = curr.next;
        }
        return N;   
    }
    /**
     * Returns the first n words and count
     * @param n number of words to be returned
     * @return first n words in (word, count) format
     */
    public String getWords(int n){
        Node curr = first;
        for (int i = 1; i < n; i++) {
            curr = curr.next;
        }
        return curr.toString();
    }


    /**
     * Frequency List iterator
     */
    @Override
    public Iterator<E> iterator() {
        return new FreqIterator();
    }
    /**
     * 
     * Frequency List iterator class
     *
     */
    private class FreqIterator implements Iterator<E>{

        @Override
        public boolean hasNext() {
            Node curr = first;
            if(curr != null) {
                return true;
            }
            return false;
        }

        @Override
        public E next() {
            Node curr = first;
            if(hasNext() == false) {
                return null;
            }
            E item = curr.key;
            curr = curr.next;
            return item;
        }
    }
}

EDIT

Это мой тест для вставки одного и того же слова дважды в связанный список. Я хочу, чтобы результат был 2, но я на самом деле получаю 1. Я предполагаю, что это связано с моим insert методом.

    @Test
    public void testInsert() {
        Frequency<String> freq = new Frequency<>();
        freq.insert("dog");
        freq.insert("dog");
        String answer = freq.getWords(1);
        assertEquals("(dog,2)", answer);
    }

Answer 1

Это не работает, потому что в вашем getCount(E key) вы никогда не проверяете, равен ли переданный в key узел curr при итерации по нему.

Сделайте это небольшое изменение в методе:

public int getCount(E key) {
    if (key == null) {
        return -1;
    }
    int N = 0;
    Node curr = first;
    while (curr != null) {
        if (curr.key.equals(key)) {  // change made here 
            N++;
        }
        curr = curr.next;
    }
    return N;
}

---

Согласно редактированию, в insert(E key) есть логическая ошибка. Вам нужно выполнить итерацию, чтобы найти последний элемент в списке , а затем присвоить следующую ссылку вновь созданному узлу .

public boolean insert(E key) {
    if (first == null || first.key != key) {
        first = new Node(key, first);
    } else {
        Node curr = first;
        while (curr.next != null) {  // iterate till the end of the list
            curr = curr.next; 
        }
        curr.next = new Node(key);   // point last node's next ref to new node
        N++;
    }
    return true;
}