CODEWITHSUNDEEP
javaarraylistcomparatorcomparable
someone
someone

Reputation: 21

Adding an element to an ArrayList in the correct postition

I have a custom ArrayList interface that extends the Comparable class and is in ascending order. The class I'm working on is implementing this interface.

My problem is I need to edit the add method so that it will add an element to the ArrayList, have the List stay ordered, and make sure there are no duplicates.

It would be easy to do all this in separate methods, but that's out the question. I need the one method to do it all, so that when the method is called, (as long as it isn't a duplicate) the element is added in the correct position.

On top of that, to check the position of the index to insert the method to, I must use the compareTo() method inherited from the Comparable class. Only problem is I have to implement my own compareTo() method in the class I'm working on. I've looked all over, and I'm confused on how to go about that for this certain class.

Here's my code so far:

    public void add(E item) throws IndexOutOfBoundsException {

        if (contains(item)) {
            throw new IllegalArgumentException("This is a duplicate!");
        }
        //here is where I need the implementation to add the item to the array, in order

    }

Then here is my compareTo() method:

        public int compareTo(E item) {

        if () {
          return -1;
        } 
        else if () {
          return 1;
        } 
        else {
            return 0;

        }
      }

Upvotes: 2

Views: 3884

Answers (4)

Jeff Foster
Jeff Foster

Reputation: 44706

Adding an element in the right position is the same as failing to do binary search and recording the last position you compared.

Check out the documentation for Arrays.binarySearch. Hopefully this will give enough information to implement it. Your implementation of comparable should just be the same as you would use for sorting. Here's the relevant excerpt from the documentation:

index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Upvotes: 0

Duncan
Duncan

Reputation: 990

You don't give that much information. If what you truly are implementing is an ArrayList like data structure, then you first need to see if the array is large enough to add a new item. If not, you need to create a new array. In the first case, you need to find the location to enter the new element, shift everything from that position on down one, and then add the element. For the second case, you can "merge" the old list with the new element (that is, keep adding from the old list until the location where the new element should go comes up, add the new element, and continue). Another question I have: where is the compareTo(Object o) being put? If you are putting in the ArrayList class, that's rather pointless since you don't really want to compare arrays. If it's in the class being stored in the ArrayList, you want to return -1 if the this object comes before the object passed in, a -1 if the this object comes after, and 0 if they are equal. If you can choose your data structure, you might want to consider a linked list: they are very easy to add to and remove from.

If you are extending the ArrayList class, then this is super (pun intended) easy. In your add method, you have to determine the location to add the element, then call the super.add(int loc) method

Upvotes: 0

Flash
Flash

Reputation: 16703

One way to do this is to first check if

myArrayList.contains(item)

and then if not, just insert and re-sort your array:

myArrayList.add(item);
Collections.sort(myArrayList);

Note that in general, if you want to maintain a sorted set without duplicates, there are better data structures than ArrayList.

Upvotes: 2

Daniel
Daniel

Reputation: 10235

What about a TreeSet? It seems to have the behaviour you're looking for.

Upvotes: 0

Related Questions