5
\$\begingroup\$

I've tried to create my best at creating a custom Linked List implementation in C++. This is my code, would love to get feedback on it!

DATA_TYPE is a macro defined elsewhere.

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

void addEnd(DATA_TYPE value, Node *&head, Node *&tail)
{
  Node *newNode = new Node;
  newNode->data = value;
  newNode->next = nullptr;
  if (head == nullptr) head = tail = newNode; 
  else {
    tail->next = newNode;
    tail = newNode;
  }
}

void addBeginning(DATA_TYPE value, Node *&head, Node *&tail)
{
  Node *newNode = new Node;
  newNode->data = value;
  if (head == nullptr) {
    newNode->next = nullptr;
    head = tail = newNode;
  } else {
    newNode->next = head;
    head = newNode;
  }
}

void addSpecific(DATA_TYPE value, DATA_TYPE location, Node *&head, Node *&tail)
{
  Node *newNode = new Node;
  newNode->data = value;
  if (head == nullptr) {
    newNode->next = nullptr;
    head = tail = newNode;
  } else {
    Node *temp = head;
    while (temp->data != location) {
      if (temp->next == nullptr) {
        std::cout << std::endl << std::endl;
        std::cout << "\t" << "LL-> Node (" << location << ") Not Found In The List.";
        std::cout << std::endl << std::endl;
        return;
      }
      temp = temp->next;
    }
    newNode->next = temp->next;
    temp->next = newNode;
    if (temp->next == nullptr) tail = newNode;
  }
}

void deleteBeginning(Node *&head)
{
  if (head == nullptr) {
    std::cout << std::endl << std::endl;
    std::cout << "\t" << "LL-> The List Is Empty. Deletion Not Possible.";
    std::cout << std::endl << std::endl;
    return;
  }
  Node *temp = head;
  if (temp->next == nullptr) {
    head = nullptr;
    delete temp;
  } else {
    head = head->next;
    delete temp;
  }
}

void deleteEnd(Node *&head, Node *&tail)
{
  if (head == nullptr) {
    std::cout << std::endl << std::endl;
    std::cout << "\t" << "LL-> The List Is Empty. Deletion Not Possible.";
    std::cout << std::endl << std::endl;
    return;
  }
  Node *temp = head;
  if (temp->next == nullptr) {
    head = nullptr;
    delete temp;
  } else {
    while (temp->next != tail) temp = temp->next;
    tail = temp;
    temp = temp->next;
    tail->next = nullptr;
    delete temp;
  }
}

void deleteSpecific(DATA_TYPE node_location, Node *&head, Node *&tail)
{
  if (head == nullptr) {
    std::cout << std::endl << std::endl;
    std::cout << "\t" << "LL-> The List Is Empty. Deletion Not Possible.";
    std::cout << std::endl << std::endl;
    return;
  }
  Node *temp1 = head, *temp2;
  while (temp1->data != node_location) {
      if (temp1->next == nullptr) {
      std::cout << std::endl << std::endl;
      std::cout << "\t" << "LL-> Given Node Not Found. Deletion Not Possible.";
      std::cout << std::endl << std::endl;
      return;
    }
    temp2 = temp1;
    temp1 = temp1->next;
  }

  if (temp1->data == node_location) {
    if (head == temp1 && tail == temp1) {
      head = nullptr;
      delete temp1;
    } else if (temp1 == head) {
      head = head->next;
      delete temp1;
    } else if (temp1 == tail) {
      temp2->next = nullptr;
      tail = temp2;
      delete temp1;
    } else {
      temp2->next = temp1->next;
      delete temp1;
    }
  }
}

void display(Node *head)
{
  if (head == nullptr) {
    std::cout << std::endl << std::endl;
    std::cout << "\t" << "LL-> The List Is Empty.";
    std::cout << std::endl << std::endl;
    return;
  }
  Node *temp = head;
  std::cout << std::endl << std::endl << "\t" << "| ";
  while (temp != nullptr) {
    std::cout << temp->data << " | ";
    temp = temp->next;
  }
  std::cout << std::endl << std::endl;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ "DATA_TYPE is a macro defined elsewhere!" Why not using a template class instead? All in all that more looks like c-code, than c++. \$\endgroup\$ – πάντα ῥεῖ Feb 23 '18 at 20:09
  • \$\begingroup\$ πάντα-ῥεῖ, I've actually thought about it, does it make big difference? What are the pros of actually using a template class? \$\endgroup\$ – Saad Sawash Feb 23 '18 at 20:14
  • 4
    \$\begingroup\$ "What are the pros of actually using a template class?" That it's generic? \$\endgroup\$ – πάντα ῥεῖ Feb 23 '18 at 20:14
  • \$\begingroup\$ ok, that's enough, I'm convinced :D \$\endgroup\$ – Saad Sawash Feb 23 '18 at 20:16
7
\$\begingroup\$

One thing that I don't like is code such as the following whenever you deal with an empty container:

std::cout << std::endl << std::endl;
std::cout << "\t" << "LL-> Node (" << location << ") Not Found In The List.";
std::cout << std::endl << std::endl;

When you move your code into a class, as @πάντα ῥεῖ said, then you should probably throw an exception (You can make your own class and inherit it from std::exception) instead of couting something. Otherwise, your function is given too many responsibilites, and not all applications for a linked list have a console to output to.

The other thing I don't like is this conditional:

if (head == temp1 && tail == temp1) {
  head = nullptr;
  delete temp1;
} else if (temp1 == head) {
  head = head->next;
  delete temp1;
} else if (temp1 == tail) {
  temp2->next = nullptr;
  tail = temp2;
  delete temp1;
} else {
  temp2->next = temp1->next;
  delete temp1;
}

Notice how there is a delete temp1 at the end of every one of those conditionals. That breaks the D.R.Y principle. Make the delete temp1 unconditional.

\$\endgroup\$
5
\$\begingroup\$

You should provide a (template) class to encapsulate the inner states (head, tail) of a linked list, instead of a bunch of free functions and the Node structure. Something like:

template <typename DataType>
class LinkedList {
    // The Node doesn't need to be seen publicly
    struct Node {
        DataType data;
        Node *next;
    };

    Node* head;
    Node* tail;

public:
    LinkedList() : head(nullptr), tail(nullptr) {}
    Node* addEnd(DataType value);
    Node* addBeginning(DataType value);
    // ...
    void deleteSpecific(Node*);
};

template <typename DataType>
LinkedList<DataType>::Node* LinkedList::addEnd(DataType value) {
   // Implementation ...
}

template <typename DataType>
LinkedList<DataType>::Node* LinkedList::addBeginning(DataType value); {
   // Implementation ...
}

template <typename DataType>
void deleteSpecific(LinkedList<DataType>::Node* node) {
   // Implementation ...
}

Clients of the LinkedList class may use the auto keyword to keep variables of the private LinkedList<DataType>::Node structure:

LinkedList<int> ll;
auto item1 = ll.addEnd(5);
auto item2 = ll.addBeginning(42);
ll.deleteSpecific(item1);
\$\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.