Singly-linked list implementation

Question

My code is working now. As you can see in the list.h some type definitions are too long and hard to read. Is there a way to do some short ones? And what happens if the code throws an exception? (I know I will have leaking memory parts) What can I do to collect garbage? And what other functions might be added to code to enhance it?

list.h

#ifndef LIST_H_
#define LIST_H_

#include <iostream>

template <typename T>
class list{
public:
    list();
    ~list();
    class node;
    typedef T           value_type;
    typedef T&          reference;
    typedef node        node_type;
    typedef node_type*  node_pointer;

    list&           push_back(value_type);
    value_type      pop_front();
    node_pointer    begin() const;
private:
    node_pointer    head, tail;
};


template <typename T>
class list<T>::node{
public:
    node(value_type value = 0);
    ~node();
    void            setData(value_type);
    value_type      getData() const;
    void            setNext(node_pointer);
    node_pointer    getNext() const;

private:
    value_type      data;
    node_pointer    ptr_next;
};

template <typename T>
inline list<T>::node::node(value_type value) : data(value), ptr_next(nullptr){
    //std::cout << "*" << value << "\t";
}

template <typename T>
inline list<T>::node::~node(){
    //std::cout << "node dtor" << std::endl;
}

template <typename T>
void list<T>::node::setData(value_type value){
    this->data = value;
}

template <typename T>
typename list<T>::value_type        list<T>::node::getData() const{
    return this->data;
}

template <typename T>
void list<T>::node::setNext(node_pointer ptr){
    this->ptr_next = ptr;
}

template <typename T>
typename list<T>::node_pointer  list<T>::node::getNext() const{
    return this->ptr_next;
}

template <typename T>
list<T>::list() : head(nullptr), tail(nullptr){
    //std::cout << "list ctor" << std::endl;
}

template <typename T>
list<T>::~list(){
    list<T>::node_pointer ptr = this->head, next_ptr;
    while(ptr != nullptr){
        //std::cout << "@" << ptr->getData() << "\t";
        next_ptr = ptr->getNext();
        delete ptr;
        ptr = next_ptr;
    }
}

template <typename T>
list<T>&    list<T>::push_back(value_type value){
    node_pointer item = new node_type(value);
    if(this->tail) this->tail->setNext(item);
    this->tail = item;
    if(!this->head) this->head = this->tail;

    return *this;
}

template <typename T>
typename list<T>::value_type    list<T>::pop_front(){
    if(this->head){
        node_pointer    item = this->head;
        value_type      value = this->head->getData();

        this->head = this->head->getNext();
        delete item;

        return value;
    }

return 0;
}

template <typename T>
typename list<T>::node_pointer list<T>::begin() const{
    return this->head;
}

template <typename T>
std::ostream & operator<<(std::ostream &stream, list<T> &obj){
    typename list<T>::node_pointer ptr = obj.begin();
    while(ptr != nullptr){
        stream << ptr->getData() << ' ';
        ptr = ptr->getNext();
    }
    return  stream;
}

#endif /* LIST_H_ */

main.cpp

int main (int argc, char ** argv){

    list<int> numbers;
    numbers.push_back(3).push_back(5).push_back(11);
    cout << numbers;

    return 0;
}

Answer 1

Let's answer your questions first:

What about the memory issues? If you are not limited to an older C++ standard in any way, it would be the best to use C++11 (or above), since it provides you with a good implementation of smart pointers (reference, in-depth-tutorial). This way, all your memory management becomes easier and more resilient. Also you do not need to manually delete anything and do not run into trouble if someone else is still accessing the element you just removed.

Caution: Smart pointers and raw pointers do not mix very well, so avoid raw pointers whenever possible.

What about type definitions? In general, many people nowadays do frown upon typedefs. Firstly, they hide the actual composition of the type and may lead to confusion or wrong assumptions - especially in team projects. Second, in C++ you do have the using keyword which is a better choice here, especially since it can be combined with templates. (reference)

What functions should be provided? If there is a push_back I would expect some kind of pop_back (also a push_front). Usually you have some methods to give you the number of elements in the list, check if the list is empty... You can take Qt's QList class as an inspiration ().

Suggestion: make node a templates class Defining the inner class list<T>::node is valid code and gets the job done. However, you may find that it would be more convenient to pull it out of the list class and define a stand-alone class node<T>. A list<T> then contains a node<T>. Depending on your design, you then might find that your node class then is re-usable e.g. for queues.

Recommendation: Use namespaces Namespaces are your #1 tool to structure your code. At least one level of namespaces should be used at all times to avoid cluttering the global namespace.

Suggestion: use #pragma once If your compiler supports it, this is a good alternative to the include guards. Just put it into the first line of your header and you are good to go.

Hint: inline is not that important First, do not waste brain capacity on whether to inline something while developing. Early optimization suffocates progress, diverts attention, and thus kills projects. Get it to run, then optimize one step at a time. Second, modern compilers know best what to inline and what not. Let them do it, they are really good at this. While learning, trust your compiler. You can argue with it later :)

Additional note: Combining templates and inline is used to address issues with the One Definition Rule (ODR). If you define a template, but do not fully specialize it, you may (but do not need to) inline. However if you do also want to provide a fully specialized case, you have to inline, otherwise you conflict with the ODR, since the compiler expands the template and thus already provides an implementation for the case you intended to cover "by hand". See also this question for details and examples. (Kudos to @Cody Gray)

Wrapping things up I just sketched together a piece of code that sums up the made suggestions/ recommendations to give you an orientation (Note: I prefer the Java-style of camel-casing the type names with an initial upper case letter, but this is a question of personal preference).

#pragma once

#include <memory> // for smart pointers

namespace collection {

template<typename ValueType>
class Node<ValueType> {

private:
    ValueType _data; 
    // alternatively store a smart pointer to the data 
    // if the amount of data is large e.g. an image
    std::shared_ptr<Node<ValueType>> _next;
    // to "delete" the next pointer just reset it to nullptr
    // only hand out the shared pointer, never the thing it points to
    // the receiver has to check if the pointer is null before use
public: 
     //... you know what to do
};

template<typename ValueType>
class List<ValueType> {

private:
    std::shared_ptr<Node<ValueType>> _head;
    // you can also keep track of the tail and whatever...
public:
    // ... all the functions
};

} // end namespace collection

Last but not least Put your code somewhere accessible (e.g. github) which makes it easier to review code, suggest concrete changes, discuss details, and notify you about the bugs and issues that were found. Post a link and I will have a look at it :)