Deleting duplicate elements from a single-linked list in C++11

Question

The code below is a simple coding exercise I got from a book that asks to remove the duplicates from a single-linked list (using a simple struct; this is part 2, see part 1 here).

Question 1: Is there a better way to delete a Node than by creating a temporary variable temp and deleting that. I actually tried deleting p directly and it worked. I find this surprising because after I delete p I would expect p->next to be a segmentation fault. Is this a compiler-specific trickery or is it a safe practice?

Question 2: I'm a little confused about passing pointers by reference. If I don't pass head by reference in insert, it doesn't work; but passing them by copy to remove_duplicates works (that is, the second call to print_node doesn't print the original list). Why?

#include <iostream>
#include <unordered_map>

struct Node {
  int data;
  Node* next;
};

void insert(Node*& head, const int data) {
  head = new Node {data, head};
}

void print_node(Node* head) {
  if (!head) return;

  std::cout << head->data;
  for(auto p = head->next; p; p = p->next) {
    std::cout << "->" << p->data;
  }
  std::cout << std::endl;
}

void remove_duplicates(Node * head) {
  if (!head || !head->next) return;

  std::unordered_map<int, bool> map {{head->data, true}};
  for (auto p = head->next, prev = head; p; p = p->next) {
    if (map[p->data]) {
      prev->next = p->next;
      Node* temp {p};
      delete temp;
    } else {
      map[p->data] = true;
      prev = p;
    }
  }
}

int main(int argc, char* argv[]) {
  Node* my_list {};
  insert(my_list, 2);
  insert(my_list, 1);
  insert(my_list, 3);
  insert(my_list, 2);
  insert(my_list, 2);
  insert(my_list, 1);
  insert(my_list, 4);
  print_node(my_list);
  // 4->1->2->2->3->1->2
  remove_duplicates(my_list);
  print_node(my_list);
  // 4->1->2->3
}

Answer 1

Currently your code is broken (it just happens to work accidentally).

  for (auto p = head->next, prev = head; p; p = p->next) {
    if (<Test>) {
      <Stuff>
      Node* temp {p};    // So p and temp both point at the same block of memory
      delete temp;       // You delete the memory pointed at by temp.
                         // This is the same effect as deleting p.
                         // This memory now belongs to the system and not
                         // your code. Access anything within this memory
                         // block is "undefined behavior".

                         // When you loop back to the `for` and
                         // execute `p = p->next` you are now
                         // invoking undefined behavior.

The term "undefined behavior" basically means the standard does not define what can happen and any hardware/compiler can do anything it likes as it result it can blow up or could look like it is working perfectly.

The reason the standard does not specify is to allow each implementation to pick the most efficient thing possible for them (you can specify the most efficient thing).

The block you have given back may be on a page that has been returned to the OS. The memory management could re-use parts of that block for its own internal buffers (to make allocation/deallocation efficient). The content of this block could have any value in it or it could be completely removed from the memory available to your processes. The least worst that could happen is probably a segfault and your application crashes. The real worst is that your application gets a random pointer and seems to work normally (but in reality it is trashes memory all through your application making it really hard to debug). Even much worse is that it happens to actually work in your tests then breaks when you push to production.

Fixed code

  std::unordered_map<int, bool> map {{head->data, true}};

  for (auto p = head->next, prev = head; p;) {
      if (map[p->data]) {
          prev->next = p->next;
          Node* temp {p};
          p = p->next;         // Move p before you delete its memory
          delete temp;         // Now you delete temp (which points at the old value)
      }
      else
      {
          map[p->data] = true;
          prev = p;
          p = p->next          // Don't forget you need to move p in both branches.
      }
  }

Bracing style.

This is horrible (IMO)

} else {

It is also not a common bracing style used in C++ os better avoided. The two main common styles are

if (<test>) {
}
else {
}

// or

if (<test>)
{
}
else
{
}

Questions

Is there a better way to delete a Node than by creating a temporary variable temp and deleting that.

No. Because you need to use the next member before deleting. So you have moved your pointer. So you need the temp value to record where you where so that you can delete it.

I actually tried deleting p directly and it worked. I find this surprising because after I delete p I would expect p->next to be a segmentation fault.

It could be a segfault or it could work as expected. The memory does not belong to you so you can't know what is there anymore. But the standard does not require the code to do anything special with the memory so it could just contain the values it used to have before you called delete.

Is this a compiler-specific trickery or is it a safe practice?

Its definitely not safe to even read this memory. It is just happens to work. But if you change anything it may stop working. Compiler flags/ Compiler/ OS Version/ OS/ Hardware. Any or none of these things could trigger a change in behavior.

I'm a little confused about passing pointers by reference. If I don't pass head by reference in insert, it doesn't work; but passing them by copy to remove_duplicates works (that is, the second call to print_node doesn't print the original list).

The remove_duplicates() only works as long as you don't try and remove the value of the head node. But because the head is never a duplicate it will work.

A reference is a variable alias. ie. It is another name for a variable that already exists. So by changing the value of the reference you actually change the originals value.

int  head  = 6;
int& otherHead = head;   // otherHead is an alias for head.
                         // If I change the value of otherHead then
                         // I change the value of head.


otherHead = 12;          // head is now 12.

So in the insert() function you are passing head by reference (it becomes another name for the variable you passed as the parameter).

void insert(int& otherValue)
{
    otherValue = 15;  // otherValue is an alternative name for the parameter
                      // that was passed to this function.
}
int main()
{
    int value = 5;
    insert(value);
    std::cout << value;  // prints 15
}

So in your function:

void insert(Node*& head, const int data) {
  head = new Node {data, head};
  ^^^^  // This is an alias for another variable.
        // So we are changing the value of that other variable.
}

If we don't use a reference:

void broken_insert(Node* head, const int data) {
  head = new Node {data, head};
  ^^^^  // This is a local variable (a copy of the original)
        // We change head here. But it does not change the original variable.
}
int main()
{
    Node* data = nullptr;
    broken_insert(data, 12);
    std::cout << data << "\n"; // Still prints nullptr
}                              // as broken_insert only changed the local
                               // variable head it has nothing to do with
                               // the variable data.