title: Array-based implementation of a sorted linked list
body: <p>I need to write a java linked list which needs to be array based and sorted. So the array contains nodes which have 2 fields: the data, and the index of the next element in the list. The last element of the list needs to have an index of -1.</p>
  
  <p>Can someone help how to add an element to such list. this is the code I wrote so far but does not seems to be right because I can add elements but the indexes are not right.</p>
  
  <pre><code>package listpackage;
  
  import java.io.IOException;
  
  public class ArrayLL {
      private int MAX_CAP = 100;
      private ANode[] list;
      private int size;
  
      public ArrayLL(){
          list = new ANode[MAX_CAP];
          list[list.length-1] = new ANode(null, -1);
          for(int i = 0; i &lt; list.length-1; i++){
              list[i] = new ANode(null, i+1);
          }
          size = 0;
      }
  
      public void addElem(String s) throws IOException{
          if(this.getSize() == 0){
              ANode a = new ANode(s, -1);
              list[0] = a;
          }else if(size == MAX_CAP + 1){
              throw new IOException("List is full");
          }else{
              int index = 0;
              for(int i=0; i &lt; list.length; i++){
                  if(list[i].getData() == null){
                      index = i;
                      break;
                  }
              }
              ANode b = new ANode(s);
              list[index] = b;
              if(this.getSize()==1){
                  if (list[index].getData().compareTo(list[0].getData()) &lt; 0){
                      list[index].setLink(0);
                      list[0].setLink(-1);
                  }else{
                      list[index].setLink(-1);
                      list[0].setLink(index);
                  }
              }else{
                  int i = 0;
                  while(list[i].getData() != null){
                      if(list[index].getData().compareTo(list[i].getData()) &lt; 0){
                          list[index].setLink(i);
                          if(i&gt;0)
                              list[i-1].setLink(index);
                      }else{
                          i++;
                      }
                  }
              }
          }
          size++;
      }
  
      public ANode[] getList(){
          return list;
      }
  
      public int getSize(){
          return size;
      }
  
  }
  
  
  
  
  class ANode{
      private String data;
      private int link;
  
      public ANode(String d){
          data = d;
          link = -1;
      }
  
      public ANode(String d, int l){
          data =  d;
          link = l;
      }
  
      public String getData(){
          return data;
      }
  
      public int getLink(){
          return link;
      }
  
      public void setLink(int l){
          link = l;
      }
  }
  </code></pre>