2
\$\begingroup\$

I created a linked list in C++ using class with few methods to provide interface for it.

Methods are pushFront(), traverse() and few more as shown below. PushFront is used to insert the data at the head of linked list at any given time. traverse is to display the linked list at any time. My code is shown below:

#include <iostream>
using namespace std;
class SingleLL{
    private:
    struct Node
    {
        int data;
        Node * next;
    };
    Node * head;
    Node * tail;
    public:
    SingleLL();
    void pushFront(int i);
    int topFront(); 
    void popFront();
    void pushBack(int i);
    int topBack();
    void popBack();
    bool find(int key);
    void erase(int key);
    void addBefore(int beforekey,int key);
    void addAfter(int afterkey,int key);
    bool empty();
    void traverse();
};
SingleLL::SingleLL(){
     head = nullptr;
     tail = nullptr;
}
void SingleLL::pushFront(int i)
{
    Node * newNode =new Node;
    newNode->data=i;
    newNode->next=head;
    head=newNode;
    if(tail==nullptr)
        tail = head;
}
int SingleLL::topFront()
{
    if(empty())
    {
        cout<<"No element at the front top.\n";
        return 0;
    }
    return head->data;
}
void SingleLL::popFront()
{
    if (empty()){
        cout<<"No element to pop.\n";
        return;
    }
    head=head->next;
    if(head==nullptr)
        tail=nullptr;
}
void SingleLL::traverse()
{
    if (empty())
        cout<<"empty list. add elements";
    Node * ptr =  head;
    while(ptr!=nullptr)
    {
        cout<<ptr->data;
        ptr=ptr->next;
    }
}
bool SingleLL::empty()
{
    return head==nullptr;
}
int SingleLL::topBack()
{
    if(empty())
    {
        cout<<"No element at the back top.\n";
        return 0;
    }
    return tail->data;
}
void SingleLL::popBack()
{
    if(empty()){
        cout<<"No element to pop\n";
        return;
    }
    Node *ptr=head;
    if(head->next==nullptr)
    {
        head=nullptr;
        tail=nullptr;
    }
    while(ptr->next->next != nullptr)
    {
        ptr=ptr->next;

    }
    tail=ptr;
    ptr->next=nullptr;
}
void SingleLL::pushBack(int i)
{
    Node * newNode2 =new Node;
    newNode2->data=i;
    newNode2->next=nullptr;
    if(tail!=nullptr)
        tail->next=newNode2;
    tail=newNode2;
    if(head==nullptr)
        head=tail;


}
bool SingleLL::find(int key)
{
    if(head == nullptr)
        return false;
    Node * boolfinder = head;

    while(boolfinder->next!=nullptr)
    {
        if(boolfinder->data==key)
        {
            return true;
        }
        boolfinder=boolfinder->next;

    }
    return false;
}
void SingleLL::erase(int key)
{
    if(find(key))
    {
        if (head->data==key)
        {
            popFront();
            return;
        }
        if(tail->data==key)
        {
            popBack();
            return;
        }
        Node * finderprev = head;
        Node * findererase = head->next;
        while(findererase!=nullptr)
        {
            if(findererase->data==key)
            {
                finderprev->next=findererase->next;
                free(findererase);
                break;
            }
            findererase=findererase->next;
            finderprev=finderprev->next;
        }
    }
    else
        cout<<"There is no such key to erase";
}
void SingleLL::addAfter(int afterkey,int key)
{
    Node * newNode =new Node;
    newNode->data=key;
    Node * ptr = head;
    while(ptr!=nullptr)
    {
        if(ptr->data==afterkey)
        {
            newNode->next=ptr->next;
            ptr->next=newNode;
            if(newNode->next==nullptr)
                tail=newNode;
            return;
        }
        ptr=ptr->next;
    }

    cout<<"There is no "<<afterkey<<" key to add "<<key<<" key before it.";

}
void SingleLL::addBefore(int keybefore,int key)
{

    if(head->data==keybefore)
    {
        pushFront(key);
        return;
    }
    Node * newNode1 = new Node;
    newNode1->data=key;
    Node *ptr = head->next;
    Node *ptrprev = head;
    while(ptr!=nullptr)
    {
        if(ptr->data==keybefore)
        {
            newNode1->next=ptr;
            ptrprev->next=newNode1;
            return;
        }
        ptr=ptr->next;
        ptrprev=ptrprev->next;
    }
    cout<<"There is no"<<keybefore<<" key to add "<<key<<" key before it.";

    }
