title: Inserting into a Doubly Linked List
body: <p>I am trying to create a doubly linked list container for a project. I cannot use any std containers. The doubly linked list has to be sorted. Here is my code so far:</p>
  
  <pre><code>#include &lt;iostream&gt;
  using namespace std;
  
  template &lt;typename T&gt;
  class dll {
  private:
      struct Node {
          Node* prev;
          Node* next;
          T data;
      };
  
      Node* head;
      Node* tail;
  
  public:
      dll();
      ~dll();
  
      void insert(T value);
  
      bool empty() const { return head == tail; };
  };
  
  template &lt;typename T&gt; dll&lt;T&gt;::dll() {
      head = nullptr;
      tail = head;
  }
  
  template &lt;typename T&gt; dll&lt;T&gt;::~dll() {
      delete[] head;
  }
  
  template &lt;typename T&gt; void dll&lt;T&gt;::insert(T value) {
      Node *node = new Node;
      node-&gt;data = value;
      // Case 1: There are no nodes yet
      if (head == nullptr) {
          node-&gt;prev = nullptr;
          node-&gt;next = nullptr;
          head = node;
          tail = head;
      }
      else {
          // Case 2: There is more than one node
          Node *curr = head;
          if (curr-&gt;next != nullptr)
          {
              while (curr-&gt;next) {
                  // If the value is less than the current value
                  if (value &lt; curr-&gt;data) {
                      Node *temp = new Node;
                      temp-&gt;data = curr-&gt;data;
                      temp-&gt;next = curr-&gt;next;
                      temp-&gt;prev = curr-&gt;prev;
                      node-&gt;next = temp;
                      node-&gt;prev = temp-&gt;prev;
                      curr-&gt;prev = node;
                  }
                  curr = curr-&gt;next;
              }
          }
          // Case 3: There is only one node
          else {
              node-&gt;prev = head;
              node-&gt;next = nullptr;
              tail = node;
          }
      }
  }
  
  int main() {
      dll&lt;int&gt; list;
      list.insert(10);
      list.insert(20);
      list.insert(15);
  }
  </code></pre>
  
  <p>The problem I am having is in my insert function. I am using the debugger and stepping into the code at the line: list.insert(10);.</p>
  
  <p>It correctly goes into the first case where head == nullptr and creates the Node.
  When I step into the next line of code (list.insert(20) ), it creates a node with this line: Node *node = new Node; 
  But it is creating the node with the memory address that head is pointing to.</p>
  
  <p>I put a watch on the head variable and the node variable and the memory addresses were the same.Basically it is creating the same Node as it did for the last insertion. </p>
  
  <p>I don't know how to get the line: Node *code = new Node; to create something new. Am I using the new keyword wrong here?</p>