title: How do I insert a new node before first node of a doubly-linked list?
body: <p>I am looking at how to insert a new node before the first node of a doubly-linked list. I'm getting confused with the <strong>auxiliary nodes required</strong> for this operation and the <strong>sequence of steps</strong> in which to perform the operation. I would be grateful for a hint on how to solve this problem i.e. what is wrong with my <code>insertBeforeFirst</code> method. As it stands the method causes a nullPointerException which i find hard to troubleshoot. (note: this is a follow-on to a previous <a href="https://stackoverflow.com/questions/5305832/inserting-first-node-into-empty-doubly-linked-list-how-to">post</a>.)</p>
  
  <pre><code>public DLL()
  {
      header = null ;
      tail = null ;
  }
  
  ...
  DLL myList = new DLL() ;
  DLLNode A = new DLLNode("Hello", null, null) ;
  DLLNode B = new DLLNode("Hi", null, null) ;
  ...
  
  myList.addFirst(A) ;
  myList.insertBeforeFirst(B)
  
  ...
  public void addFirst(DLLNode v)
  {
      v.pred = header ; 
      v.succ = tail ; 
      header = v ;
      tail = v ;
  }
  ...
  
  public void insertBeforeFirst(DLLNode v)
  {
      DLLNode aux = v ;
      aux.succ = header.succ ;
      header = aux ;
      DLLNode aux2 = aux.succ ;
      aux2.pred = v ;
  }
  </code></pre>
  
  <p><strong>[EDIT]</strong></p>
  
  <p>I've followed Aaron's advice and made a drawing and i have a slight improvement in that i don't get a nullPointerException anymore but the new mode is inserted after the first node rather than before. So my drawing skills need some polishing too i think :)</p>
  
  <pre><code>public void insertBeforeFirst(DLLNode v)
  {
      v.succ = header.succ ; // point new node succ to current first node
      header.succ = v ;  //point header to new node
      DLLNode aux = header.succ ; // auxiliary node for backward insertion
      aux.pred = v ; // point auxiliary's pred backward to new node
  }
  </code></pre>
  
  <p><strong>[EDIT2]</strong></p>
  
  <p>Looking at the post by MahlerFive I see now why some of you might get confused by my header and tail talk. Here is where i got it from: <em>"To simplify programming, it is convenient to add special nodes at both ends of a doubly linked list: a <strong>header</strong> node just before the head of the list, and a <strong>trailer</strong> node just after the tail of the list. These "dummy" nodes do not store any elements"</em> <a href="http://ww0.java4.datastructures.net/" rel="nofollow noreferrer">source</a></p>
  
  <p>So it seems that for a starter i need to find a way to implement these dummy nodes correctly before i can add anything and make correct references. these DUMMY nodes seem to require a different Node constructor? Could they be instantiated by the DLL default constructor? </p>
  
  <p><strong>[EDIT3]</strong></p>
  
  <p>@MahlerFive, the DLL constructor will look like this:</p>
  
  <pre><code>public DLL()
  {
      DLLNode Header = new DLLNode(null, null, null) ;
      DLLNode Tail = new DLLNode(null, Header, null) ;
      Header.succ = Tail ;
  }
  </code></pre>
  
  <p>and my method something like this, although i'm getting a nullPointerException at the moment:</p>
  
  <pre><code>// insert z before v
  public void addBeforeFirst(DLLNode v, DLLNode z)
  {
      DLLNode aux = v.pred ;
      z.pred = aux ;
      z.succ = v ;
      v.pred = z ;
      aux.succ = z ;
  }
  </code></pre>
  
  <p><strong>[EDIT4]</strong></p>
  
  <p>I'm making progress. (great feeling!) I am in agreement with MahlerFive that the DUMMY Header and Tail nodes are not a great way to approach this. But as it was mentioned in a published book on the matter it was worth at least exploring. Here goes my new code (without the use of dummy nodes): </p>
  
  <pre><code>...
  
  // DLL Constructor
  public DLL()
  {
      first = null ;
      last = null ;
  }
  ...
  // example insert call
  // B is the node in front of which i want to insert
  l.insert("Ciao", B) ;
  ...
  
  public void insert(String elem, DLLNode pred)
  {
      // make ins a link to a newly-created node with element elem,
      // predecessor null, and successor null.
      DLLNode ins = new DLLNode(elem, null, null) ;
      // Insert ins at the insertion point in the
      // forward SLL headed by first.
      ins.pred = first ;
      ins.succ = first ;
      // let first be the the new node
      first = ins ;
  }
  </code></pre>
  
  <p>this needs fine tuning as i haven't set any backwards links yet but it's a great starting point. To make sure this works correctly (at least in the forward way) i added print statements to print out the first and last element as i added nodes. Indeed they were updated correctly:</p>
  
  <pre><code>Hi
  first: hi
  last: hi
  
  Ciao Hi
  first: Ciao
  last: hi
  
  Moin Ciao Hi
  first: Moin
  last: hi
  </code></pre>