java - 实现链表 (java)

Question

你好，我正在尝试在 java 中实现链表。由于这是一项家庭作业，我不允许使用 java 中的内置 LinkedList。

目前我已经实现了我的 Node 类

public class WordNode
{
    private String word;
    private int freq;
    private WordNode next;

/**
 * Constructor for objects of class WordNode
 */
public WordNode(String word, WordNode next )
{
    this.word = word;
    this.next = next;
    freq = 1;

}
/**
 * Constructor for objects of class WordNode
 */
public WordNode(String word)
{
    this(word, null);
}
/**
 * 
 */
public String getWord()
{
    return word;
}
/**
 * 
 */
public int getFreq(String word)
{
    return freq;
}
/**
 * 
 */
public WordNode getNext()
{
    return next;
}
 /**
 * 
 */
public void setNext(WordNode n)
{
    next = n;
}
/**
 * 
 */
public void increment()
{
    freq++;


   }
}

和我的“LinkedList”

public class Dictionary
{
    private WordNode Link;
    private int size;

    /**
     * Constructor for objects of class Dictionary
     */
public Dictionary(String L)
{
    Link = new WordNode(L);
    size = 1;
}

/**
 * Return true if the list is empty, otherwise false
 * 
 * 
 * @return 
 */
public boolean isEmpty()
{
    return Link == null;

}
/**
 * Return the length of the list
 * 
 * 
 * @return 
 */
public int getSize()
{
    return size;
}
/** 
 * Add a word to the list if it isn't already present. Otherwise 
 * increase the frequency of the occurrence of the word. 
 * @param word The word to add to the dictionary. 
 */
public void add(String word)
{

    Link.setNext(new WordNode(word, Link.getNext()) );
    size++;
}

我在正确实现我的添加方法时遇到了问题，因为它必须检查列表，以了解单词 allready 是否存在，如果不存在，则将其添加到列表中并按字母顺序存储。我一直在研究 while 循环，但似乎无法让它工作。

编辑:我一直在尝试打印列表，但它不会打印超过第一个添加的单词公共(public)无效打印(){

    WordNode wn = Link;
    int size = 0;
    while(wn != null && size <= getSize()){
        System.out.println(wn.getWord()+","+wn.getFreq(wn.getWord()));
        size++;

    }  
} 

感谢任何帮助

Answer 1

你的添加方法是错误的。您正在获取根节点并将其下一个值设置为新节点。所以你永远不会有超过 2 个节点。如果你有 0，它可能会由于空指针而崩溃。

您要做的是为根节点设置一个当前值，然后继续获取下一个节点，直到该节点为空。然后设置节点。

WordNode current = Link;

// Check if there's no root node
if (current == null) {
    Link = new WordNode(word);
} else {
    // Now that the edge case is gone, move to the rest of the list
    while (current.getNext() != null) {
        /* Additional checking of the current node would go here... */
        current = current.getNext();
    }
    // At the last element, at then new word to the end of this node
    current.setNext(new WordNode(word));
}

您需要保留前一个节点的实例，以便您可以设置下一个值。如果没有节点开始，这会导致问题，因此需要一些额外的逻辑来以不同方式处理根节点。如果您永远不会有 0 个节点，那么您可以删除该部分。

如果您还需要检查变量的值以查看它是否存在，您可以在 while 循环中添加一些内容来查看当前值并查看它是否等于您正在查找的当前单词为。