Ytdyklly

To become more familiar with templates I attempted a doubly linked list implementation in C++. Is this a valid use for a template?

template <class T>

struct LinkedListNode {

    LinkedListNode<T>* m_previous;

    T m_data;

    LinkedListNode<T>* m_next;

};



template <class T>

class LinkedList {

public:

    LinkedList() {

        m_head = nullptr;

    }



    LinkedListNode<T>* m_head;



    void InsertEnd(T data);

    void InsertFront(T data);



};



template<class T>

inline void LinkedList<T>::InsertFront(T data)

{

    LinkedListNode<T>* insertedNode = new LinkedListNode<T>();

    LinkedListNode<T>* firstNode = m_head;



    if (!firstNode) {

        insertedNode->m_data = data;

        insertedNode->m_next = nullptr;

        insertedNode->m_previous = nullptr;

        m_head = insertedNode;

    }

    else {

        while (firstNode->m_previous != nullptr) {

            firstNode = firstNode->m_previous;

        }



        insertedNode->m_next = firstNode;

        insertedNode->m_previous = nullptr;

        insertedNode->m_data = data;



        firstNode->m_previous = insertedNode;



        m_head = insertedNode;

    }



}





template<class T>

inline void LinkedList<T>::InsertEnd(T data)

{

    LinkedListNode<T>* insertedNode = new LinkedListNode<T>();

    LinkedListNode<T>* lastNode = m_head;



    if (!lastNode) {

        insertedNode->m_data = data;

        insertedNode->m_next = nullptr;

        insertedNode->m_previous = nullptr;

        m_head = insertedNode;



    }

    else {

        while (lastNode->m_next != nullptr) {

            lastNode = lastNode->m_next;

        }





        lastNode->m_next = insertedNode;



        insertedNode->m_previous = lastNode;

        insertedNode->m_next = nullptr;

        insertedNode->m_data = data;

        m_head = insertedNode;

    }

}

main.cpp

LinkedList<int>* linkedList = new LinkedList<int>();

linkedList->InsertEnd(2);

linkedList->InsertEnd(5);

linkedList->InsertEnd(9);

linkedList->InsertFront(1);

linkedList->InsertEnd(10);



LinkedList<std::string>* stringList = new LinkedList<std::string>();

stringList->InsertFront("one");

stringList->InsertEnd("two");

stringList->InsertFront("three");

Ordering should be
linkedList
1,2,5,9,10
stringList
three,one,two

The biggest thing I can say about your code is don't use raw pointers, start getting into the habit of using smart pointers.

Smart pointers enable automatic, exception-safe, object lifetime management.

InsertFront:

m_head should always point to the first node. So while (firstNode->m_previous != nullptr) loop looks unnecessary to me. If you're concerned about having m_head changed by the caller then i would make m_head private and provide getter method for that. Than you can merge if/else blocks as they are very similar.

InsertEnd:

Instead of iterating to find the last node every time (which makes it O(n)), you may maintain another pointer which always points to the last node. After that you may merge if/else blocks.

AFAIK following style of initializing class variables are more preferred.

LinkedList(): m_head(nullptr) {

}