title: How to efficiently remove an element from java LinkedList
body: <p>I have an algorithm where I pass through nodes in a graph in a certain way, occasionally passing through the same node several times, and I need to form a list of the nodes passed, such that a node appears once for the last time I passed it.</p>
  
  <p>For instance, if I passed through nodes <code>A -&gt; B -&gt; C -&gt; A -&gt; C</code>, the list I need in the end is <code>[B, A, C]</code>.</p>
  
  <p>What I wanted to do was to use a LinkedList, such that every node in the graph will contain a reference to its node in the LinkedList. Then, every time I pass through a node, I will remove its corresponding node from the LinkedList and insert it again into the end of the LinkedList, and the complexity of the operation will only be <code>O(1)</code>.</p>
  
  <p>However, when I began implementing this, I ran into a problem: apparently, the java class LinkedList does not allow me to see its actual list nodes. Using the regular remove functions of LinkedList to remove the list node containing a given graph node will be <code>O(n)</code> instead <code>O(1)</code>, negating the whole point of using a LinkedList to begin with.</p>
  
  <p>Naturally, I can implement LinkedList myself, but I would rather avoid that - it seems to me that if I have to implement LinkedList in java, I'm doing something wrong.</p>
  
  <p>So, is there a way to solve this problem without implementing LinkedList on my own? Is there something that I'm missing?</p>