Linked List Interview Code methods, runtime, and edge cases

Question

Refactored code here

I want to write a very simple Linked List with only 3 methods Append, Remove and Print. This is not for production and is to be treated as code that could be used in an interview or a quick and dirty prototype. I'm really curious about the approach I've taken here to ensure no duplicates appear in my Linked List. I feel the data structure will be much easier to work with if remove any complexity around duplicate data and want to use this Linked List to implement a Stack, or Queue, or Binary Search Tree etc. I had int data before as the member data field for my Linked List and don't want to make this overly complex by introducing a concept of ids.

First I'd like to know if my member functions for the Linked List have any edge cases I am not catching and any improvements I can make to run time efficiency . Anyway I can simplify this code further with c++11 features, shorter variable names or any other suggestions would be appreciated too.

#include <iostream>
using namespace std;
struct Node
{
 int id;
 Node* next;
 Node(int id) : id(id), next(nullptr) { }
 void append(int newId) {
 Node* current = this;
 while (current->next != nullptr) {
 if (current->id == newId) {
 return;
 }
 else {
 current = current->next;
 }
 }
 current->next = new Node(newId);
 }
 void remove(int targetId) {
 Node* current = this;
 Node* previous;
 while (current->id != targetId) {
 if (current->next != nullptr) {
 previous = current;
 current = current->next;
 }
 else {
 cout << "node not found :(\n";
 return;
 }
 }
 if (current->next == nullptr) {
 delete current;
 previous->next = nullptr;
 }
 else {
 Node* danglingPtr = current->next;
 current->id = current->next->id;
 current->next = current->next->next;
 delete danglingPtr;
 }
 }
 void print() {
 if (this->next == nullptr) {
 cout << this->id << endl;
 }
 else {
 cout << this->id << " ";
 this->next->print();
 }
 }
};
int main()
{
 Node list(1);
 list.append(2);
 list.append(3);
 list.append(4);
 list.print();
 list.remove(3);
 list.print();
 list.remove(4);
 list.print();
 list.remove(1337);
}

• Loki Astari: How do you represent the empty list? Node and a List are different things. A Node is a member of a List (maybe a very simple member) but a List does not need to have any Nodes. There are several linked list implementations that we have reviewed here. Have a look at an existing one.

Answer 1

1. The namespace std is not designed for wholesale importation, see "Why is "using namespace std" considered bad practice? " for more detail.

   You could instead do a using std::cout; or better qualify the three use-sites.

2. You don't in any way encapsulate the list and abstract over the list. It's just a bunch of Nodes. Consider putting it all into a List owning and managing the whole lot.

3. Trying to remove() the root-Node uncovers a bug. Try to trace it through.

4. pointer != nullptr is just a long-winded way to write pointer in a boolean context. Respectively for pointer == nullptr and !pointer. Yes, Java needs that, but this is C++.

5. When you return from the if-branch, putting the alternative in an else-branch is superfluous.

6. A function for printing an object should allow the caller to specify the stream, and be called operator<<.

7. There is no reason to rely on the compiler transforming recursion to iteration, especially as it might not always be able.

8. this should rarely be used explicitly.

• greg: Thanks for the feedback Deduplicator. I'll refactor my code with these points, very helpful. In an interview scenario would you consider not encapsulating the Node, polluting the global namespace with using namespace std a bad reflection on the candidate? I want to write a solution as fast a possible, maybe in an interview I just mention that I should encapsulate my Node struct and not use std globally in a production code scenario?.
• Deduplicator: Just take a look how much the rest would change if you don't use using namespace std;. Huh, it's only used for std::cout, and that three times? And Considering that the Node, as an internal implementation-detail of List, would at most need a single ctor for ease-of-use, it wouldn't lead to that much more code. Actually, when re-writing the rest you can actually shorten things, and get rid of the recursion too!
• greg: Should I replace my recursion with a while loop instead? In what cases will the compiler not be able to transform recursion to iteration?
• Deduplicator: Well, if there are locals with non-trivial dtors, it might be non-trivial to prove, or need additional info. In this case, an optimising compiler should be able to. But writing it as iteration is more concise, clean, and always right.
• Deduplicator: The root cause is that when you are trying to remove the first node, you don't have access to whatever owns that node. Fix point 2, and you can fix that.