3
\$\begingroup\$

In my previous post I had a number of steps given to me from the accepted answer on how I can write more production ready code. In this post I want this code to be reviewed as near production code I'd write in an interview. I'd like to know how well optimized my code is now from this improvements I've made to it. If there are other optimizations or c++11 features I could be using here please share that as well.

I also included comments on worst case run time complexity for my member functions, I'd like some feedback on this and my space complexity too.

#include <iostream>
#include <string>

class LinkedList
{
    private:
        struct Node
        {
            int data;
            Node* next;
            Node(int data_) : data(data_), next(nullptr) { }
        };
        Node* _head;
        Node* _tail;
    public:
        LinkedList() : _head(nullptr) { }
        LinkedList(int data) { // O(1)
            Node* n = new Node(data);
            _head = n;
            _tail = n;
        }
        ~LinkedList() { // O(n)
            Node* current = _head;
            Node* n;
            while(current) {
                n = current;
                current = current->next;
                delete n;
            }
            _head = nullptr;
        }
        void append(int new_data) { // O(1)
            auto n = new Node(new_data);
            if(!_head) {
               _head = n;
               _tail = n;
            }
            else {
                _tail->next = new Node(new_data);
                _tail = _tail->next;
            }
        }
        void remove(int target_data) { // O(n)
            if(!_head) { return; }
            Node* previous = nullptr;
            auto current = _head;
            for(; current->data != target_data; current = current->next) {
                if(!current->next) {
                    return;
                }
                previous = current;
            }
            if(!current->next) {
                if(previous) {
                    delete current;
                    previous->next = nullptr;
                }
                else {
                     delete current;
                    _head = nullptr;
                }
            }
            else {
                auto dangling_ptr = current->next;
                current->data = current->next->data;
                current->next = current->next->next;
                delete dangling_ptr;
            }
        }
        friend std::ostream& operator<<(std::ostream& os, const LinkedList& linked_list) { // O(n)
            Node* current = linked_list._head;
            if(!current) {
                os << "Linked List is empty" << std::endl;
                return os;
            }
            else {
                for(; current; current = current->next) {
                    os << '(' << std::to_string(current->data) << ")->";
                }
                os << "nullptr";
                return os;
            }
        }
};

int main()
{
    LinkedList linked_List(0);
    linked_List.append(1);
    linked_List.append(2);
    linked_List.append(3);
    linked_List.append(4);

    std::cout << linked_List << std::endl;

    linked_List.remove(0);
    linked_List.remove(4);
    linked_List.remove(2);
    std::cout << linked_List << std::endl;

    linked_List.remove(3);
    linked_List.remove(1);
    std::cout << linked_List << std::endl;

    LinkedList linked_List_two;
    linked_List_two.append(1);
    linked_List_two.append(2);
    linked_List_two.append(3);
    linked_List_two.append(4);

    std::cout << linked_List_two << std::endl;

    linked_List_two.remove(0);
    linked_List_two.remove(4);
    linked_List_two.remove(2);
    std::cout << linked_List_two << std::endl;

    linked_List_two.remove(3);
    linked_List_two.remove(1);
    std::cout << linked_List_two << std::endl;
}
\$\endgroup\$
4
\$\begingroup\$

I see a number of things that could help you improve your code.

Don't define a default constructor that only initializes data

Instead of writing this:

class LinkedList
{
    Node* _head;
    Node* _tail;
 public:
    LinkedList() : _head(nullptr) { }
    // etc.
};

write this:

class LinkedList
{
    Node* _head = nullptr;
    Node* _tail = nullptr;
 public:
    // no need to explicitly write default constructor
    LinkedList() = default;
};

See Cpp Core Guidelines C.45 for details. Note also that this initializes both member data items.

Think about whether the destructor should be virtual

For an interview, you should be prepared to answer why the class destructor is not virtual and to explain circumstances in which it should be virtual.

Eliminate redundant variables

The current code contains this constructor:

LinkedList(int data) { // O(1)
    Node* n = new Node(data);
    _head = n;
    _tail = n;
}

I'd prefer to see n eliminated and to see it written instead like this:

LinkedList(int data) :
    _head{new Node{data}}, _tail{_head} {}

Use for rather than while where appropriate

The desructor currently looks like this:

~LinkedList() { // O(n)
    Node* current = _head;
    Node* n;
    while(current) {
        n = current;
        current = current->next;
        delete n;
    }
    _head = nullptr;
}

Rather than introducing two extra variables, I'd write it using a for loop like this:

~LinkedList() { // O(n)
    if (_head == nullptr) {
        return;
    }
    for (auto current{_head->next}; current; current = current->next) {
        delete _head;
        _head = current;
    }
}

Fix the memory leak

The current code has this member function:

void append(int new_data) { // O(1)
    auto n = new Node(new_data);
    if(!_head) {
       _head = n;
       _tail = n;
    }
    else {
        _tail->next = new Node(new_data);
        _tail = _tail->next;
    }
}

The problem is that we create two nodes but only use one unless the list is empty. I'd fix that like this:

void append(int new_data) { // O(1)
    auto n{new Node(new_data)};
    if(_head == nullptr) {
       _head = _tail = n;
    } else {
        _tail->next = n;
        _tail = _tail->next;
    }
}

Simplify your code

