title: Should the head of a linked list be a dummy node?
body: <p>I'm currently writing a program that (as of right now) utilizes about five linked lists, and there's about 50 functions that modify or otherwise use those linked lists.  I am somewhat torn on how exactly the head node should be implemented.</p>
  
  <p><strong>Implementation #1</strong> Using a dummy head node</p>
  
  <p>If I create a dummy head node, the headNode never has to be deleted, even if there is no data for that linked list to represent. Below are two different possible linked lists showing this idea.</p>
  
  <pre><code>Format: (object)--name_of_pointer_to_next_object--&gt; (next object)
  (headNode)--headNode.pNext--&gt; (Nothing/NULL)
  (headNode)--headNode.pNext--&gt; (dataNode1)--dataNode1.pNext--&gt; (dataNode2)--dataNode2.pNext--&gt; (Nothing/NULL)
  </code></pre>
  
  <p>The benefit of this implementation is that, for functions that work with the linked lists, they don't have to have special code for the case where the head node is <code>Nothing</code> or (in c++), <code>NULL</code>.  Below is an example of appending a node onto the end of the linked list using this implementation. </p>
  
  <pre><code>Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_)
      dim lastNode as NODE_
  
      Set lastNode = theLinkedList
  
      Do While Not lastNode.pNext Is Nothing
          Set lastNode = lastNode.pNext
      Loop
  
      Set lastNode.pNext = theNewNode 
  End Function
  </code></pre>
  
  <p><strong>Implementation #2</strong> headNode can be deleted</p>
  
  <p>If I allow the headNode to be deleted, this poses problems and increases the volume of code that I have to write.  Below is the same set of data, except this time the head is a legitimate node that contains data.</p>
  
  <pre><code>Format: (object)--name_of_pointer_to_next_object--&gt; (next object)
  (Nothing/NULL)
  (dataNode1)--dataNode1.pNext--&gt; (dataNode2)--dataNode1.pNext--&gt; (Nothing/NULL)
  </code></pre>
  
  <p>And here is the same function, except that this time it has to beware of the possibility that the head node is <code>Nothing</code>/<code>NULL</code>.</p>
  
  <pre><code>Public Function AppendNode(theLinkedList as NODE_, theNewNode as NODE_)
      dim lastNode as NODE_
  
      If theLinkedList Is Nothing Then
          Set theLinkedList = theNewNode 
      Else
          Set lastNode = theLinkedList
  
          Do While Not lastNode.pNext Is Nothing
              Set lastNode = lastNode.pNext
          Loop
  
          Set lastNode.pNext = theNewNode 
      End If
  End Function
  </code></pre>
  
  <p>Obviously, I am leaning towards Implementation #1.  It requires at least 4 less lines of code each time I want to use the linked lists (considering the fact that I will do this hundreds of times, you can multiply that 4 lines by 300 or so; e.g. it will save me from writing 1,200 lines of code), AND perhaps most importantly, it will cut down on the amount of state my program has.  All of the possible states that my program will be in will only require me to look for <code>pNext Is Nothing</code>, and reducing the amount of state is greatly appreciated at this point because this program is going to be a monster that will end up being around 20k lines of rather complicated code that has to deal with a lot of state.</p>
  
  <p>Am I wrong in thinking that Implementation #1 is the best way to do this?  I can't come up with a single reason why Implementation #2 would be superior.</p>