3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ The list is generic in that it accepts any data structure, but what if one wants to actually read the values contained in it without printing them? \$\endgroup\$ – D. Jurcau Jun 25 '16 at 9:09
  • \$\begingroup\$ Ayecuyrumba! I've forgotten the most basic member function, traverse! Thanks! \$\endgroup\$ – logical123 Jun 25 '16 at 9:11
  • \$\begingroup\$ Consider designing the interface to conform to the Sequence concept; that would make it much easier for other C++ programmers to use your class, and you could use your class more easily with standard library components. \$\endgroup\$ – user14393 Jun 25 '16 at 9:17
  • 1
    \$\begingroup\$ FWIW C++11 introduced std::forward_list<T>, a singly linked list. That might be a good starting point to consider what functionality you should expose. \$\endgroup\$ – Aluan Haddad Jun 25 '16 at 10:44
4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.