title: Insert an element at a linked list by using a pointer and not position
body: <p>I am using a custom Doubly Linked List to implement a heuristic algorithm for my thesis. I have already implemented the basic functions of a list (insert, delete etc.) and some more that are useful for the case of the problem that I am studying.</p>
  <p>However I am a little bit troubled with the following implementation. Lets say I have a list: A-&gt;E-&gt;B-&gt;D and I want to insert the element <strong>C</strong> at the the best possible position inside the list. The objective function that decides the optimal position is not relevant so I won't include it.</p>
  <p>The current implementation is the following: I call the function findBestPos(C) which returns a pointer <strong>ptr</strong> that points to the left element of the best insert position. For example, if <strong>ptr</strong> points to E, then the best insert position will be between the elements E and B.</p>
  <p>After that, I call the function insertAt(leftElement, insertElement) which inserts the insertElement like this:</p>
  <pre><code>if(leftElement-&gt;next != nullptr){
      leftElement-&gt;next-&gt;prev = insertElement;
  }
  
  insertElement-&gt;next = leftElement-&gt;next;
  leftElement-&gt;next = insertElement;
  insertElement-&gt;prev = leftElement;
  </code></pre>
  <p>However, I keep wondering if an implementation like this is &quot;legal&quot;. I mean, from my little experience with C++ and other languages' containers we always use the position to define where we want to insert our new element inside a container. Surely, using position will take some more time cause of the comparisons but it seems more natural, safe and reusable.</p>
  <p>Thank you in advance.</p>
  <p><strong>Update</strong></p>
  <p>After @TedLyngmo's comment, I would like to include some clarifications regarding the findBestPos functionality and to demonstrate other cases that I am using similar optimizations. What I basically have is two lists:</p>
  <ul>
  <li>Unvisited</li>
  <li>Walk</li>
  </ul>
  <p>The Unvisited list, contains all the nodes that will be considered to get inserted into the Walk list. The Walk list is basically a route of nodes that I will visit. Each node has some constant values like a visitDuration and some variables like arrivalTime, departureTime etc. that change at runtime. Also, moving from one node to another, takes some time which in my case is constant for each pair of nodes.</p>
  <p>Let's say that I am considering to insert node k between nodes i and j of Walk. The insertion cost function is:</p>
  <pre><code>shift(k) = travelTime(ik) + waitDuration(k) + visitDuration(k) + travelTime(kj) - travelTime(ij)
  </code></pre>
  <p>I calculate this cost for every possible position inside the Walk. The position that minimizes this cost is the optimal.</p>
  <p>I have used this kind of the above optimization for other functions as well. For example, when I disconnect a node from the Unvisited list I do the following:</p>
  <pre><code>void disconnect(T* curr) {
      if (head == curr) {
          head = curr-&gt;next;
      }
  
      if (tail == curr) {
          tail = curr-&gt;prev;
      }
  
      if (curr-&gt;next != nullptr) {
          curr-&gt;next-&gt;prev = curr-&gt;prev;
      }
      if (curr-&gt;prev != nullptr) {
          curr-&gt;prev-&gt;next = curr-&gt;next;
      }
      curr-&gt;next = nullptr;
      curr-&gt;prev = nullptr;
  }
  </code></pre>
  <p>As you can see, the disconnect function takes a pointer as a parameter instead of an id or a position. The head and tail pointers are private variables of the List class and they point to the first and last node of a list respectively. So for example, if I run A.disconnect(n) but node <strong>n</strong> in reality is the first node of list B, then node n will cut loose from its next node of list B, but B.head pointer will continue to point at <strong>n</strong>. Of course, it is my responsibility to not let this happen, but still it seems a little bit &quot;hackey&quot; to me.</p>