The remove function is much more longer than it needs to be. Right now it looks like this:

    void remove(int target_data) { // O(n)
        if(!_head) { return; }
        Node* previous = nullptr;
        auto current = _head;
        for(; current->data != target_data; current = current->next) {
            if(!current->next) {
                return;
            }
            previous = current;
        }
        if(!current->next) {
            if(previous) {
                delete current;
                previous->next = nullptr;
            }
            else {
                 delete current;
                _head = nullptr;
            }
        }
        else {
            auto dangling_ptr = current->next;
            current->data = current->next->data;
            current->next = current->next->next;
            delete dangling_ptr;
        }
    }

It could be made somewhat simpler by creating a temporary Node that points to _head:

void remove(int target_data) { // O(n)
    Node headptr{0};
    headptr.next = _head;
    for (Node* curr{&headptr}; curr && curr->next; curr = curr->next) {
        if (curr->next->data == target_data) {
            auto victim = curr->next;
            if (victim == _tail) {
                _tail = curr;
            }
            if (victim == _head) {
                _head = victim->next;
            }
            curr->next = victim->next;
            delete victim;
            return;
        }
    }
}

Rethink the interface

It's not unreasonable to expect that one might want to actually do something with the things inserted into a list. Right now, there's no way to do anything except print which suggests an incomplete interface.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Make test success obvious

The current test code exersizes the list, but it doesn't indicate what is expected to be printed. I'd instead write both test scenarios and also the expected result so that it would be clear to anyone running the code whether everything was working as expected or not.

Consider using a template

A linked list is a fairly generic structure that could hold any kind of data if the class were templated, and not just an int.

Consider possible uses

For any code production, but especially if you're in an interview, think about how the class is being used and whether there are any restrictions or limits inherent in the design. For example, think about copy and move operations. If you write this, does the code do the right thing?

LinkedList a;
a.append(1);
a.append(2);
a.append(3);
a.append(4);
auto b{a};
std::cout << "a: " << a << '\n';
std::cout << "b: " << b << '\n';
a.remove(1);
std::cout << "a: " << a << '\n';
std::cout << "b: " << b << '\n';

Also consider multithreaded code. Would it be thread-safe to insert nodes from one thread and remove them from another? If not, what would be needed to make that work?

\$\endgroup\$
  • \$\begingroup\$ Hey thee Edward, this is great feedback and I'll work on implementing it into the code. I noticed the sections Prefer iteration over recursion and Simplify your code for push_back may be referencing code that is not in this post. Sorry for the confusion there. \$\endgroup\$ – greg Mar 11 at 17:05
  • \$\begingroup\$ Thanks, you're right; I had copied some things from another question and forgot to delete those sections. Your code wasn't the problem -- the confusion was all my own creation! Sorry about that; I have fixed my answer now. \$\endgroup\$ – Edward Mar 11 at 18:39
  • \$\begingroup\$ \n will also flush the stream unless the stream can be determined to not go to an interactive device or sync_with_stdio(false) had been called. stackoverflow.com/a/25569849/2498188 \$\endgroup\$ – Emily L. Mar 11 at 18:51
  • \$\begingroup\$ You would only prefer to see n eliminated, and Things rewritten to use the ctor-init-list? It's not a matter of preference but correctness though. \$\endgroup\$ – Deduplicator Mar 12 at 16:36
  • \$\begingroup\$ @Deduplicator: I don't understand your comment. \$\endgroup\$ – Edward Mar 12 at 16:45
3
\$\begingroup\$
  • append leaks memory: the else branch forgets n and creates another Node.

  • append should be streamlined. The new node becomes tail no matter what:

        Node * n = new Node(new_data);
    
        if (!head) {
            head = n;
        } else {
            tail->next = n;
        }
    
        tail = n;
    
  • remove never updates tail, and only updates head when the list becomes empty. Removal of them makes the list corrupted.

\$\endgroup\$
  • \$\begingroup\$ Great catch I see this now. I'll include this feedback when I refactor these methods. \$\endgroup\$ – greg Mar 11 at 17:09
2
\$\begingroup\$

Overall, your implementation has improved so good job! Here's a few general comments.

  • In operator<<, you can make current of type const Node* (but not of type const Node* const). In other words, you have a pointer to a const Node, but not a const pointer to const Node.

  • In append, if the else-branch is executed, you will have created n for no reason. So move its declaration inside of the if-branch where it is needed.

  • In your destructor, move the declaration of n inside the while-loop and make it const. So its first line should be const Node* const n = current.

  • For the constructor of Node, I find it confusing the argument name has a trailing underscore; this does not happen for the other function arguments anywhere. Perhaps you meant the private member to be data_ (or _data) and the argument just data.

  • Why is the default constructor also not making _tail null? To avoid these type of problems, as per C.48, I would omit the default constructor and just use in-class initialization to set both to {nullptr}.

  • Unless there is a reason not to, it is good practice (as per C.46) to make single-argument constructors explicit to avoid unintentional conversions.

  • For a future version, you might want to look at smart pointers to avoid leaking memory.

\$\endgroup\$
  • \$\begingroup\$ If I move n inside my while loop, will this have any negative impacts on space complicity since I will be declaring and assigning with each iteration? I could be wrong, but I thought in my current implementation it would only allow for a declaration once and then an assignment to n for each iteration. I agree with all the points here, I've seen a lot of common feedback with smart pointers and should look into implementing them \$\endgroup\$ – greg Mar 11 at 17:08
  • \$\begingroup\$ @greg But you assign on every iteration anyway. If you really care about the details, there is no substitute at looking at the generated machine code is. \$\endgroup\$ – Juho Mar 11 at 17:16

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.