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
– Saif Asif, Commented Dec 4, 2013 at 19:11
@SaifAsif Sometimes we need to build wheels to learn about wheels. — Zong
– Zong, Commented Dec 4, 2013 at 19:13
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
– JB Nizet, Commented Dec 4, 2013 at 19:27

rolfl · Accepted Answer · 2013-12-04 19:29:41Z

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 · Accepted Answer · 2013-12-04 19:38:33Z

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

}

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
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.
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.
I have been looking into sets in java but dont really know how to implement them into my program in place of a StringBuffer

Collectives™ on Stack Overflow

Implementing a data structure with add, remove and contains methods

2 Answers 2

Comments

5 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Linked

Related