3
\$\begingroup\$

Problem: Given a singly linked list of integers l and an integer k, remove all elements from list l that have a value equal to k.

My solution works, but I suspect it's not smart and optimized because I have many extra variables to solve this question.

Node.h:

#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED

 template<typename T>
 struct ListNode {
   ListNode(const T &v) : value(v), next(nullptr) {}
   T value;
   ListNode *next;
};

#endif // NODE_H_INCLUDED

main.cpp:

#include<iostream>
#include "Node.h"

void print(ListNode<int> * l){
    while(l != nullptr){
        std::cout << l->value << "\n";
        l = l->next;
    }
}

ListNode<int> * removeKFromList(ListNode<int> * l, int k) {
    if(l == nullptr){
        return nullptr;
    }else{
        if(l->value != k){
            ListNode<int> * L2 = new ListNode<int>(l->value);
            ListNode<int> * current = L2;
            l = l->next;
            while(l != nullptr){
                if(l->value != k){
                    ListNode<int> * L3 = new ListNode<int>(l->value);
                    while(current->next != nullptr){
                        current = current->next;
                    }
                    current->next = L3;
                }
                l = l->next;
            }
            return L2;
        }else{
            return removeKFromList(l->next, k);
        }
    }
}

int main(){
    ListNode<int> * L = new ListNode<int>(5);
    ListNode<int> * L1 = new ListNode<int>(6);
    ListNode<int> * L2 = new ListNode<int>(8);
    L1->next = L2;
    L->next = L1;
    print(removeKFromList(L, 7));
    return 0;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ That's a funny interpretation of "remove". Your function does not edit the list, as I would expect, but rather it constructs a new list with the k nodes filtered out. \$\endgroup\$ – 200_success Nov 19 '18 at 3:39
  • \$\begingroup\$ You're right. It's probably better to solve it as the problem says exactly. \$\endgroup\$ – Bo Work Nov 19 '18 at 22:10
3
\$\begingroup\$

Thank you for your interest in improving your code! Please, don't be confused about amount of comments. Programming is all about mastering your skills!

What's wrong with the code?

You leak memory!

For each call of new there must be a call for delete. Otherwise objects are not removed. Think of these operators as a C++ wrappers around malloc and free calls.

What could be improved?

Use T type in your methods

You used int k as a function argument, but an actual type you want is T. So it goes:

ListNode<T> * removeKFromList(ListNode<T> * l, T k)

Same for print method.

Use auto

When you change your signature to ListNode<T> notice, that using auto for statements, like

ListNode<int> *L2 = new ListNode<int>(node->value);

would not require any additional changes in the return types:

auto *L2 = new ListNode<T>(node->value);

It is common to use lowercase letters for variable names, even though you create all the list objects in uppercase.

Moreover, it looks nicer. But, do not overload your code with auto. Use it only when it is obvious, what the type of your variable is. So iterators, lambdas and new operators are the common case.

Variable & method names

Naming method removeKFromList suggests "remove key from the list", so we expect ListNode to contain pairs of key-value. It is confusing to see only T value in the struct, treated as a key in your methods. So it is better to rename method removeAllFromList. All here would stand for all occurrences. Do not use terms "key" and "value" together, unless you mean dictionary. Now:

ListNode<T> * removeAllFromList(ListNode<T> * l, T value)

It is considered a good practice to name variables in the way it makes sense what they stand for. Anyone should understand their meaning without reading more then couple of lines of code ahead. Ideally, write your code like a book. It wouldn't require much efforts. Try not to use variable names shorter then 3 symbols (except some particular cases, like in for-loop iteration):

ListNode<T> * removeAllFromList(ListNode<T> * list, T value)

Now we see another issue. If you pass ListNode<T> * it is actually a node, that is being passed by, but not the list. Fix:

ListNode<T> * removeAllFromList(ListNode<T> * node, T value)

const &

If integer instantiation is used, it is only a 4 bytes that are copied, so performance changes are unnoticeable. But since we use more complex classes, that would be an issue. Use const & to fix this:

ListNode<T> *removeAllFromList(const ListNode<T> *node, const T &value)

Also make sure that nodes are not modified by writing const ListNode<T> *node

Style

Usually, it is hard to manually track all your spaces and tabulation. Use code refactoring tools. You sometimes mix styles by writing ) { and ){ with or without a space. We love perfection:)

Nesting levels

When you write:

if(l == nullptr){
    return nullptr;
}else{
   // ...
}

It is better to omit else body. That makes code more readable:

if (l == nullptr) {
    return nullptr;
}
   // ...

Reducing the amount of nested levels is good. And yes, use spaces.

File separation

ListNode methods are better placed in Node.cpp file, because they are relevant to ListNode.

Explicit

You may want to use explicit keyword to avoid unintentional type conversions.

