title: Random access cyclical data structure with two defined operations
body: <p>As input I recive a list of natural integers. 
  I have to store them inside a structure that enables me to go from the last element to the first without much problem.</p>
  
  <p>The task is to perform t (number given from the start) operations on this data structure. Starting from the first number given as input (i=0):</p>
  
  <p>If data[i] % 2 == 0  -> perform operation R</p>
  
  <p>else -> perform operation X</p>
  
  <p>operation R: remove element with index position i+1, and move to the right as many times as was the value of removed element.</p>
  
  <p>operation X: take the value of data[i] element and insert new element in front of that one with value data[i]-1. Then move data[i] times to the right.</p>
  
  <p>example (i->n means that i points to el. with value n):</p>
  
  <p>input: 3 1 2 3</p>
  
  <p>t = 3</p>
  
  <p>data = [ 1, 2, 3 ]</p>
  
  <pre><code> 1.
   i-&gt;1
   operation X, 
   result: [ 1, 0, 2, 3 ]
  
   2.
   i-&gt;0
   operation R,
   result: [ 1, 0, 3 ]
  
   3.
   i-&gt;1
   operation X, 
   result: [ 1, 0, 0, 3 ]
  </code></pre>
  
  <p>The real problem occurs when the value of t is very large. 
  I tried two implementations:</p>
  
  <ul>
  <li>One based on linked list. I know it works because the result is correct, but execution time is close to 2-3 minutes.</li>
  <li>One based on an array but the execution time is just a little faster.</li>
  </ul>
  
  <p>Here is the fragment that takes 99,99% of execution time:</p>
  
  <pre><code>while(t--){
      c = current -&gt; value;
      if(c % 2 == 0){
          c = current -&gt; next -&gt; value;
          Node* n = current -&gt; next -&gt; next;
          free(current -&gt; next);
          current -&gt; next = n;
  
          --size;
      }
      else{
          Node* n = getNode(current -&gt; next);
          current -&gt; next = n;
          n -&gt; value = c-1;
  
          ++size;
      }
  
      c %= size;
      while(c--){
          current = current-&gt;next;
      }
  }
  </code></pre>
  
  <p>getNode(Node* n)  returnes new node with node -> next = n.</p>
  
  <p>Any insight into optimalization method/ other approach appreciated.</p>
  
  <p>*edit:</p>
  
  <pre><code>Node* getNode(Node* nxt){
      Node* first = (Node*)malloc(sizeof(Node));
      first -&gt; value = -1;
      first -&gt; next = nxt;
      return first;
  }
  </code></pre>