title: Left vs Right linked list, Replace speed
body: <p>There are two obvious ways to structure a linked list in Mathematica, "left":</p>
  
  <pre><code>{1, {2, {3, {4, {5, {6, {7, {}}}}}}}}
  </code></pre>
  
  <p>And "right":</p>
  
  <pre><code>{{{{{{{{}, 7}, 6}, 5}, 4}, 3}, 2}, 1}
  </code></pre>
  
  <p>These can be made with:</p>
  
  <pre><code>toLeftLL = Fold[{#2, #} &amp;, {}, Reverse@#] &amp; ;
  
  toRightLL = Fold[List, {}, Reverse@#] &amp; ;
  </code></pre>
  
  <p>If I use these, and do a simple <code>ReplaceRepeated</code> to walk through the linked list, I get drastically different <code>Timing</code> results:</p>
  
  <pre><code>r = Range[15000];
  left = toLeftLL@r;
  right = toRightLL@r;
  
  Timing[i = 0; left //. {head_, tail_} :&gt; (i++; tail); i]
  Timing[i = 0; right //. {tail_, head_} :&gt; (i++; tail); i]
  
  (* Out[6]= {0.016, 15000} *)
  
  (* Out[7]= {5.437, 15000} *)
  </code></pre>
  
  <p>Why?</p>