Need better data structure implementation Java

[prakash2813]

Hello there,
I am writing a data structure and restricted not to use any API or collection.
I have written a Sorted Linkedlist, which stores strings in ascending order.

Basically I am writing a dictionary, which can be easier to implement by Map, HashMap or Dictionary provided by Collection API, but I can't.

So I need to store the word in ascending order and store their variations(or consider meanings) also in ascending order.
I can use same Sorted LinkedList to do the same. One Linkedlist for words and second for their variations.
The problem is when I delete the word, it should also delete their variations(meanings) from list.
Currently it is not possible to do, because the position of word and their variations are not same due to sorting.

Any help would be appreciated.

[rubberman]

Write an insertion sort routine, based upon bsearch and qsort algorithms. Yes, they are C code, but are easily translated into Java. Basically you use an array - presize it to your expected maximum size + some space for overflow. When you do need to resize it, double the size. So, in your structure/class, you will have the string array, a member that is the maximum size of the array, and the current last element position of the array (starts with 0). As you add members you will find the insertion point, move the following elements down one member, put the new string at that position, and increase index of the current last member, after you have determined that you don't need to resize the array. If you do, then before you insert the new element you will resize the array, copy the old array elements to the new one, delete the old array, and assign the new array to the old member variable.

This isn't a large amount of code, but it is enough to show you are thinking about how to deal with this problem efficiently. I wrote such a routine in C++ some 20 years ago and it was awesomely efficient! It is still used today in commercial software that deals with lists which are over 1 million elements in size.

[rubberman]

Note that bsearch/qsort use binary search algorithms (see Knuth Vol. 3 - Sorting and Searching Algorithms) which means that finding the insertion point for a 1 million element array is, at max, only 4 searches longer than 64K elements, and 1 billion? Only 10 more comparisons than 1 million! Binary math - ain't it great? :-)

[prakash2813]

can you please share the c code? I understood about string array but still I am confused about integrating binary search, qsort and insertion algorithm.

[rubberman]

Also note, that forwhatever it's worth, sorted linked lists are incredibly inefficient. You basically have to navigate the entire array (doing a comparison at each node) to find the insertion point. Simple to write, but VERY slow! Another thing you can do with either arrays or linked lists (assuming you keep a pointer to the last element of the list) is a head/tail optimization. Before you search, look to see if the inserted item goes at the head or tail. Worst case? 2 comparisons. We found that doing this for creating large sorted lists from sorted input (such as database queries that use an "order by" clause) gave us a 2 orders-of-magnitude speedup - that is 100x faster! When I implemented that in our code our QA people called me to say there was a problem with the new code because it was just so much faster! Yes, the results were correct. The speedup was just not expected! Stuff that could take an hour took a few seconds... Gee, what a shame!

[rubberman]

Final (hopefully) note. After re-reading your original post, you need to have associated meanings of a word or phrase. This isn't hard. I'm not giving you the answer, but propose a solution and I will critique it - after all, this IS a school exercise, right?