title: Sorting String Array Indicies with Insertion Sort, Doubly Linked List
body: <p>I am working on an assignment where I have to sort an array and store the indices in a doubly linked list ADT that I have built. </p>
  
  <pre><code>Example:
  {"A","B","C","A"} -&gt; {0,3,1,2}
  </code></pre>
  
  <p>My current approach is to bring the indices into my ADT and then sort the ADT as I sort the array. As far as I can tell, I am doing the exact same operation on both the array and the doubly linked list every time either loop executes, but my output does not match up.</p>
  
  <pre><code>public static void main(String[] args ) {
      List A = new List();
      String[] inputArray = {"A","C","B","A"};
      int i,j;
      String key;
      //load indices into doubly-linked list
      for (int x = 0; x &lt; inputArray.length; x++ ) {
          A.append(x);
      }
      //begin insertion sort
      for (j = 1; j &lt; inputArray.length; j++) {
          System.out.println(A);
          System.out.println(Arrays.toString(inputArray));
          key = inputArray[j];
          i = j - 1;
          while (i &gt;= 0) {
              if (key.compareTo(inputArray[i]) &gt; 0) {
                  break;
              }
              inputArray[i+1] = inputArray[i];
              //moveTo moves the cursor to &lt;int&gt;
              A.moveTo(i);
              //make sure we aren't trying to insert before first node
              if (i &gt; 0) { A.insertBefore(i+1); }
              else { A.prepend(i+1); }
              //remove node at cursor
              A.delete();
              i--;
          }
          inputArray[i+1] = key;
          A.moveTo(i+1);
          if (i &gt; 0) { A.insertBefore(i+1); }
          else { A.prepend(i+1); }
          A.delete();
      }
      System.out.println(A);
      System.out.println(Arrays.toString(inputArray));
  }
  </code></pre>
  
  <p>The above code gives the following output:</p>
  
  <p>run:<br>
  0 1 2 3<br>
  [A, C, B, A]<br>
  1 0 2 3<br>
  [A, C, B, A]<br>
  1 1 2 3<br>
  [A, B, C, A]<br>
  0 2 3 3<br>
  [A, A, B, C]<br>
  BUILD SUCCESSFUL (total time: 0 seconds)</p>
  
  <p>EDIT: List.java</p>
  
  <pre><code>public class List {
  
      private class Node{
          //Fields
          int data;
          Node next, previous;
          //Constructor
          Node(int data) {
              this.data = data;
              next = null;
              previous = null;
          }
          public String toString() { return String.valueOf(data); }
      }
  
      //Fields
      private Node frontNode, backNode, cursorNode;
      private int totalSize, cursorPosition;
  
      //Constructor
      List() {
          frontNode = backNode = cursorNode = null;
          totalSize = 0;
          cursorPosition = -1;
      }
      //moveTo(int i): If 0&lt;=i&lt;=length()-1, moves the cursor to the element 
      // at index i, otherwise the cursor becomes undefined.
      void moveTo(int i) {
          if (i == 0) {
              cursorPosition = i;
              cursorNode = frontNode;
          }
          else if (i == length() - 1) {
              cursorPosition = i;
              cursorNode = backNode;
          }
          else if (i &gt; 0 &amp;&amp; i &lt; length() - 1 ) {
              cursorNode = frontNode;
              cursorPosition = i;
              for (int x=0; x &lt; i; x++) {
                  cursorNode = cursorNode.next;
              }
          }
          else {
              cursorPosition = -1; 
          }
      }
  
  //prepend(int data): Inserts new element before front element in this List.
      void prepend(int data) {
          Node node = new Node(data);
          if ( this.length() == 0 ) {
              frontNode = backNode = node;
          }
          else {
              frontNode.previous = node;
              node.next = frontNode;
              frontNode = node;
          }
          totalSize++;
          //cursorPosition might change?
      }
      //insertBefore(int data): Inserts new element before cursor element in this
      // List. Pre: length()&gt;0, getIndex()&gt;=0
      void insertBefore(int data) {
          Node node = new Node(data);
          if ( this.length() &gt; 0 &amp;&amp; this.getIndex() &gt;= 0 ) {
              node.previous = cursorNode.previous;
              node.next = cursorNode;
              cursorNode.previous.next = node;
              cursorNode.previous = node;
              totalSize++;
          }
          else if ( this.length() &lt;= 0 )
          {
             throw new RuntimeException
                      ("Error: insertBefore called on empty list");
          }
          else {
              throw new RuntimeException
                      ("Error: insertBefore called without cursor set");
          }
      }
  </code></pre>