Inserting a string into a sorted array

Question

I'm having some problems figuring out how to do get this program to work in Java. I'm supposed to have a class WordList:

public class WordList{
    private int size; //number of words in array
    private String array1[]; //array of words
    private int capacity; // how big the array is supposed to be

And we're supposed to have two constructors: First one:

public WordList(int capacity){
    this.array1 = new String[capacity]; //makes a new array of specified capacity
    this.capacity = capacity; //sets the capacity
    this.size = 0; //sets the size of array (i.e. # of words) to 0
}

Second one:

public WordList (String[] arrayOfWords){
    this.capacity = 2 * arrayOfWords.length; //makes the capacity of array twice the # of words in input array
    this.array1 = new String[capacity]; //makes a new array
    this.size = arrayOfWords.length; //sets the # of words in array
    for (int i = 0; i < arrayOfWords.length; i++){ //loops through array
        this.insert(arrayOfWords[i]); //inserts the words (sorted into our array)
}
}

and finally an insert method. I think the main problem is here. I don't know if my two constructors are correct, but I'm 110% sure there's something wrong here:

public void insert(String newword){


    for (int i = 0; i < size; i++){
        int l = newword.compareTo(array1[i]);
        if (l > 0)
            continue; // means that the word we're inserting is after
        if (l < 0){
            for (int j = size; j > i; j--){
                array1[j] = array1[j-1]; //shifts all array elements over by one - starting at end of array to avoid over writing anything
            }
            array1[i] = newword;//inserts the word
        }
        if (l == 0)
            return;//doesn't do anything if word is already in list
    }
    }

Essentially it's supposed to insert the word provided into an already sorted array of words and keep the list sorted. The program just crashes. Any ideas on what might be wrong?

NullPointerException ????????

Biu
– Biu

2015-01-21 01:21:04 +00:00
Commented Jan 21, 2015 at 1:21 — Biu
– Biu, Commented Jan 21, 2015 at 1:21

Yang Yu · Accepted Answer · 2015-01-21 01:56:58Z

1

In the for loop, try initialize j to size-1 instead of size. Also, please notice that while the program will run if you don't check the capacity in insert, you will lose the last element when inserting to a full array. Hope this helps.

answered Jan 21, 2015 at 1:56

Yang Yu

3562 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user949300 · Accepted Answer · 2015-01-21 01:32:17Z

0

Is this homework? I think it is, so I'll just give some ideas, not complete answers.

Since the array is sorted, you could use Arrays.binarySearch() to find its location for insert()
I know you build in some extra space in the constructor, but if you insert enough items, your array will need to grow. Insert will need to compare size and capacity.
Think about your "shift everything right" code. Write down on paper ( or use index cards) an example initial array, do a gedanken insert, and go through your code one loop at a time updating the array. You likely have a bug there. Just saying... :-)
Can you use System.arraycopy()? If so, use that when inserting or enlarging your array.

answered Jan 21, 2015 at 1:32

user949300

15.7k7 gold badges39 silver badges69 bronze badges

Collectives™ on Stack Overflow

Inserting a string into a sorted array

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related