0
\$\begingroup\$

I asked a similar question (C++ linked list) but I'd like to have this similar code reviewed. It's not the same code, just slightly different and with bugs fixed.

The code takes the head pointer of a singly linked list and an int element to find and remove from the list:

void removeFromList(node* &head, int toBeRemoved){
    if (head != nullptr){
        node* temp = head;
        if (head->data == toBeRemoved){
            head = head->next;
            delete temp;
        }
        else{
            while (temp->next != nullptr && temp->next->data !=toBeRemoved)
                temp = temp->next;

            if (temp->next == nullptr)
                //some code to be executed when element not found
                else{
                if (temp->next->data == toBeRemoved){
                    node* removeThis = temp->next;
                    temp->next = temp->next->next;
                    delete removeThis;
                }
            }
        }
    }
    else
        //some code to be executed when list is empty
}

I've tested it by outputting messages to the console in case the element is not found or the list is empty, and it seems to be working in every case.

Still, I'd like to know if the code can be improved (not trying to use the C++ list implementation, just to rewrite this in the best way).

\$\endgroup\$
  • 1
    \$\begingroup\$ In general you are better of asking one question, and wait for the answers to that question before asking another question on the same theme. This would save the reviewers a whole lot of time, as we don't need to comment upon the same issues twice. In this case you're repeating the same flaws of indentation, strange and inconsistent brace usage, and at the same time fixed a few of the issues in the other posts related to not doing the && when one side is testing for nil. But having two questions alive at the same times, is discouraging for reviewers. \$\endgroup\$ – holroy Apr 14 '17 at 12:22
  • \$\begingroup\$ May be the element value isn't the best choice to identify the element to be rmoved. What if the value occurs multiple times? Is that really what you intend? \$\endgroup\$ – πάντα ῥεῖ Apr 14 '17 at 12:40
4
\$\begingroup\$

Design

You are obviously not using classes (as this is a free function). This means you are exposing the implementation details of the linked list to the user. This is bad as you can not guarantee any of the invariants of the list.

Invariants:

  1. All the nodes were allocated with new.
  2. Does your list use sentinels? (not at the moment see below).
  3. (Sure I could come up with more).

Personally I would wrap this up in a class where the user never sees a node object.

Code Re-Use

You have repeated chunks of code that do the same things.

void removeFromList(node* &head, int toBeRemoved){
    // STUFF
        if (head->data == toBeRemoved){
            head = head->next;
            delete temp;
        }
    // STUFF
                    temp->next = temp->next->next;
                    delete removeThis;
                }

You should isolate code that does the same thing in to its own function/method. Then use a decent function name so the code becomes self documenting.

Sentinel

When writting list it is sometimes useful to have a sentinel node. This is a special node in the list that does not carry any data. But it makes manipulating the list easy as you no longer need to worry about a null value (or empty list). Thus the head no longer becomes a special case.

Example: A sentinel list will always contain one item at the head (this head item contains no data). The rest of the API should be coded with the understanding of the sentinel value. So en empty list contains only the sentinel value.

With this assumption we can simplify the code too:

void removeFromList(node* head, int toBeRemoved){
    node* temp = head;
    while (temp->next != nullptr && temp->next->data !=toBeRemoved) {
        temp = temp->next;
    }
    if (temp->next == nullptr && temp->next->data == toBeRemoved){
        node* removeThis = temp->next;
        temp->next = temp->next->next;
        delete removeThis;
    }
}

Use Braces

You don't consistently use braces. This is going to come back and haunt you one day. Any nested statement should have braces (even if it is a single item). Doing this one thing will save you from so many bugs.

            if (temp->next == nullptr)
                //some code to be executed when element not found
                else{
                }

Just add the braces after the if(). Also align your code better.

            if (temp->next == nullptr) {
                //some code to be executed when element not found
            }
            else {
                // Other stuff.
            }

Types and names

In C++ the most important part of the program is the type information. There is nothing more important than types. Get your types correct and you are 85% there in a C++ program.

As a result it is useful to be able to distinguish types from objects in the code. So a common convention is to use a naming scheme. A very common naming scheme is that user defined types have an initial uppercase letter while objects (variables/methods/functions) have an initial lower case letter.

// So
Node*  item;
// rather than
node*  item;

