Insert element to ArrayList with ascending order and no duplicate elements.

Question

I have a homework assignment where I need to insert or add new elemment into ArrayList<Interger> with follow condition:

1. Element must ascending order.

2. No duplicate elements in ArrayList<Integer>

3. insert method run in O(n) times.

Here is my insert method for check duplicate element before add new element.

    public void insert(int x){
            //effect: Check duplicate elements if not x to the elements;
                boolean found = false;
                if(super.size()!=0){
                    for(int i=0; i<super.size(); i++){
                        if(super.get(i)==x){
                            found = true;
                        }
                    }
                }
                if(found){ return; }
                else{ super.add(x);  }
        }

how can i do it? Thank you.

addition

here is my class names InSetExtra

public class IntSetExtra extends ArrayList<Integer> {


    private static final long serialVersionUID = 1L;

    public IntSetExtra(){
        super();
    }

    public void insert(int x){
        //effect: Check duplicate elements if not x to the elements;
            boolean found = false;
            if(super.size()!=0){
                for(int i=0; i<super.size(); i++){
                    if(super.get(i)==x){
                        found = true;
                    }
                }
            }
            if(found){ return; }
            else{ super.add(x);  }
    }

    public String toString(){
        //effect: return string of this.
        if(super.size()==0) return "[]";
        String s = "[" + super.get(0).toString();
        for(int i=1; i<super.size(); i++){
            s += ", " + super.get(i).toString();
        }
        return s += "]";
    }

}

and i need to insert a large size of elements, for example:

IntSetExtra a, b;

    a = new IntSetExtra();
    b = new IntSetExtra();

    for(int i=0; i<30000; i++){ a.insert(2*i); }
    for(int i=0; i<30000; i++){ a.insert(i); }

    System.out.println("a sub = "+a.toString().substring(0, 37));

what should i do?

ps. my instructor need to use only ArrayList

Answer 1

I use TreeSet when i want to add non-duplicate elements to a Set. Give it a shot!

Answer 2

Since this is homework, I assume you must use an ArrayList and implement the logic manually (rather than using TreeSet as the obvious solution). I think the following hint should be enough for you to finalize the implementation :-)

If the array elements are already in ascending order, you don't need to loop through the whole array. Just search for the first element which is equal to or greater than the new element. If equal, you have a dupe. If greater, insert the new element before it and you are done. If all existing elements are smaller than the new one, insert it at the end.

This will give you O(n) performance as required. However, as an improvement, you may consider using binary search instead of linear.

Answer 3

Why don't you use TreeSet: http://download.oracle.com/javase/1.4.2/docs/api/java/util/TreeSet.html

As this is HomeWork question and ArrayList need to be used I am changing my answer.

You will need to use traverse linearly and compare elements. Take action accordingly:

• if new element is equal to current element do nothing and return.
• if new element is greater than current element traverse to next.
• if new element is smaller than current element add element at this index and return.
• if end of list is reached while traversing then add new element and return. (This will add element at the end of list)

I assume here that all elements are added using above algorithm. So ArrayList is always sorted :).

here is code:

public void insert(int x) {
    for (int i = 0; i < size(); i++) {
        if (x == get(i)) {
            // if new element is equal to current element do nothing and
            // return
            return;
        } else if (x > get(i)) {
            // if new element is greater than current element traverse to
            // next.
            continue;
        }
        // code reaches here if new element is smaller than current element
        // add element at this index and return.
        add(i, x);
        return;
    }
    // if end of list is reached while traversing then add new element and
    // return. (This will add element at the end of list)
    add(x);
}

Hope this helps.

Answer 4

A list is a list and not a set, and if it behaves like a set, it breaks its contract. Inserting in a TreeSet should be O(log(n)) or so...

Answer 5

Here is how I would do it: (Explanation in comments)

public void insert(int x){
    // loop through all elements
    for (int i = 0; i < size(); i++) {
        // if the element you are looking at is smaller than x, 
        // go to the next element
        if (get(i) < x) continue;
        // if the element equals x, return, because we don't add duplicates
        if (get(i) == x) return;
        // otherwise, we have found the location to add x
        add(i, x);
        return;
    }
    // we looked through all of the elements, and they were all
    // smaller than x, so we add ax to the end of the list
    add(x);
}

The current solution that you posted looks mostly correct, except for the fact that it will not save elements in ascending order.

Answer 6

Create a class for the new data structure.

Whenever a data value is added, perform a binary search on the arraylist to ensure that the data value is not already present. If it is already present, raise an exception. If it is not present, insert it into its sorted position.

Make a note in your homework that there is an existing data structure (TreeSet) that performs this functionality, but does so via a better implementation than the one you just created.

Answer 7

Here is an insert method in O(log n).

public void insert(int x) {
    int pos = Collections.binarySearch(this, x);
    if (pos < 0) {
        add(-pos-1, x);
    }
}