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

• Innkeeper: Hm, I realised there is no way of iterating through it. I should implement an iterator

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

• Innkeeper: Thank You! I might edit with the implemented iterator later.
• Jamal: @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.
• 200_success: What's the problem with the capitalization convention? I don't see any issue.
• Jamal: @200_success: More of a personal preference, I suppose. It just seems odd sharing it with types, variables, and functions.
• Innkeeper: 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?

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

• Jamal: 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.
• Emily L.: 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.
• Jerry Coffin: @EmilyL.: You sound like you were in the data structures classes I taught 20+ years ago. At that time, the advice was even sort of close to accurate. Unfortunately, it wasn't nearly as good then as I thought, and it's much less so now.
• Emily L.: @JerryCoffin "Right tool for the job" is no longer applicable? Then I'm out of a job :'( Jokes aside, I'm not saying to use linked lists for everything or even most things. I'm saying that there are use cases and you need to know what structure you need and how it will perform on your target machine. Blanket statements like "linked-lists are worthless" are not constructive or educational in any way.
• Jerry Coffin: @EmilyL.: Okay, if you find somebody making an unqualified statement that "linked-lists are worthless", feel free to tell them so. So far, you're showing much more about your inability to quote accurately than anything about linked lists though. If you really do have a good use-case for them, feel free to add it as an answer to this question.