Singly linked list implementation

Question

I feel like there is room for improvement in the push/pop methods. Any suggestions?

#include <exception>

template <typename T>
class List
{
public:

                    List();
                    ~List();
    void            PushBack(const T &data);
    void            PushFront(const T &data);
    void            PopBack();
    void            PopFront();
    void            Clear();    
    bool            IsEmpty() const;
    unsigned int    Size() const;
    T&              Front() const;
    T&              Back() const;

private:

    template <typename T>
    struct Node
    {
        Node(const T &data) : data(data), next(NULL) {}
        T      data;
        Node  *next;
    };

    Node<T> *head;
    Node<T> *tail;
};

template <typename T>
List<T>::List()
    : head(NULL),
      tail(NULL)
{

}

template <typename T>
List<T>::~List()
{
    Clear();
}

template <typename T>
void List<T>::PushBack(const T &data)
{   
    if ( !head )
    {
        head = new Node<T>(data);
        tail = head;
        return;
    }

    tail->next = new Node<T>(data);
    tail = tail->next;
}

template <typename T>
void List<T>::PushFront(const T &data)
{
    Node<T> *tmp = head;
    head = new Node<T>(data);
    head->next = tmp;

    if ( !tail )
    {
        tail = head;
    }
}

template <typename T>
void List<T>::PopBack()
{
    //empty list
    if ( !head )
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    //list with one element
    if ( head == tail )
    {
        delete head;
        head = NULL;
        tail = NULL;
        return;
    }

    Node<T> *current = head;
    while ( current->next != tail )
    {
        current = current->next;
    }

    delete tail;
    tail = current;
    tail->next = NULL;
}

template <typename T>
void List<T>::PopFront()
{
    //empty list
    if ( !head )
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    //list with one element
    if ( head == tail )
    {
        delete head;
        head = NULL;
        tail = NULL;
        return;
    }

    Node<T> *tmp = head->next;
    delete head;
    head = tmp;
}

template <typename T>
void List<T>::Clear()
{
    Node<T> *current = head;
    while ( head )
    {
        current = head;
        head = head->next;
        delete current;
    }

    head = NULL;
    tail = NULL;
}

template <typename T>
bool List<T>::IsEmpty() const
{
    return ( head == NULL );
}

template <typename T>
unsigned int List<T>::Size() const
{
    unsigned int size = 0;
    for ( Node<T> *current = head; current; current = current->next )
    {
        ++size;
    }

    return size;
}

template <typename T>
T& List<T>::Front() const
{
    if ( !head )
    {
        throw std::out_of_range("Can't return value from empty list");
    }

    return head->data;
}

template <typename T>
T& List<T>::Back() const
{
    if ( !head )
    {
        throw std::out_of_range("Can't return value from empty list");
    }

    return tail->data;
}

Answer 1

• Consider using a different naming convention for your data members and methods, such as camelCase or snake_case. Your user-defined types are already uppercase, which is okay. Whichever you choose, it's more readable to keep them separate.

• The push/pop methods here imply that this is a stack implementation, but a linked list should be capable of inserting or removing a node at any location in the list. Consider adding additional functions for this. For an idea of typical linked list functions, read this.

• Since you're using a list class, you should have a size member to maintain. Your Size() method is calculating the size at each call by traversing, which is O(n).

  Instead, have a size data member and update it with other operations:

  • initialize to 0 in the initializer list
  • increment with each push
  • decrement with each pop
  • reset to 0 with each clear

  When you call Size(), it should just return the data member value, which is O(1).

  It should also return a std::size_t. It is closest to the return type used in STL containers, and a very large list size may not fit inside an unsigned int.

• Instead of having a return in PushFront(), put the last two lines into an else block.

• Shouldn't popBack() check tail if PopFront() checks head? Although they may be pointing to the same node if there's only one node, but the intent is more clear this way.

• You should probably also have a Front() and Back() that return a T const&, in case the reference will not be modified or a const value is needed.

• You should have some way of displaying the list. For that, consider overloading operator<< for the List class (instead of a display function), allowing you to do this:

  List list;
  std::cout << list;
  

  You could also overload Node's operator, allowing you to output a node within the List class.

• std::out_of_range is defined in <stdexcept>, not <exception>.

Answer 2

IMO, if you're going to implement a linked list (probably shouldn't--they're pretty worthless) it's best to specify both the data and the next pointer when you create a node.

Node(const T &data, struct node *next = nullptr) : data(data), next(next) {}

This lets you simplify quite a bit of the insertion code. For example:

template <typename T>
void List<T>::PushFront(const T &data) {

    head = new node(data, head);

    if ( !tail )
        tail = head;
}

The other big thing that jumped out at me (that Jamal hasn't already discussed) was using NULL. I'd prefer nullptr, unless you're stuck with an ancient compiler that doesn't support it yet (in which case, you still want to do it, but after updating your compiler).