Adding an element to an ArrayList in the correct postition

Question

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;

        }
      }

List has a contains(Object o) method that does what your loop is doing. It makes the code simpler. — MeBigFatGuy
– MeBigFatGuy, Commented Apr 6, 2011 at 3:27
What part do you not understand? We shouldn't be doing your homework for you. :) You're going to have to know this stuff come exam time. — squawknull
– squawknull, Commented Apr 6, 2011 at 3:27
using == means, that the exact same object is in the list, not that two objects are equals. use .equals(Object o). -- or just use contains(Object o) — MeBigFatGuy
– MeBigFatGuy, Commented Apr 6, 2011 at 3:28
1) I am assuming that you have a class extending ArrayList. 2) what are the items you are adding? how do you compare/sort them? — Aleadam
– Aleadam, Commented Apr 6, 2011 at 3:30

Flash · Accepted Answer · 2011-04-06 03:36:58Z

2

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.

answered Apr 6, 2011 at 3:36

Flash

16.9k15 gold badges74 silver badges100 bronze badges

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

1 Comment

someone Over a year ago

thanks for the input. i changed the duplicate check to use the contains() method. I actually had that earlier. the only problem is i need the method to insert it first, and not have to sort it. it should stay sorted after the method is called.

Daniel · Accepted Answer · 2011-04-06 03:29:38Z

0

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

answered Apr 6, 2011 at 3:29

Daniel

10.3k3 gold badges48 silver badges62 bronze badges

Comments

Duncan · Accepted Answer · 2011-04-06 08:09:07Z

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

Jeff Foster · Accepted Answer · 2011-04-06 08:15:12Z

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.

Collectives™ on Stack Overflow

Adding an element to an ArrayList in the correct postition

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related