Implementing a data structure with add, remove and contains methods

Question

I would like to create a data structure in java, basically I have researched this and the best structure would be a list to allow for duplicates, I would like to attempt this without the Java API. I don't know how to go about doing this or even starting this and have already done around 6 hours of research.

class WordStoringTest implements WordStore {
    private String[] words;

    public WordStoringTest(int n){
        words = new String[n];
    }
    public void add(String word) {
        int count = words.length+1;
        words = new String[count];
    }

    @Override
    public int count(String word) {
    int count =0;
        for(int i=0; i<words.length; i++){
            if(words[i].equals(word)){
                count++;
            }
        }
        return count;
    }

    @Override
    public void remove(String word) {
        // TODO Auto-generated method stub
    }
}

I don't know where to start please give me some guidance :) thanks

`I would like to attempt this without the java api`. The first question would be *why* ? Why go re-inventing the wheel when Java already has a a vast set of API's already pre-built. — Saif Asif, Dec 04 '13 at 19:11
Have you read [this question](http://stackoverflow.com/q/1781868/2970947)? Especially [this answer](http://stackoverflow.com/a/1781902/2970947). — Elliott Frisch, Dec 04 '13 at 19:11
not using the java api would help me increase my programming skills immensly and also give me a deeper understanding, also good for CV — Joshua Baron, Dec 04 '13 at 19:12
@SaifAsif Sometimes we need to build wheels to learn about wheels. — Zong, Dec 04 '13 at 19:13
@ZongZhengLi maybe, but wouldn't you agree that the *study* of wheels to make something beyond wheels is a far better thing? — Saif Asif, Dec 04 '13 at 19:18
As much as i am enjoying this dicussion of why i want to do it, is there any chance of showing me how to do it, unless you cant ;) — Joshua Baron, Dec 04 '13 at 19:20
If you're completely stuck, how about reading the source code of HashSet? Java is open-source. That said, if a Set is what you want, I don't really see the point of a count() method, since it will always return 0 or 1. You should familiarize with what the collections are before to think about how to implement them. — JB Nizet, Dec 04 '13 at 19:27
Oh yes @JoshuaBaron . Coming back to the OP. What issue are you facing? String[] would be good to begin with. Another thing, as far as I understand, you need an implementation of the Set interface, right ? ( as you want add,remove and contains) — Saif Asif, Dec 04 '13 at 19:28
If you read the hashset javadoc it says pretty much what you will need, a hashtable implementation and a list implementation — Kevin, Dec 04 '13 at 19:30
You still haven't received a good answer, so I'd suggest just conducting more research. Implementing a hashset is not difficult, but it doesn't seem like anyone wants to offer the effort to explain it considering there seems to be many articles out there. — Zong, Dec 04 '13 at 22:06

score 0 · Answer 1 · answered Dec 04 '13 at 19:29

There are inconsistencies in your code that make understanding it quite hard.... for example, you suggest a 'set' is the thing you want it to be, but then you have a count(...) method which indicates you expect multiple copies of the values in the 'set'. Traditional understanding is that members of a 'set' are not equals() to any other member of the set.

Additionally, what you have right now is just an array of data. This data array does not give you any advantages.... Things that would be advantages are (the sorts of things you get in java.util.*):

all values are unique
the ability to search the data is 'fast'
there is reduced maintenance because the data will grow/shrink as you need it.
the data is always sorted

... something has to be better than just a plain array.

Right now, not even you add() method works:

public void add(String word) {
    int count = words.length+1;
    words = new String[count];
}

The above method will delete all the data in the array by creating an empty one, and that's all.

My suggestion os for you to look through some standard examples for how things are done... consider looking at .... google basic java data structures.... I found this blog which looks useful

LHA · Answer 2 · 2013-12-04T19:38:33.810

0

How about this (Tested).

Note: This is like a Java List, NOT Set because there are duplicate.

This is not the best implementation. We can prepare array buffer for word array like initialCapacity.

public class WordStoringTest implements WordStore {

private String[] words;

public WordStoringTest() {
    this(0);
}

public WordStoringTest(int n) {
    this.words = new String[n];
}

public void add(String word) {
    String[] newWords = new String[this.words.length + 1];
    System.arraycopy(this.words, 0, newWords, 0, this.words.length);
    newWords[newWords.length - 1] = word;
    this.words = newWords;
}

// @Override
public int count(String word) {
    int count = 0;
    for (String w : this.words) {
        if (word.equals(w)) {
            count++;
        }
    }
    return count;
}

// @Override
public void remove(String word) {
    int pos = 0;
    String[] temp = this.words;
    while (pos < temp.length) {
        String w = temp[pos];
        if (w.equals(word)) {
            String[] newTemp = new String[temp.length - 1];
            if (pos == 0) {
                System.arraycopy(temp, 1, newTemp, 0, newTemp.length);
            } else if (pos == temp.length - 1) {
                System.arraycopy(temp, 0, newTemp, 0, newTemp.length);
            } else {
                System.arraycopy(temp, 0, newTemp, 0, pos);
                System.arraycopy(temp, pos + 1, newTemp, pos, newTemp.length - pos);
            }
            temp = newTemp;
        } else {
            pos++;
        }
    }
    this.words = temp;
}

}

edited Dec 04 '13 at 19:38

answered Dec 04 '13 at 19:33

LHA

9,398
8
46
85

Thanks Loc, what is a way to make the above more efficient, i have tried adding 10,000 words to the array and then add another 10,000 and it takes quite a while. im trying to improve my way of writing code to be more efficient, for example i have also been learning the best sort methods, please advise on making this data structure more efficient for large use – Joshua Baron Dec 04 '13 at 19:43
As I said in the comment, to make better performance. You need to prepare buffer for array of words here ( like new ArrayList(initialCapacity) ). For example. Instead of new String[this.words.length + 1], you have to code like this: new String[this.words.length + 1 + 100]; // 100 is buffer. Of course, this require some modifications in my code. – LHA Dec 04 '13 at 19:45
Instead of a fixed buffer size, array list implementations usually double the size of the allocation. This results in amortized O(1) add instead of O(n) as you have. – Zong Dec 04 '13 at 20:34
the thing is that array lists are part of the Java API – Joshua Baron Dec 04 '13 at 21:40
I have been looking into sets in java but dont really know how to implement them into my program in place of a StringBuffer – Joshua Baron Dec 07 '13 at 18:03

Implementing a data structure with add, remove and contains methods

2 Answers2