What else could be improved?

Create LinkedList class

It is good to encapsulate your ListNode implementation. Hide your nodes, so no one could modify the values from outside, causing memory leaks or any kind of unintended behavior. It would also allow you to control memory by calling delete on each ListNode element in destructor.

There are more issues I may cover. But, please, start with those, provided above. The method removeAllFromList could now look like this:

template<typename T>
shared_ptr<ListNode<T>> removeAllFromList(shared_ptr<ListNode<T>> node, const T &value) {
    if (node == nullptr) {
        return nullptr;
    }

    // The beginning node
    shared_ptr<ListNode<T>> root = nullptr;

    // Node used for iteration
    shared_ptr<ListNode<T>> current = nullptr;

    while (node != nullptr) {
        if (node->value == value) {
            node = node->next;
            continue;
        }
        if (root == nullptr) {
            root = std::make_shared<ListNode<T>>(node->value);
            current = root;
        } else {
            current->next = std::make_shared<ListNode<T>>(node->value);
            current = current->next;
        }

        node = node->next;
    }

    return root;
}

In my answer, I assume that you need to create a copy of the linked list and delete all the nodes with the value provided.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's written in the statement that he have to deal with a linked list of integer to remove an integer. I think they aren't yet at using templates at his school (and I guess the struct ListNode<T> came form his professor). Let him learn one thing at a time, solid foundations first. Even if you're right, try to take that in consideration. \$\endgroup\$ – Calak Nov 19 '18 at 20:34
  • 1
    \$\begingroup\$ Right. Thank you for the comment. I suggest if it is difficult to understand templates, consider removing them completely. Learn by steps. \$\endgroup\$ – kupihleba Nov 19 '18 at 21:49
  • \$\begingroup\$ Thank you for your answer! This was a CodeSignal problem I did in my free time and I should have put templates in my code because I have learned them before (like about two weeks in school). I've rarely applied templates to personal projects/code before, so I forgot about using them in this instance. \$\endgroup\$ – Bo Work Nov 19 '18 at 22:08
  • \$\begingroup\$ Good luck with your work! And see you soon XD \$\endgroup\$ – kupihleba Nov 19 '18 at 22:09
1
\$\begingroup\$

Review

  1. Using meaningful names

    Yes, it's your teacher who named the variables, I guess. But I think, if you choose better names (say "list" and "value"), and explain him why you think a name that make sense is better, you're in the right way.

  2. Adopt const-correctness

    When value don't change, you should mark it as const. Here, you have a full chapter of the C++ FAQ about what, how and where you have to care about this.

  3. Don't be redundant in your conditions

    As explained in the Core Guideline, comparing a pointer to nullptr in a condition, not only is useless, but it's also much more verbose. A pointer can (and should) be used directly in a condition. So, instead of if(l == nullptr) write if(!l).

  4. Return early and clearly

    Moving special (and short) case at the to to trying to return early can make your code more readable. You're almost there. You already return early for empty list. However, you can go further, shifting to the top, the case when the actual list begin with a value to remove.

    Once you placed all special return case at the top, you don't have to wrap the rest of your code in nested braces since previous cases already returned.

  5. Code with style

    You can always use the coding style which you are comfortable, just as you can enjoy cooking with boxing gloves. You'll get only benefits using one of large adopted styles. You can also find a lot of resources about coding style on SO, about why, how and when.

  6. Improve resource management

    Even if the memory will be cleaned up by the program termination, it's a good habit to delete resource that you allocated once you don't need it anymore. Because, yes, the OS normally will clean not released memory, but then, it don't call destructor.

    I'll add, without talking about memory that you allocated yourself, what become node that you skipped but don't delete memory ? In fact, in your code, all the given list leak since you return a copy instead of modifying the list. The caller have to manage himself memory that he allocated, it's not impossible, but state it clearly.

    Also, when you can give a try to smart pointer and if don't know how they work, there's a nice article about them.

  7. Future improvements

    I guess you're student and don't learn already about classes and templates, in a near future you'll have to rewrite this code wrapping it in a class, using template parameter for the data type, ... In fact, the only purpose of this kind of code is learning, you already have a good simply linked list in the C++ standard called std::forward_list.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your response. I was reading the std::forward page and I got confused as there seems to be no memory deletion for some std::forward linked lists. I found that including && before an argument name means that argument is going to be deleted, so I guess that's the automatic memory deletion you're talking about in C++11. However, there are still &, or lvalues, being called, and they don't get deleted from memory. Why isn't there a delete statement for lvalue? \$\endgroup\$ – Bo Work Nov 19 '18 at 22:20
  • \$\begingroup\$ @BoWork oops, wrong link (about fwd list), now corrected. \$\endgroup\$ – Calak Nov 19 '18 at 23:08

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.