C++11 Singly Linked List with raw pointers

Question

Regarding C++, I have an experience in writing only short non-object-oriented programs and competitive programming challenges.

I would like to get your feedback about my C++ style, design decisions, and overall quality.

The below is the implementation of a Singly Linked List containing a multiset of values of type T. Type T is required to provide equal to operator. The class supports the following operations:

1. push a new value to the front of the list
2. push a new value to the end of the list
3. remove the first encountered occurrence of a given value
4. check if the list contains a given value
5. get the number of elements in the list
6. print the list in a pretty format
7. swap two lists

For the design, I decided to use both head and tail pointers to make both inserts constant time operations. For now, all pointers are raw pointers. The Node class is the internal class of LinkedList and an instance of LinkedList is responsible to delete its nodes. I decided to do that because this allows freeing the memory iteratively instead of recursively, which could cause problems if stack size is limited.

/* Singly Linked List by @pkacprzak */
#ifndef LINKED_LIST_HH__
#define LINKED_LIST_HH__
#include <ostream>
template<typename T>
class LinkedList {
public:
 LinkedList() {}
 LinkedList(const LinkedList& x) {
 auto cur = x.head;
 while (cur != nullptr) {
 pushBack(cur->val);
 cur = cur->next;
 }
 }
 LinkedList& operator=(const LinkedList& rhs) {
 LinkedList tmp(rhs);
 swap(*this, tmp);
 return *this;
 }
 ~LinkedList() {
 auto cur = head;
 while (cur != nullptr) {
 auto tmp = cur;
 cur = cur->next;
 delete tmp;
 tmp = nullptr;
 }
 }
 void pushFront(T val) {
 auto node = new Node(val);
 node->next = head;
 if (head == nullptr) {
 tail = node;
 }
 head = node;
 ++sz;
 }
 void pushBack(T val) {
 auto node = new Node(val);
 if (head == nullptr) {
 head = node;
 } else {
 tail->next = node;
 }
 tail = node;
 ++sz;
 }
 bool contains(T val) const {
 auto cur = head;
 while (cur != nullptr) {
 if (cur->val == val) {
 return true;
 }
 cur = cur->next;
 }
 return false;
 }
 void removeValue(T val) {
 if (head == nullptr) return;
 if (head->val == val) {
 auto cur = head;
 head = head->next;
 delete cur;
 if (head == nullptr) {
 tail = nullptr;
 }
 --sz;
 } else {
 auto cur = head->next;
 auto prev = head;
 while (cur != nullptr) {
 if (cur->val == val) {
 prev->next = cur->next;
 if (cur == tail) {
 tail = prev;
 }
 delete cur;
 --sz;
 return;
 }
 prev = cur;
 cur = cur->next;
 }
 }
 }
 int size() const {
 return sz;
 }
 friend std::ostream& operator<<(std::ostream& os, const LinkedList& x) {
 auto cur = x.head;
 os << "[";
 while (cur != nullptr) {
 os << cur->val;
 if (cur != x.tail) {
 os << ",";
 }
 cur = cur->next;
 }
 os << "]";
 return os;
 }
 friend void swap(LinkedList& a, LinkedList& b) {
 std::swap(a.head, b.head);
 std::swap(a.tail, b.tail);
 }
private:
 struct Node {
 Node(T val_) : val(val_) {}
 T val;
 Node* next = nullptr;
 };
 Node* head = nullptr;
 Node* tail = nullptr;
 int sz = 0;
};
#endif

• Incomputable: As I mentioned in the comment, please do not fix bugs mentioned in the answers. Let them pass. Only in extreme cases people will try to do something about it when upvoted answers are already present. On the side note: extensive testing before posting (and testing in general) will fix this. Try to learn how to write useful tests. May be google test will facilitate you.
• Loki Astari: Don't use double underscore. It is reserved for the implementation. LINKED_LIST_HH__ stackoverflow.com/a/228797/14065

Answer 1

Item 1. swap does not handle sz member

Item 2. No move constructor or operator= (no move semantic at all)

Item 3. Functions like contains get parameters by value - which is Ok for primitive types T and could be expensive for complex types

