CODEWITHSUNDEEP
javadata-structureslinked-list
Daniel D
Daniel D

Reputation: 409

remove() method of a linked list

I am taking a programming class I have the following assignment.

Write a menu driven program that either accepts words and their meanings, or displays the list of words in lexicographical order (i.e. as in a dictionary). When an entry is to be added to the dictionary you must first enter the word as one string, and then enter the meaning as separate string. Another requirement - from time to time words become obsolete. When this happens, such word must be removed from the dictionary.

Use the JOptionPane class to enter the information.

Use the concept of linked list to carryout this exercise. You will need at minimum the following classes:

For the output, the program should produce two scrollable lists:

So far, I have everything coded except for the remove method, and I am not sure how to code that, so could anyone help me please. I coded the add method already, but now I don't know where to begin with the remove method in my WordList class. My classes are below.

WordList Class:

public class WordList {

WordMeaningNode list;

WordList() {
    list = null;
}

void add(WordMeaning w)// In alphabetical order
{
    WordMeaningNode temp = new WordMeaningNode(w);

    if (list == null)
        list = temp;
    else
    {
        WordMeaningNode aux = list;
        WordMeaningNode back = null;
        boolean found = false;

        while(aux != null && !found)
            if( temp.getWordMeaning().getName().compareTo(aux.getWordMeaning().getName()) < 0 )
                found = true;
            else
            {
                back = aux;
                aux = aux.next;
            }

        temp.next = aux;
        if (back == null)
            list = temp;
        else
            back.next = temp;
    }
}

boolean listIsEmpty() {
    boolean empty;
    if (list == null) {
        empty = true;
    } else {
        empty = false;
    }

    return empty;
}

public String toString()
{
    String result = "";
    int count = 0;
    WordMeaningNode current = list;

    while (current != null)
    {
        count++;
        result += current.getWordMeaning().getName() + "\n" + "\t" + current.getWordMeaning().getDefinition();
        current = current.next;
    }

    return result + "\nThe number of words is : " + count;
}
}

I tried to use the same method format for the remove method as I did for the add method, but didn't really work, or I did it wrong.

Upvotes: 4

Views: 1886

Answers (2)

Alex Salauyou
Alex Salauyou

Reputation: 14338

To remove an item from LinkedList, you should iterate over its nodes. Then, if occurence found, connect previous and next node, setting previous.next = next:

boolean remove(String word) {

    if (list == null)   // list is empty
        return false;

    WordMeaningNode n = list;
    WordMeaningNode prev = null;

    do {
       if (n.wordMeaning.name.equals(word)) {  // word found
           if (prev != null) {
              prev.next = n.next;   // connect previous to next
           } else {
              list = list.next;     // connect head to next
           }
           return true;
       }
       prev = n;
       n = n.next;
    } while (n != null);   // repeat till the end of a list
    return false;
}

In main code, change the piece of case 2:

if (diction.remove(word)) {
    obsolete.add(new WordMeaning(word, " "));
    // notify about deletion
} else {
    // notify that word don't exist.
}

because you really don't need NullPointerException here.

Upvotes: 4

Olivier Croisier
Olivier Croisier

Reputation: 6149

To remove an element from your list, you need to find the element just before the one to remove, and set its next reference to the element after the one to remove.

You will have some (not mutually exclusive) corner cases to pay attention to :

  • If the element to remove is the first (then, the first node of WordList should be set to the element after the one to remove)
  • If the element to remove if the last one in the list (then you will have to set the previous element's next reference to null)

Also, I see you need to keep a list of removed items, so don't forget to keep a reference on the removed item during the process, and to add it to your list of obsolete words.

Upvotes: 0

Related Questions