In Java how can I check if an object is in a linked list?

Question

Below is my class. The insertSymbol method is supposed to add an object to the linked list which is then added to a hash table. But when I print the contents of the hash table it has double entries. I tried to correct this by using "if(temp.contains(value)){return;}" but it isn't working. I read that I need to use @override in a couple of places. Could anyone help me know how and where to use the overrides? Thank you!

import java.util.*;

public class Semantic {
    String currentScope;
    Stack theStack = new Stack();
    HashMap<String, LinkedList> SymbolTable= new HashMap<String, LinkedList>();


    public void insertSymbol(String key, SymbolTableItem value){
        LinkedList<SymbolTableItem> temp = new LinkedList<SymbolTableItem>();
        if(SymbolTable.get(key) == null){
            temp.addLast(value);
            SymbolTable.put(key, temp);
        }else{
            temp = SymbolTable.get(key);
            if(temp.contains(value)){
                return;
            }else{
                temp.addLast(value);
                SymbolTable.put(key, temp);
            }
        }
    }   

    public String printValues(){
        return SymbolTable.toString();
    }

    public boolean isBoolean(){
        return true;
    }

    public boolean isTypeMatching(){
        return true;
    }

    public void stackPush(String theString){
        theStack.add(theString);
    }

}

You should use lower case for variables like "symbolTable" because we are all used to reading Java that way. Its the standard convention. — Lee Meador, Jul 08 '13 at 18:52
Btw, what you can do instead of `map.get(key) != null` is to use `map.containsKey(key)` — Erik Pragt, Jul 08 '13 at 18:57
Thank you for the insight. It's good to learn these things. Some of the identifiers, such as SymbolTable, are given by the professor, though, so I try to use them. — bstrong, Jul 08 '13 at 19:09
Sad when the professor doesn't teach you to follow such a strongly followed convention. Mostly only C# people try to capitalize using a different set of conventions. — Lee Meador, Jul 08 '13 at 19:14

Erik Pragt · Answer 1 · 2013-07-08T19:17:06.027

5

You have multiple options here. You'll need at least to add an equals (and therefor also a hashcode) method to your class.

However, if you want your collection to only contain unique items, why not use a Set instead?

If you still want to use a List, you can use your current approach, it just that the characteristics of a Set are that all items in a Set are unique, so a Set might make sense here.

Adding an equals method can quite easily be done. Apache Equalsbuilder is a good approach in this.

edited Jul 08 '13 at 19:17

answered Jul 08 '13 at 18:51

Erik Pragt

13,513
11
58
64

If you want to keep the List and don't know how to add equal/hash methods, here is a similar question: http://stackoverflow.com/questions/27581/overriding-equals-and-hashcode-in-java – Brinnis Jul 08 '13 at 18:54
The last sentence before the list of options only refers to the 1st option. That's a tiny bit confusing. Not worthy of changing your answer. – Lee Meador Jul 08 '13 at 19:12

Lee Meador · Accepted Answer · 2013-07-08T19:06:09.887

You don't need the 2nd line when you add a new value with the same key:

temp.addLast(value);
SymbolTable.put(key, temp); // <-- Not needed. Its already in there.

Let me explain something that @ErikPragt alludes to regarding this code:

if(temp.contains(value)){

What do you suppose that means?

If you look in the javadocs for LinkedList you will find that if a value in the list is non-null, it uses the equals() method on the value object to see if the list element is the same.

What that means, in your case, is that your class SymbolTableItem needs an equals() method that will compare two of these objects to see if they are the same, whatever that means in your case.

Lets assume the instances will be considered the same if the names are the same. You will need a method like this in the 'SymbolTableItem` class:

@Overrides
public boolean equals(Object that) {
    if (that == null) {
        return false;
    }
    if (this.getName() == null) {
        return that.getName() == null;
    }
    return this.getName().equals(that.getName());
}

It it depends on more fields, the equals will be correspondingly more complex.

NOTE: One more thing. If you add an equals method to a class, it is good programming practice to add a hashcode() method too. The rule is that if two instances are equal, they should have the same hashcode and if not equal they don't have to be different hashcodes but it would be very nice if they did.

If you use your existing code where only equals is used, you don't need a hashcode, stricly. But if you don't add a hashcode it could be a problem someday. Maybe today.

In the case where the name is all that matters, your hashcode could just return: this.getName().hashcode().

Again, if there are more things to compare to tell if they are equal, the hashcode method will be more complex.

It's a good remark, but this is not really an answer to his question, right? — Erik Pragt, Jul 08 '13 at 18:58
His question is where to use @overrides. I suppose nobody is answering that because its fair game to offer any corrections. — Lee Meador, Jul 08 '13 at 18:59
I guess the @overrides are probably for the equals and hashcode method. Not really needed, but when going for option 2, it might be useful. — Erik Pragt, Jul 08 '13 at 19:01

In Java how can I check if an object is in a linked list?

2 Answers2