title: Why is removing elements from the start/beginning in a Linked List faster than remove(last) in an Array List?
body: <p>Deleting items from an <strong>Array List</strong> from the end has a time complexity of O(1), just like deleting items from the head of a <strong>Linked List</strong>. But <strong>Linked List</strong> is still a bit faster when I test it in java and I don't quit understand why. Can somebody explain why is <strong>Linked List</strong> still faster even though they're both in O(1) time complexity?</p>
  <p>I don't think that my code will help you answer my question, since it is more about Data Structure. But here it is just in case (don't mind the French it's for a homework) :</p>
  <pre><code>LinkedList&lt;Integer&gt; LinkL = new LinkedList&lt;Integer&gt;();
          ArrayList&lt;Integer&gt; ArrL = new ArrayList&lt;Integer&gt;();
          int N;
          N = 1000;
          //2.creer le Linked List
          for(int i=0; i&lt;N; i++) {    
          LinkL.add(i);
          }
          //System.out.println(LinkL);  
          //3. et 4.Supprimer les elements de Linked List et afficher le temps
          long debut = System.nanoTime(); 
          for(int i=0; i&lt;N; i++) {
          LinkL.removeFirst();
          }
          long fin = System.nanoTime();
          long tempsExecution = fin - debut;
          System.out.println(&quot;1.Suppression des éléments de LinkL avec la méthode \nremoveFirst( ) de LinkedList, avec une durée \nduréeLinkedList = &quot;+tempsExecution+ &quot; nanosecondes&quot;);  //-
          
          //5.Creer Array List
          for(int i=0; i&lt;N; i++) {    
              ArrL.add(i);
              }
          //System.out.println(ArrL);
          //6.Supprimer les elements de Array List et afficher le temps
          debut = System.nanoTime(); 
          for(int i=0; i&lt;N; i++) {
          ArrL.remove(0);
          }
          fin = System.nanoTime();
          tempsExecution = fin - debut;       
          System.out.println(&quot;\n2.Suppression des éléments de ArrL avec remove(0) d’un \nArrayList, durée duréeArrayDirect = &quot;+tempsExecution+ &quot; nanosecondes&quot;);
          
          //7. Recreer ArrL
          for(int i=0; i&lt;N; i++) {    
              ArrL.add(i);
              }
          //System.out.println(ArrL);
          //Supprimer les elements de ArrL
          debut = System.nanoTime(); 
          for(int i=N-1; i&gt;=0; i--) {
              ArrL.remove(i);
              }
          fin = System.nanoTime();
          tempsExecution = fin - debut;   
          System.out.println(&quot;\n3.Suppression des éléments de ArrL avec remove(i) ciblant \nles derniers éléments d’un ArrayList, avec une durée \nde duréeArrayInverse = &quot;+tempsExecution+ &quot; nanosecondes&quot;);
  
      }
  
  }
  </code></pre>
  <p>Thanks in advance.</p>