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> *tail;
};

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

}

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

template <typename T>
void List<T>::PushBack(const T &data)
{
{
return;
}

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

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

if ( !tail )
{
}
}

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

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

while ( current->next != tail )
{
current = current->next;
}

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

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

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

}

template <typename T>
void List<T>::Clear()
{
{
delete current;
}

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
{
{
throw std::out_of_range("Can't return value from empty list");
}

}

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

return tail->data;
}

-
Hm, I realised there is no way of iterating through it. I should implement an iterator –  Innkeeper Apr 5 '14 at 17:47

• 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>.

-
Thank You! I might edit with the implemented iterator later. –  Innkeeper Apr 5 '14 at 19:59
@Innkeeper: You're welcome! As that change may affect more of your code, I'd recommend asking a new question with that implementation. Follow-up questions are okay here. –  Jamal Apr 5 '14 at 20:01
What's the problem with the capitalization convention? I don't see any issue. –  200_success Apr 6 '14 at 3:35
@200_success: More of a personal preference, I suppose. It just seems odd sharing it with types, variables, and functions. –  Jamal Apr 6 '14 at 3:38
If I overloaded operator<<, I still wouldn't have any way to iterate through and say, modify each item. Wouldn't an iterator/const iterator be more useful? Well, these could coexist, but I'm on the right track thinking this really needs an iterator, right? –  Innkeeper Apr 6 '14 at 9:56

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) {

if ( !tail )

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).
I haven't forgotten about nullptr, but I sometimes feel tempted to not bring it up if it appears that the OP isn't already using C++11. –  Jamal Apr 6 '14 at 3:34
Linked lists are not worthless, you need to know when to use the correct data structure. Linked lists have constant time insertion and deletion at the front and tail or anywhere where you already have a pointer. If you are frequently inserting or deleting at the front or tail (like a queue) then a linked list is just fine. A plain vector or array would perform terribly in this case making a pop operation an $\mathcal{O}(n)$ operation. –  Emily L. Aug 21 '14 at 15:26