1

hello im trying to implement a Linked list in java. As this is a homework assignment I am not allowed to use the built in LinkedList from java.

Currently I have implemented my Node class

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


   }
}

and my "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++;
}

Im having trouble with implementing my add method correctly, as it has to check the list, for wether the word allready exists and if do not exists, add it to the list and store it alphabetic. Ive been working on a while loop, but cant seem to get it to work.

Edit: Ive been trying to print the list but it wont print more than the first added word public void print() {

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

    }  
}

Any help is appreciated

Improve this question
3
  • Post the loop you have written so far. We can try to help you on it. Commented Dec 25, 2010 at 16:06
  • public void add(String word){ WordNode temp; int size = 0 while(temp.getNext()!=null){ temp=temp.getNext(); } temp.setNext(new WordNode(word, null)); size++; Commented Dec 25, 2010 at 16:13
  • A linked list is a great datastructure for adding and removing items quickly O(1). If your HW requires you to first check the list to see if the word has already been added to the linked list then you may be using the wrong datastructure. It sounds like you need a combination of a hashtable (to find if it exists) and a linked list (to store alphabetically). Commented Dec 25, 2010 at 16:15

5 Answers 5

Reset to default
2

Your add method is wrong. You're taking the root node and setting its next value to the new node. So you will never have any more than 2 nodes. And if you ever have 0, it will probably crash due to a null pointer.

What you want to do is set a current value to the root node, then continue getting the next node until that node is null. Then set the node.

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

You need to keep the instance of the previous node so you can set the next value. Since this would cause a problem if there are no nodes to begin with, there needs to be some extra logic to handle a root node differently. If you'll never have 0 nodes, then you can remove that portion.

If you also need to check the values of the variables in order to see if it's there, you can add something to the while loop that looks at the current value and sees if it is equal to the current word you're looking for.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thx for ur fast response, ive added current.getWord != word , to the while loop. But im wondering, shouldnt there be a case of when the word exists in list, where i up the freq of that word, and nother case where is dont exists where the length of the list is increased
1 
WordNode current = Link;
while (current != null) {
   //check stuff on current word
   current = current.getNext();
}
Improve this answer

Comments

1

Without your loop code, it will be hard to help you with your specific problem. However, just to give you a bit of a hint, based on the instructions you don't actually have to search every node to find the word. This will give you the opportunity to optimize your code a bit because as soon as you hit a word that should come after the current word alphabetically, then you can stop looking and add the word to the list immediately before the current word.

For instance, if the word you're adding is "badger" and your words list are 

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

You know that beehive should come after badger so you don't have to keep looking. What you will need to implement is a method that can do alphabetical comparison letter-by-letter, but I'll leave that to you ;-)

Improve this answer

Comments

1

Assuming that you always insert in alphabetical order it should look something like this:

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++;
}
Improve this answer

8 Comments

when im removing nodes from the list , ill use the same from add WordNode wn = Link; WordNode prevNode = null; while(wn != null){ if(word.equals(wn.getWord())) prevNode.setNext(word.getNext()) but it dosnt seem to work, I figure that when I remove a Link the prev link must point to link after the one im removing ? and ofc size--
Yeah, that's right. prevNode should be set to wn's next node, that is prevNode.setNext(wn.getNext()) and size-- as you suggested. If that's not working there must be some other problem in the code.
ive got my remove method to work now. But the add method, is "buggy". My first added word is always the first in the list. So if I had "cat" to begin and then later "apple" - "apple" isnt added to my list. unless my print method is bugged.. public void print() { WordNode current = Link; while (current != null) { System.out.println(current.getWord()+","+current.getFreq(current.getWord())); current =current.getNext(); } }
I see. Yeah, there is a bug in the else if(word.compareTo... branch in the place where I fix the next link of the previous node. If prevNode is null then Link should be set to point to the newNode. Hope that fixes it.
if(prevNode == null){ Link.setNext(newNode), now it prints , but the order is wrong. My first word is "orange" and my next is "apple" - and it prints "orange" and then "apple" ;(
|
0

Use this code :

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

    }
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.