How do I create a new Node in a Doubly Linked List? (C++)

Question

I will first ask the question and then include all code. I am working in a data structures course and we have a make file provided us, but my C++ skills are mediocre at best. I have poured over many different articles and I still can't find out how to integrate the code in order to create a new node... I must be able to create new nodes in order to enqueue them, dequeue them, and do other manipulations on them related to a doubly linked list.

I have tried many different ways of building a constructor but it always seems there is some type of compiler error.

I am not allowed to change any code in the main file, but all my work must be contained in a templated header file. Can someone show me how to do this correctly? I will now include relevant code.

Here is my header file. I am aiming to get the buildNode() function in the LinkedList class to create a Node, then I can add the node to a doubly linked list.

#include <limits>
#include <string>
#include <cassert>
#include <iostream>

template <typename T>
class Node {
public:
    T data;
    Node* next;
    Node* prev;

    Node();

    ~Node();

    void getData() {

    }
};

template <typename T>
class Iterator {
private:

public:

Iterator() {
}

int operator*() const {
}

Iterator& operator++() {
}

bool operator==(Iterator const& rhs) {
}

bool operator!=(Iterator const& rhs) {
}
};

template <typename T>
class LinkedList {
private:
    Node<T> *head = 0;
    Node<T> *tail = 0;

public:

LinkedList() {
}

~LinkedList() {}

Iterator<T> begin() const {
}

Iterator<T> end() const {
}

bool isEmpty() const {
    if (this->head == 0) {
        std::cout << "Isempty works.";
        return true;
    }
}

T getFront() const {
}

T getBack() const {
}

void enqueue (T element) {
}

void dequeue() {
}

void pop() {
}

void clear() {
}

bool contains(int element) const {
}

void remove(int element) {
}

void buildNode() {  //experimental function.
    Node<T> n;
    // Node n = new Node();
    // Node<T> n;
    //Node<T> *n = new Node<T>();
    //Node n = new Node<T>;
}
};

I will only include the elements of the main file that are important to this particular challenge, which is

int main()
{
    // Get ready.
    LinkedList<string&> referenceList;
    LinkedList<char const*> valueList;

    //ascribe valueList and referenceList to a variable inside the LinkedList class...

unsigned int numOfStrings = 8;
string testStrings[] = {
        "alpha"
        , "bravo"
        , "charlie"
        , "charlie"
        , "dog"
        , "echo"
        , "foxtrot"
        , "golf"
};

string tempStr;

// Test isEmpty function.
 assert(valueList.isEmpty() && referenceList.isEmpty());

referenceList.buildNode(); //can't get this to work. Later the methodology will be transported to enqueue method.

EDIT: When I use the

Node<T> * n = new Node<T>; 

line in the buildNode() function, I get a linker error stating:

/Applications/CLion.app/Contents/bin/cmake/bin/cmake --build /Users/Boisselle/Library/Caches/CLion2016.2/cmake/generated/LinkedList-75be2cc8/75be2cc8/Debug --target LinkedList -- -j 8
Scanning dependencies of target LinkedList
[ 50%] Building CXX object CMakeFiles/LinkedList.dir/main.cpp.o
[100%] Linking CXX executable LinkedList
Undefined symbols for architecture x86_64:
  "Node<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&>::Node()", referenced from:
  LinkedList<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >&>::buildNode() in main.cpp.o
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
make[3]: *** [LinkedList] Error 1
make[2]: *** [CMakeFiles/LinkedList.dir/all] Error 2
make[1]: *** [CMakeFiles/LinkedList.dir/rule] Error 2
make: *** [LinkedList] Error 2

Answer 1

I believe you are looking for this syntax:

Node<T> * node_pointer = new Node<T>;

The template type should accompany the data type name.

Answer 2

In

template <typename T>
class Node {
public:
    T data;
    Node* next;
    Node* prev;

    Node();

    ~Node();

    void getData() {

    }
};

Node(); says the constructor exists somewhere, but is not defined here. You need to fully implement this function and ~Node();. As an aside, the Rule of Zero recommends that you not have ~Node(); at all.

Node() 
{ 
    do stuff here 
} 

is common, but in your case

Node() : next(nullptr), prev(nullptr) 
{ 
    /* does nothing */ 
} 

will work a bit better. See Member Initializer List for more details.

Once you have Node(); correctly implemented you can create a new node as suggested with

Node<T> *n = new Node<T>();

Addendum:

next(nullptr) and prev(nullptr) are pointing the links to null, a safe parking space for unused pointers. This makes testing the node to see what it has been linked to much easier than leaving them uninitialized. Initializing data in the constructor is probably easiest with

Node(T newdata) : data(newdata), next(nullptr), prev(nullptr) 
{ 
    /* does nothing */ 
}