3
\$\begingroup\$

Seeking recommendations on how to improve this code, LL always seem to be a struggle.

A basic linked list that does include next and previous pointers. I used a struct inside of a class, which I'm not sure if that's frowned upon. The program includes 5 basic member functions, one to add to the head of the list, one to add to the tail of the list, one to delete the head, one to delete any index, one that checks the list for duplicate data (based on the data variable in the struct), and a print. Everything works as it should, but I'm just not sure if I was efficient, in fact I'm pretty sure I wasn't. Sorry If im forgetting something, but I'm new here!

1.

class list
{
private:
    struct node
    {
        int data;
        node* next;
        node* prev;
    };

    typedef node* nodePtr;

    nodePtr head;
    nodePtr temp;
    nodePtr prev;

public:
    list(); 
    void add_to_head(int);
    void add_to_tail(int);
    void delete_index(int);
    void check_duplicates(int);
    void print();
};

2.

#include <iostream>
using std:: cout;
using std:: endl;


list::list(void)
{
    head = NULL;
    temp = NULL;
    prev = NULL;
}

void list:: add_to_head(int num)
{
    nodePtr n = new node;

    n->data = num;

    if(head == NULL)
    {
        n->prev = NULL;
        n->next = NULL;
        head = n;

    }
    else
    {
        n->next = head;
        n->prev = NULL;
        head = n;
    }

    return;
}


void list::add_to_tail(int num)
{
    nodePtr n = new node;

    n->data = num;

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

        while(temp->next != NULL)
        {
            temp = temp->next;
        }

        temp->next = n;
        n->prev = temp;
        n->next = NULL;
    }

    return;
}

void list::delete_index(int index)
{
    if(index == 0)
    {
        temp = head->next;
        temp ->prev = NULL;

        prev = head;
        delete prev;

        head = temp;
    }
    else
    {
        nodePtr del = new node;

        int count =0;
        temp = head;

        while(count != index)
        {
            prev = temp;
            temp = temp->next;
            count++;    
        }

        del = temp;

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

        delete del;
    }

    return;
}


void list::check_duplicates(int num)
{
    int count = -1;

    temp = head;

    while(temp != NULL)
    {
        if(temp->data == num)
        {
            count++;
        }

        temp = temp->next;
    }

    if(count > 0)
    {
        cout<<endl<<endl<<"The number "<<num<<" was found "<<count + 1<<" times."<<endl;
    }

    else if(count == -1)
    {
        if(head == NULL)
        {
            cout<<"The list is empty."<<endl;
        }
        else
        {
            cout<<"The number was not found within the list."<<endl;
        }
    }

    return;
}


void list::print()
{
    temp = head;

    cout<<endl<<"The list:"<<endl;

    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }

    return;
}
\$\endgroup\$
  • \$\begingroup\$ improve with opportunities C++11/C++14? \$\endgroup\$ – user110702 Jul 14 '16 at 15:28
  • \$\begingroup\$ Sorry, I should've put that. C++11 \$\endgroup\$ – user111415 Jul 14 '16 at 15:30
  • 1
    \$\begingroup\$ It's easier to help if you provide some information about what the code does. Please consider adding some explanations. Thanks =) \$\endgroup\$ – Stewie Griffin Jul 14 '16 at 15:37
3
\$\begingroup\$

You can simplify your code a lot.

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

Both sides of this else look identical.
I think you can shorten your code with:

void list:: add_to_head(int num)
{
    nodePtr oldHead = head;
    head = new node{num, oldHead, nullptr);
    // Also you forget to do this bit.
    if (oldHead) {
        oldHead->prev = head;
    }
}

@pm100 covered the temporary variable.

nodePtr temp;
nodePtr prev;

You don't need these as a class member. It should be local to the member functions where they are used.

If I was you I would add another member though.

nodePtr tail;

Then you don't need to search for the tail every time you add a new element.

Const correctness. In a lot of code we pass variables by reference and const reference. If you pass an object by const reference you can only call const members on it.

So you should take care to mark functions that don't mutate the object as const. This will allow you to call the methods from a const reference. Also it enables some compiler optimizations when it knows you are not mutating the object.

So the following functions should probably be const.

void check_duplicates(int) const;
void print() const;

Your print() is fine. But I would make it more generic. Rather than print to std::cout you should print to a generic stream (you can always default to std:::cout.

print(std::ostream& str = std::cout) const;

Also in C++ printing is usually done via operator<<. So I would add this function. All it needs to do is call the print function passing the stream.

std::ostream& operator<<(std::ostream& str, List const& data)
{
     data.print(str);
     return str;
}
\$\endgroup\$
2
\$\begingroup\$
  • Class design

    A member called temp is an immediate red flag. It doesn't represent any state of the list, it is just a variable used to traverse a list, and shall be defined where it is used. Make it local to appropriate methods.

    Same applies to prev.

    Some methods (particularly, delete_index) may crash on bad inputs. If it is a conscious design decision, it must be documented.

    I highly recommend to have nodeptr tail; member.

  • struct node better have a constructor

    node(int num): data(num), prev(nullptr), next(nullptr) {}
    
  • add_to_head doesn't update the old head's prev. Besides, it looks unnecessary complicated. Consider

    add_to_head(int num) {
        nodeptr n = new node(num);
        n->next = head;
        if (head) {
            head->prev = n;
        }
        head = n;
    }
    
  • delete_index leaks memory:

        del = new node;
        ....
        del = temp;
    
\$\endgroup\$
2
\$\begingroup\$

A few basics.

You might want to consider a naming convention for member variables. m_head or head_ are common ones. Some people find this useful, others not.

I assume the few places you have an extra space after :: is just a typo

use nullptr instead of NULL

It is unusual to have a print method for a container like this. Why not a save, load, etc. As long as you make it trivial to iterate over the list then you dont need a print

delete_index is an odd name. It suggests that an index is going to be deleted. I would call it delete_at or just plain delete.

temp (and probably prev) do not need to be class members. They are just local variables of some methods

major points

OK how about access methods. Like get_at and first / next. At the moment I can put things in the list but not get them out!

c++ people will expect iterators

It only stores ints, make it generic - you will learn a lot

\$\endgroup\$
  • 1
    \$\begingroup\$ Using a naming convention like that is not that common in C++. A case of selection bias I think. \$\endgroup\$ – Martin York Jul 14 '16 at 16:23
  • \$\begingroup\$ I agree you don't need a print. But everybody that writes a container for the first time includes one. You may be better off explaining how to do it in a C++ like manner with operator<< and operator>> \$\endgroup\$ – Martin York Jul 14 '16 at 16:25
  • \$\begingroup\$ @LokiAstari I googled c++ naming convention. The first one I hit was google.github.io/styleguide/cppguide.html#Variable_Names \$\endgroup\$ – pm100 Jul 14 '16 at 17:24
  • \$\begingroup\$ 1) I am not sure what the proves. 2) Google style guide for C++ (though it is getting better) is consider generally as a bad style guide for C++ programmers in general (it is more specific to Google than to general C++). I point you at: google.github.io/styleguide/cppguide.html#Exceptions Now that's a bad idea. \$\endgroup\$ – Martin York Jul 14 '16 at 17:36
  • 1
    \$\begingroup\$ google.github.io/styleguide/cppguide.html#Spaces_vs._Tabs Arggg two spaces. (OK don't care that much). Looks a lot better than the last time I read it though. But naming convention on members varies greatly from company to company. The only real standard (as defined by Stroustrup) is that user defined types have an initial capitol letter. And I agree with that one. But saying it was universal would be overstating it. \$\endgroup\$ – Martin York Jul 14 '16 at 17:43

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.