title: Swap items in doubly-linked list by their indices in the backing array
body: <p>I have an array of objects of the following type:</p>
  
  <pre><code>struct Node {
      Node *_pPrev, *_pNext;
      double *_pData;
  };
  </code></pre>
  
  <p>Some of the nodes participate in a doubly-linked list, with <code>_pData!=nullptr</code> for such nodes. There is also a dummy head node with <code>_pNext</code> pointing to the beginning of the list, and <code>_pPrev</code> pointing to the end. The list starts with containing only this head node, and it should be never removed from the list.</p>
  
  <p>The doubly-linked list is backed by an array, with initial size equal to the maximum number of nodes in the list.</p>
  
  <pre><code>struct Example {
      Node _nodes[MAXN];
      Node _head;
  };
  </code></pre>
  
  <p>Now I want to perform the following operation on this data structure: given 2 indices <code>i</code> and <code>j</code> to the <code>_nodes</code> array, swap the nodes in the array, but preserve their positions in the doubly-linked list. This operation needs updating <code>_nodes[i]._pPrev-&gt;_pNext</code>, <code>_nodes[i]._pNext-&gt;_pPrev</code> and the same for node <code>j</code>.</p>
  
  <p>One problem is the corner cases when nodes <code>i</code> and <code>j</code> are next to each other. Another problem is that the naive code involves a lot of <code>if</code>s (to check for <code>_pData==nullptr</code> for each node and handle the 3 cases differently, and to check whether the nodes are next to each other), thus becoming inefficient.</p>
  
  <p>How to do it efficiently?</p>
  
  <p>Here is what I have so far in C++:</p>
  
  <pre><code>assert(i!=j);
  Node &amp;chI = _nodes[i];
  Node &amp;chJ = _nodes[j];
  switch (((chI._pData == nullptr) ? 0 : 1) | ((chJ._pData == nullptr) ? 0 : 2)) {
  case 3:
      if (chI._pNext == &amp;chJ) {
          chI._pPrev-&gt;_pNext = &amp;chJ;
          chJ._pNext-&gt;_pPrev = &amp;chI;
          chI._pNext = &amp;chI;
          chJ._pPrev = &amp;chJ;
      }
      else if (chJ._pNext == &amp;chI) {
          chJ._pPrev-&gt;_pNext = &amp;chI;
          chI._pNext-&gt;_pPrev = &amp;chJ;
          chJ._pNext = &amp;chJ;
          chI._pPrev = &amp;chI;
      } else {
          chI._pNext-&gt;_pPrev = &amp;chJ;
          chJ._pNext-&gt;_pPrev = &amp;chI;
          chI._pPrev-&gt;_pNext = &amp;chJ;
          chJ._pPrev-&gt;_pNext = &amp;chI;
      }
      break;
  case 2:
      chJ._pNext-&gt;_pPrev = &amp;chI;
      chJ._pPrev-&gt;_pNext = &amp;chI;
      break;
  case 1:
      chI._pNext-&gt;_pPrev = &amp;chJ;
      chI._pPrev-&gt;_pNext = &amp;chJ;
      break;
  default:
      return; // no need to swap because both are not in the doubly-linked list
  }
  std::swap(chI, chJ);
  </code></pre>