Templated Singly-Linked List

Question

I'm really new to C++ (very surprised at the leap from Python and others to C++!). The code compiles and works well. This took all day to get to work, and I've the tendency to move on after I get [what I see as] basic functionality. I'd really like to become a good programmer, though.

I assume there are a ton of things I'm doing wrong, but I don't know what they are.

Although I've read a lot about them, I still don't fully understand when I should use a pointer. I know what they are, and what its difference is with a reference—but I haven't grokked why I should use one over the other.

Also, everything I've read about implementing the STL iterator (and I've read quite a bit on that) confuses the hell out of me, so I wrote a pretty basic one instead.

//====================
// Include Guard
#ifndef __LINKEDLIST_HPP_INCLUDED__
#define __LINKEDLIST_HPP_INCLUDED__
//===================
// Included Dependencies
#include <iostream>
#include <iterator>
//====================
// Forwarded Dependencies
//====================
// Classes (Header)
template<class T> class Node {
 public:
 Node();
 Node(T object);
 T getObject();
 Node* next_;
 private:
 T object_;
};
template<class T> class ListIterator {
 public:
 ListIterator(Node<T>* head_node);
 T next();
 private:
 Node<T>* current_node;
};
template<class T> struct LinkedList {
 public:
 LinkedList (T initialObject);
 ~LinkedList();
 void addObject (T addedObject);
 void removeObject (int position); 
 int getSize();
 ListIterator<T> getIterator();
 private:
 Node<T>* head_;
 Node<T>* current_;
 int size_;
};
//====================
// Class (Instantiation)
template<class T> Node<T>::Node() {};
template<class T> Node<T>::Node(T object) { object_ = object; };
template<class T> T Node<T>::getObject() { return object_; };
template<class T> ListIterator<T>::ListIterator(Node<T>* head_node) {
 current_node = head_node;
};
template<class T> T ListIterator<T>::next() {
 Node<T>* tmp_node = current_node;
 current_node = current_node->next_;
 return current_node->getObject();
};
template<class T> LinkedList<T>::LinkedList(T initialObject) {
 head_ = new Node<T>;
 current_ = new Node<T>(initialObject);
 head_->next_ = current_;
 current_->next_ = head_;
 size_ = 1;
};
// Destructor
template<class T> LinkedList<T>::~LinkedList() {
 for (int ii = 0; ii <= size_-1; ii++) {
 Node<T>* tmpNode = head_->next_;
 head_->next_ = head_->next_->next_;
 delete tmpNode;
 };
 delete head_;
};
// Add object. Link it to head to make this circular
template<class T> void LinkedList<T>::addObject(T addedObject) {
 Node<T>* tmpNode_ = current_;
 current_->next_ = new Node<T>(addedObject);
 current_ = current_->next_;
 current_->next_ = head_;
 size_ += 1;
};
// Remove the node in the spot specified by 'position'
template<class T> void LinkedList<T>::removeObject(int position) {
 if (position <= 0) { std::cout << "ERROR: Invalid position."; }
 else if (size_ > 0 && position <= size_) {
 Node<T>* tmpNode_ = head_;
 for (int ii = 0; ii < position-1; ii++) {
 tmpNode_ = tmpNode_->next_;
 };
 delete tmpNode_->next_;
 tmpNode_->next_ = tmpNode_->next_->next_;
 size_ -= 1;
 }
 else if (size_ > 0 && position > size_) { 
 std::cout << "ERROR: LinkedList contains less than " << position 
 << " elements\n"; 
 }
 else if (size_ == 0) { std::cout << "ERROR: LinkedList is empty\n"; }
};
// Return size of Linked List
template<class T> int LinkedList<T>::getSize() { return size_; };
// Return iterator
template<class T> ListIterator<T> LinkedList<T>::getIterator() {
 return ListIterator<T>(head_);
};
#endif

Answer 1

1. Node
   1. There is no need to make Node public. LinkedList and ListIterator need it but client of your library doesn't. So consider hiding it from him. For example by defining Node within the LinkedList class.
   2. Node()
      1. It would be cleaner if next_ would be set to nullptr (if in C++11 or above) or NULL/0 (otherwise).
      2. There should be no use for default constructor anyway. (See below notes on LinkedList<T>::head_.) In fact use of this constructor requires type T to be DefaultConstructible while there is no need to require that.
   3. Node(T object)
      1. Use member initializer list instead of assigning to members in constructor's body.
      2. It would be cleaner if next_ would be set to nullptr (if in C++11 or above) or NULL/0 (otherwise).
      3. Change argument to const T& if you are pre-C++11.
      4. Otherwise use move semantics when constructing object_ from object. And also possibly add const T& overload anyway.
   4. getObject()
      1. Return T& instead of T as it would not require copying of the object.
      2. And add const overload which returns const T&.
   5. next_
      1. Should not be a public member! Make it private and grant to LinkedList and ListIterator access to for example using friend.
   6. It could be useful to forbid copying of Node objects as it seems there is no use in that. To do that use boost::noncopyable if you have Boost. If you don't then either explicitly "delete" copy constructor and assignment operator (if in C++11 or above) or make them private without defining them.
2. ListIterator
   1. As you noted yourself your iterator differs significantly from what C++ considers and iterator. This means in particular that it will not be usable with any STL function. Or other libraries that use "normal iterators".
   2. As a side note I will mention that boost::iterator_facade makes it much easier to write proper iterator. But it requires use of Boost.
   3. With your current design as it is how will you know that the iteration ended? There is no method in ListIterator that says that. With your current implementation (of cyclic list - see comments in LinkedList) any iteration would be infinite unless you would count elements yourself during iteration and stop at getSize.
   4. ListIterator(Node<T>* head_node)
      1. Use member initializer list instead of assigning to members in constructor's body.
   5. next()
      1. Implementation incorrectly returns value from current_node. It seems that instead it should return value from tmp_node.
      2. Return T& instead of T as it would not require copying of the object. (But to do that you have to do the same for Node<T>::getObject() as commented above.)
   6. Consider having also a ConstListIterator which uses const Node<T>* and returns const T& from next(). This would allow to iterate over const LinkedList object. With some template magic this could be done with single implementation.
3. LinkedList
   1. From implementation it seems to be a cyclic list. Was this intended?
   2. I don't follow the idea behind head_ node. I think that it is not needed. Not to mention that it's value could be undefined while it will show up during iteration.
   3. The class would be a bit more usable if you could add element at arbitrary position. Given by integer (to make your design consistent) or iterator (to be consistent with previous comment).
   4. The class would be a bit more usable if you could remove element based on iterator. Or else allow the iterator to return it's position as integer. But remove by iterator is more in line with C++ (STL) style.
   5. The class would be a bit more usable if it allowed also const iteration. So getIterator() should have a const overload returning const iterator (as commneted above).
   6. Size in C++ is usually expressed using std::size_t type. So should be also positions in your case.
   7. There should be a default constructor making an empty list.
   8. LinkedList(T initialObject)
      1. Consider making it explicit so that it cannot be used for conversion.
      2. Add also second argument being count of initial elements. And default it to 1. It would make the constructor a bit more flexible and little cost. (And also it will match typical STL container constructors.)
      3. Change argument to const T& if you are pre-C++11.
      4. Otherwise use move semantics when constructing object_ from object. And also possibly add const T& overload anyway.
      5. Use member initializer list instead of assigning to members in constructor's body.
   9. You should properly define copy constructor and assignment operator. Or at least forbid them (as already mentioned for Node).
   10. Consider adding other constructors. For example from a range of elements of other list (by positions or by iterators).
   11. ~LinkedList()
       1. <= size_-1 in loop condition is risky. Once you change to (unsigned) std::size_t (as commented above) size_-1 for size_ == 0 would wrap around 0 and result in maximal positive value. The loop would be infinite. On the other hand note that alternative < size_ results in infinite loop for size_ being already maximal positive value. (Which however seems less likely than being 0.)
       2. In loop use ++ii rather than ii++. On modern compilers with integers it doesn't matter really. But it is cleaner to write so. And could make a difference if ii would be an iterator rather than integer. So it is better to have good habits.
   12. addObject(T addedObject)
       1. Unused tmpNode_ local variable.
       2. I would write ++size_ instead of size_ += 1. Feels more natural. But in the end there should be no difference.
       3. You are making no check against exceeding maximal positive value for size_.
       4. Change argument to const T& if you are pre-C++11.
       5. Otherwise use move semantics when constructing Node<T> from addedObject. And also possibly add const T& overload anyway.
   13. removeObject(int position)
       1. Instead of writing to cout use exceptions. There are also other means (like returning error code). But outputting to cout is of no use. (And cerr seems more adequate anyway...)
       2. < position-1 in loop condition is risky. Once you change to (unsigned) std::size_t (as commented above) position-1 for position == 0 would wrap around 0 and result in maximal positive value. The loop would be go crazy (although it would not be infinite). Instead of that you could start with ii = 1.
       3. In loop use ++ii rather than ii++. On modern compilers with integers it doesn't matter really. But it is cleaner to write so. And could make a difference if ii would be an iterator rather than integer. So it is better to have good habits.
       4. You could extract the loop fragment to separate (private) method which returns Node<T>* of given position. It would make code somewhat cleaner. And also you could reuse the method in other functions that I recommended to add (in comments above).
       5. You should first store tmpNode_->next_ in a local variable. Then set tmpNode_->next_ to tmpNode_->next_->next_. And only then delete the local variable. Current code uses next_ of already deleted object and sooner or later will crash on that.
       6. I would write --size_ instead of size_ -= 1. Feels more natural. But in the end there should be no difference.
       7. This method is badly implemented anyway. For example on a list constructed with the single element constructor calling removeObject(1) will actually delete the node from head_ but will never update head_ member. Maybe changing the condition to position < size_ (and next to position >= size_) would correct it. But since the idea of head_ is likely wrong this method would change anyway.
   14. getSize()
       1. Should be a const method as it doesn't change the object.

There are also other possible extensions. For example you could add allocator support. Or allow in-place construction of elements. But those are more advanced topics. Maybe save them for later.

• AmagicalFishy: I thought this was going to go unnoticed! The cyclic iterator was purposeful; the objects I'm going to use this for will all have unique ID numbers, so the iterator will end when the ID of one of the objects repeats. Thanks so much for your corrections—I'll start working on them immediately.
• AmagicalFishy: One more question: If I define Node within Linked List—then I'd have to define the iterator within Linked List too, right? (If I did that, wouldn't Node and the iterator have to be public anyway?)
• Adam Badura: @AmagicalFishy If Node is made private within LinkedList then either ListIterator must be defined within LinkedList or must be a friend of it.