0
\$\begingroup\$

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

\$\endgroup\$

closed as off-topic by Edward, Graipher, πάντα ῥεῖ, t3chb0t, Snowhawk Jan 5 at 2:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Edward, Graipher, πάντα ῥεῖ, t3chb0t, Snowhawk
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Welcome to Code Review! I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. Code Review is not the site to ask for help in fixing or changing what your code does. Once the code does what you want, we would love to help you do the same thing in a cleaner way! Please see our help center for more information. Specifically InsertEnd is faulty. Have you tested this code? \$\endgroup\$ – Edward Jan 3 at 15:32
  • \$\begingroup\$ @Edward Hi, thanks for the reply. I have tested the code and it runs fine for me and I have debugged this to ensure the ordering is correct, unless there are other cases that I have missed that produces incorrect results. I am not looking for help in fixing the code, but rather whether it is a correct usage for templates, and/or if anything could be done better. \$\endgroup\$ – jjmcc Jan 3 at 15:46
  • 1
    \$\begingroup\$ Strengths of a doubly linked list are constant time front, back and random insertion/lookup/removal. The given implementation does neither of those operations in constant time (no lookup/removal at all, no random insertion, front and back insertion in linear time). (Just voicing my expectations when I hear "doubly linked list" - this doesn't mean your code is wrong, just that the implementation didn't match my expectations from the title). \$\endgroup\$ – hoffmale Jan 3 at 15:49
  • 2
    \$\begingroup\$ It would be useful if you augmented the question with the code you used to test. \$\endgroup\$ – Edward Jan 3 at 16:00
  • 1
    \$\begingroup\$ @bruglesco I will finish the implementation then. Thank you \$\endgroup\$ – jjmcc Jan 3 at 16:07
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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) {
}
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.