Item 4. No iterators - so not usable with algorithms. And also implementing something like remove_all is almost impossible - no indication of the remove success (except comparing size before and after), no possibility to continue scanning from the last location...

I suggest to take the std::forward_list http://en.cppreference.com/w/cpp/container/forward_list and try to emulate its API a lot closer then current attemp. Or justify your design choices explaining in more details why you think your change in the standard list API is superior to the stl approach.

Generally I like how the code looks and compiles. :)

• pkacprzak: Thaks a lot. Actually, the first item (member sz not swapped) is a bug, which I'll fix in the question.
• pkacprzak: By no operator= do you mean no such operator with move semantic?
• Incomputable: @pkacprzak, there are 2 operator=, one copy, and one move. The latter has parameter T&& other. Move constructor is missing too. Though they are disabled by explicit implementation of rule of 3, so everything is ok for now. Also, please do not edit the part of code which was mentioned in the review, leave it as it is.
• pkacprzak: @Incomputable I didn't implement them on purpose because I wanted this implementation to be a basic one. Thanks for clarification
• Matthieu M.: @pkacprzak: Take heed of the iterators here, if your class exposed iterators and erase(it), both contain and remove could be implemented using the STL algorithms. Throw in insert(it, value) and the user can insert an item at a specific spot without having to pop items from the list, push value and push the items back.

Answer 2

First of all, let me tell you that learning how to implement standard library features is not the best way to learn postmodern C++ or standard library. Try to apply it on problems you've seen. Try to refactor some code into standard library compatible components.

Good things

• Only necessary includes

  Well done. Having neat include list is one of the ways to achieve less compilation time and good dependency graph in general. One thing I would suggest is to bring <iosfwd> instead of <ostream>, as the former is even more compact.

• Properly implemented rule of three.

  I'm not sure if rule of five was implemented correctly by accident, but the copy functions will disable move functions, so it is more or less all right.

• Correct const qualifiers where appropriate.

  Not much to talk about this one, but in general, it is just another small piece which build up an insane code quality.

Things I didn't like

• No element access

  By far, very few people will be happy with absence of the observer function.

• No iterator support

  Iterators are fundamental concept. They are integral part of containers. Presence of iterators will eradicate following problems:

  • Ridiculous access complexity

    Users will just use the iterator to traverse back and forth, saving previous value if needed.

  • Rebuilding all of the algorithms from scratch

    With iterators, whole <algorithm> header will be available to them.

  • Storing index/reference/pointer to element.

    Iterator is an ultimate reference to an element in terms of containers. It provides a lot of information about container, element, location, etc.

  tl;dr: implement iterator support.

• No passing by reference in push and delete

  (削除) It has multiple issues, which I hope you'll learn by yourself. This is the lesson one needs to learn the hard way. (削除ここまで) Might not be that important for now.

• No emplace support

  Not all types are copy constructible. Especially from linked list, I would expect handling non-copyable types.

• int for size.

  int is required to be only non less than 16 bit. Some computers can have 128 GiB of memory. Use std::size_t for elements in memory. It might be a good candidate for size in general, but not necessarily so.

• Some other things that I don't think are that important.

Gotchas

Implement free swap, preferably put everything into namespace, so it wouldn't mess up ADL when people use it.

operator<< has a very big drawback: formatting! std::setw() applies only to first <<, then gets reset, which is very annoying. The output from a simulation got messed up, and I've been responsible for that. Fortunately matlab was confused enough to let us know before data got into paper...

• Matthieu M.: Note: arguably, passing by value in push is better (since the value can be moved from).
• Incomputable: @MatthieuM., not all types are moveable. So, it is still better to implement both copy and move versions.
• Lightness Races in Orbit: "int is required to be only 16 bit" I'm sure you meant to say that it the only size constraint on int is that it must be 16 bits or wider. The way you've phrased it, IMO, is misleading.
• Incomputable: @LightnessRacesinOrbit, yes, thank you. By the way, welcome back! Sorry for the last time. You would be a great contributor to our site.
• Matthieu M.: @Incomputable: That's true, in absolute. In practice it's also incredibly rare that a type cannot be movable, so for beginners I'd advise "Want speed? Pass by value." to avoid overwhelming them with trivia. There are bigger fishes in the pond.