int main()
{
    SingleLL l1;
    for(int i=10;i>=1;i--)
        l1.pushFront(i);
    l1.traverse();
    l1.popFront();
    cout<<"\n";
    l1.traverse();  
    for(int i=0;i<8;i++)
        l1.popFront();
    cout<<"\n";
    l1.traverse();
    l1.popFront();
    l1.popFront();
    l1.popBack();
    if(l1.empty())
        cout<<"linked list is empty.\n";
    l1.topBack();
    l1.popBack();
    return 0;
}

I know that many things that I have used is not upto mark, like I have used struct like in old c where it contains data only. I have seen implementation of linked list using class in few other languages like java and python. But since C++ takes many or we can say all features from c language and adds O.O.P.to that, there are many things different in this language. Can anyone provide me the valuable code review and point out what are the things that I need to improve in my coding style. And how can I improve my O.O.P. design skills. What are the mistakes in this code? And also what changes should I do to make it full modern powerful C++ code? And even though I will try it myself anyways i need valuable insight from this community on how to templatize or make this class generic so that it takes any atomic data type not only integer type as it does now.

\$\endgroup\$
  • 1
    \$\begingroup\$ C++ doesn't just bolt on OOP, but adds support for more paradigms. Pure OOP isn't really good C++ anyways. And there is Nothing wrong with having a POD, especially as an implementation-detail. \$\endgroup\$ – Deduplicator Jan 9 at 22:23
  • \$\begingroup\$ You don't want to use cout << … inside a library as you might not always want to see the text on the console. \$\endgroup\$ – Phil1970 Jan 12 at 16:38
5
\$\begingroup\$

Code Review:

Please stop doing this:

using namespace std;

It's a bad habit that will one day cause you lots of grief because it can silently change the meaning of the code. See: Why is “using namespace std” considered bad practice?

Not indenting after public/private makes it very hard to spot the public interface:

class SingleLL{
    private:
    Node * head;
    Node * tail;
    public:
    SingleLL();
};

Much easier if you had written like this:

class SingleLL{
    private:
        Node * head;
        Node * tail;
    public:
        SingleLL();
};

The * is part of the type. Put it with the type not half way to the identifier.

Node * head

Prefer to use the initializer list to initialize member variables.

SingleLL::SingleLL(){
     head = nullptr;
     tail = nullptr;
}

Like this:

SingleLL::SingleLL()
   : head(nullptr)
   , tail(nullptr)
{}

If the members had constructors then you would have constructed them before the code block then re-assigned them with the assignment operator. I know it seems trivial but changing types is a common maintenance task. If the type of the object but was expecting the behavior to not change then you now if a non optimal initialization strategy.

Sure this works:

void SingleLL::pushFront(int i)
{
    Node * newNode =new Node;
    newNode->data=i;
    newNode->next=head;
    head=newNode;
    if(tail==nullptr)
        tail = head;
}

But it is very verbose. Why not create and initialize the object in one go?

void SingleLL::pushFront(int i)
{
    head = new Node{i, head};
    if(tail==nullptr)
        tail = head;
}

I know checking is the nice thing to do.

int SingleLL::topFront()
{
    if(empty())
    {
        cout<<"No element at the front top.\n";
        return 0;
    }
    return head->data;
}

But if your code guarantees that the list has values then this becomes a waste of time:

