Generic singly linked list using the C++11 standard

Question

This here is a templated singly linked list that I have been working on for the past couple of days in C++. I am not a programmer or computer scientist by training; finishing up my undergrad in physics this fall but trying to add more skills to my toolkit, so to speak.

I have been working my way through implementing the standard rigmarole of structures usually encountered in a data structures course. Here, I have tried to make my implementation generic by using templated classes. Any pointers, tips, flagrant errors, or anything else would be much appreciated.

#include <iostream>

template <typename Data>
class Node{
    template <typename T> friend class List;

    private:
        Data _val;
        Node<Data>* _nxt;
    public:
        Node(void)
            : _val {0}
            , _nxt {nullptr} {}
        Node(Data val)
            : _val {val}
            , _nxt {nullptr} {}
        Node(Data val, Node* nxt)
            : _val {val}
            , _nxt {nxt} {}
};

template <typename Data>
class List{
    private:
        Node<Data>* _head, * _tail;
        unsigned int _size;
    public:
        List(void)
            : _head {nullptr}
            , _tail {nullptr}
            , _size {0} {}
        List(Data val)
            : _head {new Node<Data> {val}}
            , _tail {_head}
            , _size {1} {}
        List(Node<Data>* val)
            : _head {val}
            , _tail {_head}
            , _size {1} {}
        List(Node<Data> data)
            : _head {new Node<Data> {data}}
            , _tail {_head}
            , _size {1} {}
        ~List(void) {}
        void insert(Data val, const unsigned int idx);
        void remove(const unsigned int idx);
        void print_list(void);
};

template <typename Data>
void List<Data>::insert(Data val, const unsigned int idx){
    Node<Data>* data {new Node<Data> {val}};
    if(_size == 0){
        _head = data;
        _tail = _head;
        _size = 1;
        return;
    }
    else if(idx == 0){
        data->_nxt = _head;
        _head = data;
        ++_size;
        return;
    }
    else if(idx >= _size){
        _tail->_nxt = data;
        _tail = _tail->_nxt;
        return;
    }
    else{
        Node<Data>* tmp {_head};
        for(int i {0}; i < idx-1; ++i)
            tmp = tmp->_nxt;
        data->_nxt = tmp->_nxt;
        tmp->_nxt = data;
        return;
    }
}

template <typename Data>
void List<Data>::remove(const unsigned int idx){
    if(_size == 0)
        return;
    else if(_size == 1){
        _head = nullptr;
        _tail = nullptr;
        return;
    }
    else if(idx == 0){
        Node<Data>* tmp {_head};
        delete _head;
        _head = tmp->_nxt;
        return;
    }
    else{
        Node<Data>* tmp {_head};
        for(int i = 0; i < idx-1; ++i)
            tmp = tmp->_nxt;
        Node<Data>* del {tmp->_nxt};
        delete tmp->_nxt;
        tmp->_nxt = del->_nxt;
        delete del;
        return;
    }
}

template <typename Data>
void List<Data>::print_list(){
    if(_head == nullptr)
        std::cout << "NULL";
    else{
        Node<Data>* tmp {_head};
        while(tmp != nullptr){
            std::cout << tmp->_val << ' ';
            tmp = tmp->_nxt;
        }
    }
    std::cout << std::endl;
    return;
}

int main(void){
    List<int> l {};
    for(int i {0}; i < 5; ++i){
        l.insert(i, 0);
        l.print_list();
    }
    l.insert(10, 4);
    l.print_list();
    l.remove(0);
    l.print_list();


    Node<int> n {5};
    List<int> l2 {n};
    l2.print_list();

    Node<int> n2 {15};
    List<int> l3 {&n2};
    l3.print_list();

    return 0;
}

Standard output:

0
1 0
2 1 0
3 2 1 0
4 3 2 1 0
4 3 2 1 10 0
3 2 1 10 0
5
15

Things that are on my mind:

• For the single node list case in remove, I seem to be having issues with deleting the head and tail pointers (line 84-88)? It functions fine as is but I'm pretty sure I'm supposed to deallocate those pointers, right?
• Will I run into issues with my List constructor with the template type as the parameter type? I was just thinking that somehow it could misinterpret a pointer to a node or a node itself as an actual Data, and use a node/node* as the template type. I'm not sure if that can actually happen.

Answer 1

A couple of things that jump out...

Constructors

I'm not a huge fan of passing Node's into linked lists. Besides exposing the list implementation it opens you up to confusion. Consider these two methods:

List(Node<Data>* val)
    : _head {val}
    , _tail {_head}
    , _size {1} {}
List(Node<Data> data)
    : _head {new Node<Data> {data}}
    , _tail {_head}
    , _size {1} {}

The first one takes in a pointer and directly uses it. Any other nodes that are pointed to by the node will be added to the list, although not included in size, so will be output by your print method, however will be beyond the tail of the list. That sounds wrong.

The second method only adds the data from the Node, which at least makes the list make sense, however isn't the behaviour I'd expect if I was passing in a Node chain.

Remove

You don't appear to be reducing _size when removing from the list. That looks like a bug. I'd also consider writing it based around the contents of the nodes (_head, _nxt) etc, rather than having decisions based around size, I find it easier to follow...

It also looks a lot like it will blow up if you try to remove index 100 from a list that only has 5 items in it.

Also, if the last item from the list is removed, it doesn't look like you're updating tail which means it'll blow up when you add to the end of the list afterwards.

Insert

If you insert to index 20, on a list that only has 5 items, it goes to index 6. This doesn't comply with the expected contract and is likely to cause confusion. Usually I'd expect methods like (add_head, add_tail). If you're allowing indexes, you should return some error if that index doesn't exist.

Count

If you track _size in a list, it's usually as a convenience variable for returning the count of the number of items in the list. You don't expose a method for doing this publicly, which seems like an omission.