1
\$\begingroup\$

My go at creating a function to remove a specific node from a linked list:

void deleteSpecific(DataType N, Node *&H, Node *&T)
{
  if (H == nullptr) // 1. Check Whether List Is Empty (head == NULL)
  { // If It's Empty Then, Display The Following And Terminate The Function.
    std::cout << std::endl << std::endl;
    std::cout << "\t" << "-> LL| ERR: The List Is Empty. Deletion Not Possible.";
    std::cout << std::endl << std::endl;
    return;
  }
  Node *TMP1 = H, *TMP2; // If It's Not Empty Then, Define Two Node Pointers Temp1 And Temp2 And Put Head In Temp1 Only.
  while (TMP1->data != N) // Keep Moving Temp1 Until it reaches to exact node to delete
  {
    if (TMP1->next == nullptr) // If Node is not found in list then display the message and exit the loop and function.
    {
      std::cout << std::endl << std::endl;
      std::cout << "\t" << "-> LL| ERR: Given Node Not Found. Deletion Not Possible.";
      std::cout << std::endl << std::endl;
      return;
    }
    TMP2 = TMP1;
    TMP1 = TMP1->next;
  }
  if (H->next == nullptr)
  {
    H = nullptr;
    delete TMP1;
  }
  else if (TMP1 == H)
  {
    H = H->next;
    delete TMP1;
  }
  else if (TMP1->next == nullptr)
  {
    TMP2->next = nullptr;
    T = TMP2;
    delete TMP1;
  }
  else
  {
    TMP2->next = TMP1->next;
    delete TMP1;
  }
}  

Is The logic of the code correct? I've tried it with multiple inputs and it works, however are there any special cases that you can notice that'll not work with this?

\$\endgroup\$
  • \$\begingroup\$ Can you post the full code? \$\endgroup\$ – yuri Mar 2 '18 at 9:56
3
\$\begingroup\$

Code Review

Removing the Element:

Your four choices do seem to cover all the situations.

  if (H->next == nullptr)
  {
    H = nullptr;
    delete TMP1;
  }
  else if (TMP1 == H)
  {
    H = H->next;
    delete TMP1;
  }
  else if (TMP1->next == nullptr)
  {
    TMP2->next = nullptr;
    T = TMP2;
    delete TMP1;
  }
  else
  {
    TMP2->next = TMP1->next;
    delete TMP1;
  }

But in reality there are only two situations. You are deleting the head node. You are deleting another node. The other two are special cases of deleting the tail and we should handle that separately.

  Node* TMP1 = H;
  Node* TMP2 = nullptr;   // set a value for TMP2 so we can check it/

  // Find node to delete

  // Check if the item being removed is the tail
  // and update the tail appropriately.
  if (T == TMP1) {
      T = (T == H) ? nullptr : TMP2;
  }

  // Now update the list.
  if (TMP2 == nullptr) {       // If TMP2 is null this is the head
      H = TMP1->next;          // Node we are deleting. So reset H
  }
  else {
      TMP2->next = TMP1->next; // Otherwise TMP1 is being deleted and
                               // TMP2 is the previous node.
  }

  // Now the node is unlinked delete it.
  delete TMP1;  

You can simplify this even more by using an extra helper function.

Objects

Why is this a free standing function?

void deleteSpecific(DataType N, Node *&H, Node *&T)

I would expect this to be part of a class. Where head and tail are part of the object. So you don't need to pass them around.

Separation of Concerns

Your code should either be resource management or business logic. Your code mixes the two different types of code together. Here the resource management is removing the node from the list. But you also have some business logic inside your code that is talking to the user.

std::cout << std::endl << std::endl;
std::cout << "\t" << "-> LL| ERR: The List Is Empty. Deletion Not Possible.";
std::cout << std::endl << std::endl;

Is it really an error in the first place? But why is it part of the resource management code?

The resource management code should be wrapped in another layer of code that does the business logic and informs the user. That way you can re-use the deleteSpecific() function from another piece of code that does not care if the data is in the list or not.

Style Comments

Naming

Variable names are supposed to be self documenting.

 H:   head
 T:   tail

That's no so self documenting as you think. Just spell it out. There are a couple of other conventions you need to keep in mind.

  1. Identifiers that are all caps are usually reserved for macros.
  2. Identifiers with an initial cap are usually user defined "Types"
  3. Identifiers with an initial lower case letter are usually objects.

These are good conventions to follow and will help you spot things as your code gets more complicated.

Pointer & Reference

In "C" the "*" was usually placed by the object. But "C++" is much more strongly types and the "*" and "&" are considered part of the type information so you usually place these with the type.

void deleteSpecific(DataType N, Node *&H, Node *&T)

Is more usually written as:

void deleteSpecific(DataType N, Node*& H, Node*& T)

But you say "AHhhh, but what about"

Node *TMP1 = H, *TMP2;

Yes it does not work in this situation. But there is a more important rule recommendation that makes this situation obsolete. The rule is to declare one variable per line. So this should actually be written as:

Node*  TMP1 = H;
Node*  TMP2 = nullptr;

Please stop writing C++ like it was C. These are completely different languages with their own styles and idioms.

Prefer "\n" over std::endl

The difference between the two is that endl flushes the buffer. Usually this is not what you want and makes the code exceedingly inefficient (user flushing is almost always wrong). If you think you need it then add an explicit flush.

\$\endgroup\$

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.