Implementation of a templated Singly linked list class in c++

Question

The code below is my implementation of singly linked list.I would prefer it, if you kindly review the code and give me pointers on how a professional programmer would have written the code. Basically, i want to know about some good code habits that I have missed in the code.

The class one_way_linked_list is the linked list class. It uses the node class to create the nodes of the list. It keeps record of every object's head node using the head pointer. The function list_create() creates the list. The function list_print() prints the code. The function list_delete() deletes the linked list by deallocating every node one by one.

Sorry for my english, as it is not my native language. Thank you in advance.

#include <iostream>

using namespace std;

template<typename t>
class node
{

public:
    t data;
    node *next;

    //constructors
    node()
    {
        next=NULL;
    }
    node(t d)
    {
        data=d;
        next=NULL;
    }
};

template<typename t>
class one_way_linked_list
{
    node<t> n;
public:
    node<t> *head=NULL;
    node<t> *prev=NULL;

    void list_create(t);
    void list_print();
    void list_delete()
};

template <typename t>
void one_way_linked_list<t>::list_create(t dat)
{
    node<t> *ptr=new node<t>(dat);
    if(head==NULL)
{
    head=ptr;
    prev=head;
}
else
{
    prev->next=ptr;
    prev=ptr;
}
}

template<typename t>
void one_way_linked_list<t>::list_print()
{
    node<t> *ptr=this->head;
    cout<<"Printing the list: "<<endl;
    while(ptr!=NULL)
    {
        cout<<ptr->data<<" ";
        ptr=ptr->next;
    }
    cout<<endl;
}

template<typename t>
void one_way_linked_list<t>::list_delete()
{
    node<t> *ptr=new node<t>();
    ptr->data=this->head->data;
    while(ptr!=NULL)
    {
        ptr=ptr->next;
        delete ptr;
    }
    delete this->head;
    head=NULL;
    cout<<"Deleted"<<endl;
}

int main()
{
    //driver program for int type list
    one_way_linked_list<int> list1;
    int temp;
    while(1)
    {
        cin>>temp;
        if(temp==-1) break;
        else
        {
            list1.list_create(temp);
        }
    }
    list1.list_print();
    list1.list_delete();
    list1.list_print();
}

Answer 1

Don't use namespace std

Starting top down

using namespace std;

on file level is a very(!) bad idea. for a header file this is an absolute no go as you leak the namespace everywhere. in a cpp file you can get away with it but you increase the chance of a name collision. in a mixed file (like here) you should avoid it as it makes later refactoring more difficult. use it in implementation bodies only.

Use uppercase template types parameters

template<typename t> shall be template<typename T>, that is de facto standard

next=NULL; shall be next = nullptr;. NULLis a C-language leftover tha was finally fixed in C++11. Also, for the sake of readability, start using whitespace reasonably.

In class one_way_linked_list

node<t> n; is orphaned and shall be deleted

node<t> *head=NULL; again NULL and whitespace but you also use a different way to initialize compared to class node

prev shall be named tail to pair with head

Improve method naming scheme

Bad names list_create(t), list_print(), and list_delete(). you should always name functions with a verb. So print_list() would be a better name than list_print(). however the list_ prefix is completely needless and distracting duplication in one_way_linked_list<T>::list_print(). it is even more distracting in list_create(T dat) as this does not create a list bit inserts a node.

Also, you should try to use common names that can be interpreted by anybody. there are lots of containers in the standard library, you should follow the standard.

• list_create(t) should be named like insert(), add(), push_back() or so
• list_delete() should be named clear()

Don't implement printing to a stream

list_print() should not be there at all. you introduce a dependency on std::cout. it is for debugging only and it won't help you when writing to a file or serialize to a string. you could implement operator<< (member or non-member) to be more generic.

Issues with method/function implementation

void one_way_linked_list<t>::list_create

if(head==NULL) (again whitespace!) is more readable if written as if (!head). also you want to assign ptr to two variables but you use the previously assigned headin the next statement. therfore you did not see the statement is the same in both branches and may be moved outsie the if condition

if(head==NULL)
{
    head=ptr;
    prev=head;
}
else
{
    prev->next=ptr;
    prev=ptr;
}

should look like

if (!head)
{
    head = ptr;
}
else
{
    tail->next = ptr;
}
tail = ptr;

void one_way_linked_list<t>::list_print()

While it should not be there at all - here in this small scope you could use the std namespace for convenience

template<typename T>
void one_way_linked_list<T>::print()
{
    using namespace std;
    ...

void one_way_linked_list<t>::list_delete()

You should not clutter this function with std::cout. while you may do this during development it is inappropriate in code to be reviewed. For logging in production code use logging libraries.

Despite logging to cout the implementation is a complete mess. Starting with the first lines

node<t> *ptr=new node<t>();
ptr->data=this->head->data;

where a new node is constructed. nobody needs a new node for deletion. the value is saved for what?

while(ptr!=NULL)
{
    ptr=ptr->next;

and there it is. ptr gets assigned, the newly created node from before is not accessible anymore and can't be deleted, we leak memory.

    delete ptr;

wait, what was assigned to ptr? the default value of the newly created nodes member next which is the nullptr, right? For some reasons the gods of C++ decided this should not segfault. any other value than NULL would.

now, as we safely deleted the nullptr our loop ends as the ptr is NULL. we haven't deleted anything but leaked a node. let's go on after the loop.

delete this->head;
head=NULL;

cool. we have successfully deleted one node, the head node. the rest of the list is now dangling in memory. no one pointing to the second element, we leak another (n-1) nodes, altogether n nodes. but at least the list looks empty.

what we miss is

tail=NULL;

which potentially dangerous.

Additional notes

• For what functionality is missing compare to other containers from the standard library
• learn about std::shared_ptr and friends to avoid memory leaks
• learn to write unit tests to get at least the basic implementation tested and right
• care about readability (whitespaces, naming conventions, ...) to avoid causing pain to others

Answer 2

Advice 1

You can move the definition of node into the declaration body of one_way_linked_list. This allows "inheritting" the type parameter t, and, thus, omitting it altogether in the node.

Advice 2

node(t d)
{
    data=d;
    next=NULL;
}

The more C++ way would be:

node(t d) : data{d}, next{nullptr} {}

Advice 3

Most C++ programmers write the type parameters starting from an uppercase letter. In your case, I suggest you rename t to T in the template declaration.

Advice 4

public:
    node<t> *head=NULL;
    node<t> *prev=NULL;

Here, you expose the implementation details. Move the two under a private:. Also, write nullptr instead of NULL.

Advice 5

prev: a better name is tail.

Advice 6

list_create: a better name is add or append.

Advice 7

template<typename t>
void one_way_linked_list<t>::list_delete()
{
    node<t> *ptr=new node<t>();
    ptr->data=this->head->data;
    while(ptr!=NULL)
    {
        ptr=ptr->next;
        delete ptr;
    }
    delete this->head;
    head=NULL;
    cout<<"Deleted"<<endl;
}

rewrite as:

node<t>* next;
node<t>* current = head;

while (current) {
    next = current->next;
    delete current;
    current = next;
}