Linked List Interview Code methods, runtime, and edge cases refactored

Question

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;
}

Answer 1

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?

Answer 2

• 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.

Answer 3

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.