title: Insert element to ArrayList with ascending order and no duplicate elements
body: <p>I have a homework assignment where I need to insert or add new elemment into <code>ArrayList&lt;Interger&gt;</code> with follow condition:</p>
  
  <ol>
  <li><p>Element must <strong>ascending order</strong>.</p></li>
  <li><p><strong>No duplicate</strong> elements in <code>ArrayList&lt;Integer&gt;</code></p></li>
  <li><p>insert method run in <strong>O(n)</strong> times.</p></li>
  </ol>
  
  <p>Here is my insert method for check duplicate element before add new element.</p>
  
  <pre><code>    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&lt;super.size(); i++){
                          if(super.get(i)==x){
                              found = true;
                          }
                      }
                  }
                  if(found){ return; }
                  else{ super.add(x);  }
          }
  </code></pre>
  
  <p>how can i do it? Thank you.</p>
  
  <p><strong>addition</strong></p>
  
  <p>here is my class names InSetExtra</p>
  
  <pre><code>public class IntSetExtra extends ArrayList&lt;Integer&gt; {
  
  
      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&lt;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&lt;super.size(); i++){
              s += ", " + super.get(i).toString();
          }
          return s += "]";
      }
  
  }
  </code></pre>
  
  <p>and i need to insert a large size of elements, for example:</p>
  
  <pre><code>IntSetExtra a, b;
  
      a = new IntSetExtra();
      b = new IntSetExtra();
  
      for(int i=0; i&lt;30000; i++){ a.insert(2*i); }
      for(int i=0; i&lt;30000; i++){ a.insert(i); }
  
      System.out.println("a sub = "+a.toString().substring(0, 37));
  </code></pre>
  
  <p>what should i do?</p>
  
  <p>ps. my instructor need to use only ArrayList</p>