实现链表（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++;
}

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

编辑：我一直在尝试打印列表，但它不会打印比第一个添加的单词更多的内容 公共无效打印（） {

    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 循环中添加一些内容，以查看当前值并查看它是否等于您正在查找的当前单词。

Answer 2

WordNode current = Link;
while (current != null) {
   //check stuff on current word
   current = current.getNext();
}

Answer 3

如果没有循环代码，将很难帮助您解决特定问题。但是，只是为了给您一些提示，根据说明，您实际上不必搜索每个节点来查找该单词。这将使您有机会稍微优化您的代码，因为一旦您遇到按字母顺序排列在当前单词之后的单词，您就可以停止查找并将该单词添加到紧邻当前单词之前的列表中。

例如，如果您要添加的单词是“badger”，并且您的单词列表是“

apple-->avocado-->beehive-->...

beehive”，那么您就知道“beehive”应该出现在“badger”之后，这样您就不必继续寻找。您需要实现的是一种可以逐字母进行字母比较的方法，但我将把它留给您;-)

Answer 4

假设您始终按字母顺序插入，它应该看起来像这样：

public void add(String word){
  WordNode wn = Link;
  WordNode prevNode = null;
  while(wn != null){
    if(word.equals(wn.getWord())){
      //match found, increment frequency and finish
      wn.increment();
      return;
    }else if(word.compareTo(wn.getWord) < 0){
      //the word to add should come before the
      //word in the current WordNode.

      //Create new link for the new word,
      //with current WordNode set as the next link
      WordNode newNode = new WordNode(word, wn)

      //Fix next link of the previous node to point
      //to the new node
      if(prevNode != null){
        prevNode.setNext(newNode);
      }else{
        Link = newNode;
      }

      //increase list size and we are finished
      size++;
      return;
    }else{
      //try next node
      prevNode = wn;
      wn = wn.getNext();
    }
  }

  //If we got here it means that the new word 
  //should be added to the end of the list.
  WordNode newNode = new WordNode(word);
  if(prevNode == null){
    //if list was originally empty
    Link = newNode;
  }else{
    //else append it to the end of existing list
    prevNode.setNext(newNode);
  }
  //increment size and finish
  size++;
}

Answer 5

使用此代码：

class NodeClass {

    static Node head;
    static class Node {
        int data;
        Node next;
        //constractor
        Node(int d) {
            data=d;
            next=null;
        }
    }

    static void printList(Node node ) {
        System.out.println("Printing list ");
        while(node!=null){
            System.out.println(node.data);
            node=node.next;
        }

    }

    static void push(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    static void addInLast(int data) {
        Node node = new Node(data);
        Node n = head;
        while(n.next!=null){
            n= n.next;
        }
        n.next = node;
        node.next =  null;

    }

    public static void main (String[] args) {
        NodeClass linklistShow = new NodeClass();
        linklistShow.head = new Node(1);
        Node f2 = new Node(2);
        Node f3 = new Node(3);
        linklistShow.head.next = f2;
        f2.next =f3;
        printList(linklistShow.head);
        push(6);
        addInLast(11);
        printList(linklistShow.head);

    }
}