My custom linked list

Question

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

"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++. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Feb 23, 2018 at 20:09
πάντα-ῥεῖ, I've actually thought about it, does it make big difference? What are the pros of actually using a template class? — saad.sawash
– saad.sawash, Commented Feb 23, 2018 at 20:14
"What are the pros of actually using a template class?" That it's generic? — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Feb 23, 2018 at 20:14

Arnav Borborah · Accepted Answer · 2019-01-17 21:41:37Z

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.

πάντα ῥεῖ · Accepted Answer · 2018-02-23 20:51:48Z

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

Stack Exchange Network

My custom linked list

2 Answers 2

You must log in to answer this question.

Hot Network Questions

My custom linked list

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions