General advice on a practice linked_list for C++ classes/templates

Question

Introduction

I'm learning C++ (Coming from Haskell, C, and Assembly - and other languages sparsely) and this was my practice with classes and templates. It's a linked list that you can call in this fashion:

#include "list.hpp"

int main(void){
   linked_list<char> test;

   char c;

   while(c != '\n') //
      test.prepend(c = fgetc(stdin));

   std::cout << test;

   std::cout << std::endl;

   return 0;
}

Topic

I am here to ask if some more experienced coders would point out my mistakes (mainly about classes) so I can break the habits. Thanks for your help!

Here is the source code: (Btw, it isn't optimized on purpose, I was only playing with classes/templates)

(I do notice the inefficient and potentially dangerous tail() call, but considering the trivial nature of the project - I decided to leave it for later, simply make it a deque. I also naively checked it with memcheck. No leaks and no errors in my library, seemingly.) Ideone Link

//Compile with "g++ -std=C++11 -O2 -o list main.cpp list.hpp"

#ifndef LIST_H
#define LIST_H
#include <iostream>

template <typename T>
class linked_list {
    private:
        int empty = 1;

        struct node {
            T data;
            struct node * next;
        } * head;

        struct node * get_add(int index); 
    public:
        linked_list(){head = new node;};
        linked_list(T data){head = new node; head = data; empty = 0;}
       ~linked_list();

       int size();   
       inline int nsize(){return sizeof(struct node);};
       inline struct node * lhead() {return head;};
       inline struct node * tail() {return get_add(size()-1);};

       int search(T key);

       void prepend(T data);                                     
       void append(T data);
       int insert(T data, int index);
       int del(int index);

       int set(T data, int index);     
       T get(int index);      

       T& operator[](int i);                      
};  

template<typename  T>
std::ostream& operator<< (std::ostream &out, linked_list<T> &list); 

//////////////IMPLEMENTATION//////////////
//////////////////////////////////////////

template <typename T>
T& linked_list<T>::operator[](int i){
    return (get_add(i)->data);
}

template <typename T>
std::ostream& operator<< (std::ostream &out, linked_list<T> &list){
    int i;
    for(i = 0; i < list.size(); i++)
        out << list.get(i);
    return out;
}

template <typename T>
int linked_list<T>::size(){
    int i;
    struct node * tmp = head;

    for(i = 1; tmp->next != NULL; i++)
        tmp = tmp->next;

    return i;
}

template <typename T>
int linked_list<T>::set(T data, int index){
    if(index >= size())
        return -1;

    get_add(index)->data = data;

    return data;
}

template <typename T>
void linked_list<T>::prepend(T data){ 
    if(empty){
        head->data = data;
        empty = 0;
    } else {
        struct node * tmp = new node;
        tmp->data = head->data;
        tmp->next = head->next;

        head->data = data;
        head->next =  tmp;
    }
}

template <typename T>
void linked_list<T>::append(T data){
    if(empty){
        head->data = data;
        empty = 0;
    } else {
        struct node * tmp = new node;

        tmp->data = data;
        tmp->next = NULL;

        tail()->next = tmp;
    }
}

template <typename T>
int linked_list<T>::insert(T data, int index){
    if(index >= size())
        return -1;

    if(empty){
        head->data = data;
        empty = 0;
    } else {
        struct node * tmp = new node;
        struct node * location = get_add(index);
    struct node * prev = get_add(index-1);

    tmp->data = data;
    tmp->next = location;
        prev->next = tmp;
    }

    return 0;
}

template <typename T>
int linked_list<T>::del(int index){
    if(index >= size())
        return -1;

    struct node * prev = get_add(index-1);
    struct node * tmp = prev->next->next;

    delete prev->next;

    prev->next = tmp;

    return 0;
}


template <typename T>
int linked_list<T>::search(T key){
    int i;
    struct node * tmp = head;

    for(i = 0; key != tmp->data; i++)
        tmp = tmp->next;

    return i;
}

template <typename T>
T linked_list<T>::get(int index){
    if(index >= size())
        return 0;

    int i;
    struct node * tmp = head;

    for(i = 0; tmp->next != NULL && i < index; i++)
        tmp = tmp->next;

    return tmp->data;
}

template <typename T>
struct linked_list<T>::node * linked_list<T>::get_add(int index){
    if(index >= size())
        return 0;

    int i = 0;
    struct node * tmp = head;

    while(i++ < index)
        tmp = tmp->next;

    return tmp;
}

template <typename T>
linked_list<T>::~linked_list(){
    struct node * tmp = head->next;

    for(; head->next != NULL; tmp = head->next){
        head->next = head->next->next;  
        delete tmp;
    }

    delete head;
}
#endif

Thanks again.

Answer 1

This won't be as complete an answer as you often see on Code Review, but here are a few pointers to improve your code:

template <typename T>
T& linked_list<T>::operator[](int i){
    return (get_add(i)->data);
}

First of all, you should tell the programmer that your index will never be a negative one. In order to do so, you could change your int parameter to be an unsigned int one. Here, since we are talking about sizes, a size_t or std::size_t parameter would be even better:

template <typename T>
T& linked_list<T>::operator[](std::size_t i) {
    return get_add(i)->data;
}

C++ differentiates between functions that change the class members and functions that do not. If your function does not change the member variables, it should be const-qualified. Moreover, this qualification is a part of the function's signature. That means that you can have both the const-qualified version of the function in your class and the normal one:

template <typename T>
T& linked_list<T>::operator[](std::size_t i) {
    return get_add(i)->data;
}

template <typename T>
const T& linked_list<T>::operator[](std::size_t i) const {
    return get_add(i)->data;
}

You can apply my remarks about const-qualified functions to every function that should not change the class (e.g. size and search).

Now, let's talk about this piece of code:

template <typename T>
std::ostream& operator<< (std::ostream &out, linked_list<T> &list) { ... }

Let's have a look a the function's signature: your parameter is a linked_list<T>&. However, you should specify that this output function will not modify your list by adding a const before the type:

template <typename T>
std::ostream& operator<< (std::ostream &out, const linked_list<T> &list) { ... }

About for loops in C++:

int i;
for(i = 0; i < list.size(); i++)
    out << list.get(i);

In C++, you can use declaration statements in the first part of the for. That means that you don't have to declare your int i before the loop. You can declare it inside the for. And that is what should be done, unless you still need the value of i after you leave the loop. You can write it like this:

for(int i = 0; i < list.size(); i++)
    out << list.get(i);

And since your list can not have negative indices, the std::size_t is still welcome:

for(std::size_t i = 0; i < list.size(); i++)
    out << list.get(i);

We will now see this piece of code:

int search(T key);

While it is valid, you are passing key by value, which means that if you pass an instance of a big class (if T is a big class), it will be entirely copied before being used. In C++, if we don't need to modify the object passed to a function, it is better to pass it by const reference: it will not change the way you use it, but the compiler will use the address of the instance instead of doing a whole copy. To search, you don't need to modify your key, so it is better to pass by const reference:

int search(const T& key);

Answer 2

A specific note on memory management in particular:

• Don't use raw pointers (std::unique_ptr is better -- and then std::shared_ptr but only if you're absolutely sure you need to share) -- e.g., you can express the fact that your list owns the resource by using std::unique_ptr, while raw pointers leave the ownership semantics unexpressed & undocumented (it's best to be as clear as possible when expressing the intent in the code).
• Don't use raw new (right now you're leaking memory if you forget to delete after new -- and this happens all too often in practice) -- prefer make_unique (soon in the standard, for now just Google it) and std::make_shared instead.
• Prefer RAII.

See:
- http://speakerdeck.com/lichray/resource-management-the-c-plus-plus-way
- http://www.informit.com/articles/article.aspx?p=1944072
- http://klmr.me/slides/modern-cpp/
- http://www.hackcraft.net/raii/
- http://www.slideshare.net/adankevich/raii-and-scopeguard

Answer 3

• node doesn't have a constructor: this means that every instance you create starts out with a garbage next pointer, which could cause problems (besides, it's just nasty)

  struct node {
      T data;
      node *next; // note that node is a type name in C++
  
      // requires that T is default-constructable
      node() : next(NULL) {}
      // requires that T is copy-constructable
      node(T const &source) : data(source), next(NULL) {}
      // requires C++11 and that T is move-constructable
      node(T &&source) : data(std::move(source)), next(NULL) {}
  };
  

• you always new and then delete your head node, so the indirection doesn't buy you any flexibility (ie, it can never legally be NULL). So, just make it a regular member:

  node head; // this is a sentinel-style list head
  

  and now you never need to new or delete it. Now it has a default constructor too, you don't need to mention it in your constructors at all

• empty should be type bool, if it can only be true or false. However, we can do without it entirely, since the identity empty == (head.next == NULL) is required to be true. Let's just add

  bool empty() const { return head.next == NULL; }
  

  and use empty() instead of empty everywhere.

• conversely, size() is really expensive, so we can replace the member we just saved with int size; and use that instead of the function call

Answer 4

Here's a few issues that I noticed:

1. Initialising private member empty is not allowed

2. I would find it more natural to have the head pointer as just a struct node * instead of being a node itself. Then if head is NULL, the list is empty and the empty variable is not necessary.

3. I would prefer get_address, or at least get_addr to get_add

4. 2nd constructor should say head->data = data;

5. nsize better as sizeof(node)

6. tail fails if list is empty

7. do the method names match those of standartd containers?

8. operator[] fails if list is empty

9. use braces even on single-line blocks (after if, for, etc)

10. declare loop-variabless within loops where possible

11. size returns 1 even for an empty list

12. set returns int rather than T

13. in prepend it would be slightly easier to replace the head pointer with tmp

14. insert fails if index is zero. It would also be more logical just to search for index-1 (if index!=0) instead of searching for both index-1 and index

15. del fails if index is zero.

16. insert and del might be better returning bool rather than 0/-1

17. search should handle an empty list separately

18. get could be written using get_add