While we are taking about types. The '*' and the '&' are part of the type information so they go with the type not the object. This is the inverse of how C programmers do it.

// So
Node*&  head
// Rather than
node*   &head

Note: Notice how the SO code block picks up the type. This is a reflection of common conventions used in C++.

Re-Design

class LinkedList
{
    struct Node
    {
        Node* next;
        virtual ~Node(){}
    };
    struct DataNode: public Node
    {
        DataNode(Node* next, int val)
            : Node(next)
            , data(val)
        {}
        int    data;
    }

    Node  sentinel;    // Notice I don't dynamically allocate this.

    public:
        ~LinkedList()
        {
            Node* next;
            for(Node* loop = sentinel.next; loop; loop = next) {
                next = loop->next;
                delete loop;
            }
        }
        LinkedList()
            : sentinel{}  // forces zero-initialization
        {}
        // Delete compiler generated methods.
        LinkedList(LinkedList const&)            = delete;
        LinkedList& operator=(LinkedList const&) = delete;

        void add(int val)
        {
            sentinel.next = new DataNode{sentinel.next, val};
        }
        void del(int val)
        {
            for(Node* loop = &sentinel; loop->next; loop=loop->next) {
                if (dynamic_cast<DataNode*>(loop->next)->data == val) {
                    Node* del = loop->next;
                    loop->next = del->next;
                    delete del;
                    break;
                }
            }
        }
};

To see an example of a fully implemented doubly linked list check out this answer.

\$\endgroup\$
  • \$\begingroup\$ Using a sentinel is a weakness: It must be allocated, dynamically or not. And there's no need for it. Also giving the nodes a virtual dtor makes things more inefficient... \$\endgroup\$ – Deduplicator Apr 14 '17 at 15:07
  • \$\begingroup\$ @Deduplicator: Completely disagree (on basically every point). Using a sentinel makes all the rest of the code simpler to write. It does not need to be dynamically allocated as I have shown more than once. The cost of adding virtual is insignificant and probably not measurable (it is a theoretical inefficient that in the real world is outweighed by so many other factors (like cache misses and development cost and maintenance)). Overall using a sentinel is a superior technique because it simplifies the code; thus making it easier to read/write and maintain. \$\endgroup\$ – Martin York Apr 14 '17 at 15:47
  • \$\begingroup\$ If you don't shun the double-pointer, you get the same regularity without using a sentinel, and only have one node-type without any virtual dispatch. Those are small but not insignificant gains in storage- and time-efficiency without any drawback. Of course there are other languages not providing double-pointers... \$\endgroup\$ – Deduplicator Apr 14 '17 at 17:08
  • \$\begingroup\$ I see no not insignificant gains. In terms of storage. You have a head pointer. I have a sentinel object. Space the same. In time I have an overhead during a call to delete on a node that has a theoretical higher cost; but in reality a non measurable difference. Your code is more obtuse to read and thus represents a much higher cognitive burden resulting in more time being spent developing and maintaining the code. \$\endgroup\$ – Martin York Apr 14 '17 at 17:22
  • \$\begingroup\$ Your sentinel object is one vptr bigger, as are all your nodes. Alternatively, only your sentinel would be one 'data' bigger. Does the virtual dtor-call get inlined? The non-virtual gets inlined in all cases. And whether using sentinel or double-pointer is the bigger cognitive burden is a matter of being used to it. \$\endgroup\$ – Deduplicator Apr 14 '17 at 19:15
1
\$\begingroup\$

Your code is oddly redundant. See this simplified rewrite:

void removeFromList(node*& head, int toBeRemoved){
    if(!head) {
        //some code to be executed when list is empty
        return; /* optional */
    }
    node** cur = &head;
    while(*cur && (*cur)->data != toBeRemoved)
        cur = &(*cur)->next;
    if(*cur) {
        node* temp = *cur;
        *cur = (*cur)->next;
        delete temp;
    } else {
        //some code to be executed when element not found
    }
}

Anyway, I hope this is just interna of a list-class or such for encapsulation.

You have some confused indentation and braces, which coincidentally works out. Don't rely on coincidence.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the simpler version :) I believe indentation was a copy-paste defect, as I had to translate my variables and object names into English. \$\endgroup\$ – Floella Apr 15 '17 at 12:39

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.