title: LinkedList Custom Implementation Faster than Java LinkedList
body: <p>I've recently started Cracking the Code Interview and I just got to LinkedLists. I did problem 2.1 to remove duplicate entries from the book's implementation of LinkedList.</p>
  <p>When I time the removal of dupes, I see the book's implementation is faster than Java LinkedList.</p>
  <p>I've implemented four dupe removal methods, each with a different parameter. The book's LinkedList implementation is referred to as Node.</p>
  <pre><code>    static void removeDupes(LinkedList&lt;Integer&gt; list) {
          HashSet&lt;Integer&gt; integerHashSet = new HashSet&lt;&gt;();
          for (int i = 0; i &lt; list.size(); i++) {
              if (integerHashSet.contains(list.get(i))) {
                  list.remove(list.get(i));
              } else {
                  integerHashSet.add(list.get(i));
              }
          }
      }
  
      static void removeDupes(ArrayList&lt;Integer&gt; list) {
          HashSet&lt;Integer&gt; integerHashSet = new HashSet&lt;&gt;();
          for (int i = 0; i &lt; list.size(); i++) {
              if (integerHashSet.contains(list.get(i))) {
                  list.remove(list.get(i));
              } else {
                  integerHashSet.add(list.get(i));
              }
          }
      }
  
     static void removeDupes(Node currentNode) {
          HashSet&lt;Integer&gt; integerHashSet = new HashSet&lt;&gt;();
          while(currentNode != null) {
              if (integerHashSet.contains(currentNode.data)) {
                  currentNode.prev.next = currentNode.next;
                  if (currentNode.next != null) {
                      currentNode.next.prev = currentNode.prev;
                  }
              } else {
                  integerHashSet.add(currentNode.data);
              }
              currentNode = currentNode.next;
          }
      }
  
      static void removeDupesNoBuffer(Node currentNode) {
          while (currentNode != null) {
              Node runnerNode = currentNode;
              while(runnerNode.next != null) {
                  if (runnerNode.next.data == currentNode.data) {
                      runnerNode.next = runnerNode.next.next;
                      if (runnerNode.next != null) {
                          runnerNode.next.prev = runnerNode;
                      }
                  } else {
                      runnerNode = runnerNode.next;
                  }
              }
              currentNode = currentNode.next;
          }
      }
  </code></pre>
  <p>Book's LinkedList implementation:</p>
  <pre><code>public class Node {
      Node prev;
      Node next;
      int data;
  
      Node(int d) {
          data = d;
      }
  
      void add(int d) {
          Node newNode = new Node(d);
          Node currentNode = this;
          while (currentNode.next != null) {
              currentNode = currentNode.next;
          }
          currentNode.next = newNode;
          newNode.prev = currentNode;
      }
  }
  </code></pre>
  <p>Each List or Node, I populated with a length of 100000, where each odd index was 0 and everything else was unique.</p>
  <p>My results were:</p>
  <ul>
  <li>Node: 18ms</li>
  <li>Node No Buffer: 5154ms</li>
  <li>LinkedList: 2734ms</li>
  <li>ArrayList: 1392ms</li>
  </ul>
  <p><strong>What am I not understanding?</strong></p>
  <p><em><strong>EDIT:</strong></em></p>
  <p>When I swapped the remove dupes with the LinkedList parameter to an enhanced for loop as pointed out by the comments and solution, it became just as fast.</p>
  <pre><code>    static void removeDupes(LinkedList&lt;Integer&gt; list) {
          HashSet&lt;Integer&gt; integerHashSet = new HashSet&lt;&gt;();
          for(Integer i : list) {
              if (integerHashSet.contains(i)) {
                  list.remove(i);
              } else {
                  integerHashSet.add(i);
              }
          }
      }
  </code></pre>