title: Moving pointers instead of objects in some kind of list or queue in Java
body: <p>Java offers a LinkedList implementation of the List interface which is actually a doubly-linked list. If we do the following:</p>
  
  <pre><code>linkedlist.remove(obj);
  </code></pre>
  
  <p>and then:</p>
  
  <pre><code>linkedlist.add(obj);
  </code></pre>
  
  <p>we actually remove the object obj from the linkedlist and reinsert it from the right-end (tail).</p>
  
  <p>We can also implement manually a linkedlist with nodes, head, and tail. In languages such as C++ which have some low-level characteristics, one can use pointers for the next and previous object of the obj object. Thus we don't have actually to remove the item but just to update the previous and next pointers.</p>
  
  <p>Is there any data structure in Java with which we can have the same effect (and thus the same performance gain of removing only "pointers" insted of the objects themselves)? </p>
  
  <p>Note that I would like to use a ready-to-go data structure instead of manually writting my one linkedlist implementation (and perhaps reinventing the wheel). Moreover, please note that it has not neccessarily to be a linkedlist - it might be, for example, some kind of queue such as an ArrayDeque. </p>
  
  <p>EDIT: To put it a little differently, if internally the LinkedList implementation of the List interface in Java makes use of prev and next pointers, then why l.remove(obj) is O(n) and not O(1)? And thus in practice, when you have a LinkedList with many millions of objects (as in my case), it takes so long time to do this removal and re-insertion? (Same with ArrayList, same with ArrayDeque - very long time).</p>