// Here I am checking that the list is not empty before
// entering the loop and getting the value. So the internal
// check is completely wasted.
while(!list.empty()) {
    std::cout << list.topFront();
    list.popFront();
}

There are times though when a check should be done. So most containers provide two accesses mechanisms. Both a checked and an un-checked version. It may be worth adding an unchecked version for situations where you don't need to check (like the loop above).

Same comment as above.

void SingleLL::popFront()
{
    if (empty()){
        cout<<"No element to pop.\n";
        return;
    }
    head=head->next;
    if(head==nullptr)
        tail=nullptr;
}

I would also note that printing to the output so not a good idea for a generic container. Throw an exception or do nothing.

Sure have a traverse.

void SingleLL::traverse()
    // STUFF
        cout<<ptr->data;

But why std::cout? You may not want to print it. Allow the caller to pass in a function and do an operation on the data. Then call the function for each node.

That's a good test.

bool SingleLL::empty()

But it does not modify the state of the object. So you should mark it as a const method. bool SingleLL::empty() const.


Update to implement traverse to show that you can apply an external function to all elements in the list:

Original code:

void SingleLL::traverse()
{
    if (empty())
        cout<<"empty list. add elements";
    Node * ptr =  head;
    while(ptr!=nullptr)
    {
        cout<<ptr->data;
        ptr=ptr->next;
    }
}

Modify to pass function/functor/lambda

// Use a template for the function
// This is because there are several different types that can
// act like a function and you should be able to support all of them.
// --
// If you want to limit this and support only a specific type that
// is possible.
// --
// Alternatively you can use the std::function<void(int)> will
// work just as well and be a specific type that accepts most function
// like objects.
template<typename F>
void SingleLL::traverse(F const& action)
{
    Node * ptr =  head;
    while(ptr!=nullptr)
    {
        action(ptr->data);
        ptr=ptr->next;
    }
}

Now we can call traverse like this:

SingleLL   list;
// Add items.

// Pass a lambda
list.traverse([](int val){std::cout << val << " ";});

// Pass a functor
struct Functor {
    void operator()(int val) const {std::cout << val << " ";}
};
list.traverse(Functor{});

// Pass a function
void function(int val) {std::cout << val << " ";}
list.traverse(&function);

----

// Now the reason in allowing traverse() to have an action ist
// that you can now manipulate the data in the list (not just print it)

list.traverse([](int& val) const {val += 2;}); // Add two to each member.

int  count[2] = {0,0};
list.traverse([&count](int val) const {++count[val%2];}); // Count odd and even values in the list.
\$\endgroup\$
  • \$\begingroup\$ Thanks Martin for this review. Learnt many things from this single review. I also wanted to ask what would be the best practices to make this class generic. At this point it takes data which are integers only. I want to templatize it. And may be i could use template specialization so that i could add other nodes or linked lists as data like extend() in python or '+' operator for strings in C++. What would be the major things to take care in such case? \$\endgroup\$ – shishir jha Jan 15 at 8:25
  • \$\begingroup\$ If anyone is watching, I have one doubt in above code review which i realised after this much time. Martin here advised me to allow the caller to pass the function to my traverse method right? As far as I know, unlike python, functions are not objects in c++ so we cannot pass the name of the function as argument in c++ right? the only way i can think of to achieve that is to use function pointers. Can anyone help me with that? \$\endgroup\$ – shishir jha Jun 11 at 11:38
  • 1
    \$\begingroup\$ @shishirjha You can not pass a function by name. But you can pass any function like object. This includes function pointer, functor (function like object ie an object of a class that implements operator()) and lambda (syntactic sugar to create an anonymous functor). \$\endgroup\$ – Martin York Jun 11 at 12:57
  • \$\begingroup\$ @shishirjha Added an example to the end that uses a lambda. \$\endgroup\$ – Martin York Jun 11 at 13:02

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.