A linked list with push pop append and destructor

Question

I tried to implement a linked list that can do pop(), push(), append(), printall(), and so on, and also I tried to handle the wraparound features, and de-wrap it when check if the list is cyclic to avoid endless loop, but I am sure this wrap and de-wrap features can be implemented better...

#include <iostream>

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

class LinkedList{

    std::size_t count;
    Node* head;

    public: 
    void pop();           //pop from head
    void push(int);       //push from head
    void append(int);     //append at end
    void wraparound();    //wrap around the list
    bool isCyclicDwrap(); //check if cyclic, if yes, de-wrap-around it

    void printll() const; 
    std::size_t size() const { return count; }

    LinkedList(): head(nullptr),count(0) {}
    ~LinkedList();
};


void LinkedList::pop(){

  if(head==nullptr){
    std::cout<<"empty stack !"<<std::endl;
    exit(0);
  }

  Node* cur = head;
  Node* tmp = cur->next;
  head = tmp;
  delete cur; count--;

}

void LinkedList::append(int data){
    Node* cur = head;
    Node* tmp = new Node;
    tmp->value = data;
    tmp->next = nullptr;

    if(!cur){
        head = tmp; count++;
    }
    else{
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = tmp; count++;
    }

}

void LinkedList::wraparound(){
    Node* cur =head;
    while(cur->next != nullptr)
        cur=cur->next;

    cur->next = head;
}

bool LinkedList::isCyclicDwrap()
{
    Node *n1, *n2;
    n1 = head;
    n2 = head->next;

    do{
        n1 = n1->next;
        n2 = n2->next->next;

        if(n1 == n2){

            Node* cur =head;
            size_t cnt=count;
            while(--cnt != 0)
                cur=cur->next; //move to the last node
            cur->next=nullptr; // -> de-warp-around !

            return true;
        }

    }while(n1 != head);

    return false;
}


void LinkedList::push(int data)
{
    Node* cur = (Node*)malloc(sizeof(Node));
    cur->value=data;
    cur->next=head;
    count++;
    head=cur;
}


void LinkedList::printll() const{
    if(head==nullptr)
        std::cout<<"empty Linkedlist!"<<std::endl;
    Node* cur = head;
    while(cur != nullptr){
        std::cout << cur->value << '\n';
        cur = cur->next;
    }
}

LinkedList::~LinkedList()
{
    Node* cur = head;

    while (cur != NULL)
    {
        Node* next = cur->next;
        delete cur;
        cur = next;
    }

    head = NULL;
}


int main(){
    LinkedList LL;
    LL.append(5);
    LL.append(6);
    LL.append(7);
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.wraparound();
    std::cout<<"Cyclic: "<<LL.isCyclicDwrap()<<"; if 1, then remove the Cyclic feauture!"<<std::endl;

    LL.push(4); //push
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
    LL.printll();
    std::cout<<"size of the stack/linkedlist: "<<LL.size()<<std::endl;

    LL.pop();
}

Answer 1

Without reading too far.

You have committed the biggest C++ sin possible. You have an owned pointer in your class and don't follow the rule of three (or five).

class LinkedList{

    std::size_t count;
    Node* head;          // This is an owned pointer.

You must implement the rule of three. Otherwise the following will cause you to blow up:

{
    LinkedList     list1;
    list1.push(5);

    LinkedList     list2(list1); // Copy construction.
}
// Both list go out of scope here and are destroyed.
// Both object have the same value for `head` and both destructors
// will destroy all the elements in that chain. You are going to have
// multiple double deletes.

// Same problem happens with assignment operator.

Answer 2

I see a few things that could improve your code quite a bit:

Linked List Structure Design

You declare your Node structure outside of your LinkedList class in the header file; this means that anyone including the header file can access your Node structure and use it in their code. This is bad OO design since the Node structure is really an implementation detail of the LinkedList. Therefore, the user should be able to use the linked list without ever having to use (or the ability to use) the Node data structure. To fix this issue, I would declare the Node data structure inside of the private space of your LinkedList class. Moreover, I would provide a constructor for the Node data structure that will populate the values of the structure for me:

class LinkedList {
    struct Node {
        int data;
        Node *next;
        Node(int d, Node *n = nullptr) :
            data(d), next(n) {}
    }* head;
};

In this way, I can use the more C++ way of initializing objects on the heap over the more C way of doing things.

C++ way (recommended):

Node *node = new Node(data);

More C-style way (deprecated / not recommended):

Node *node = new Node();
node->data = data;
node->next = nullptr;

Use C++ Style

Speaking of C and C++ ways, do NOT mix new and malloc in C++ code - especially when you're using delete to free objects allocated by both. new and delete call constructors/destructors whereas malloc and free don't. Use delete to free new'd objects and free to free malloc'd objects. This code is invalid and can cause issues:

void LinkedList::push(int data)
{
    Node* cur = (Node*)malloc(sizeof(Node));
    cur->value=data;
    cur->next=head;
    count++;
    head=cur;
}

Why not use the more C++ way of doing things:

void LinkedList::push(int data)
{
    Node* cur = new Node(data, head); // use constructor I defined for you above.
    ++count;
    head = cur;
}

In addition, keep your style consistent between NULL and nullptr. In C++11 and beyond, always prefer to use nullptr.

Linked List API

I would rename some of your functions to be a bit more descriptive. For example, I would make wraparound() be called make_cyclic(). I would also provide a counter function called make_acyclic() to break the cycle. To check for a cycle, I would rename your function to is_cyclic(). I would also add another function is_empty() to signal when the list is empty and a size() function to return the size of your list so far; otherwise, what's the point of the count member variable? There is also the added benefit that the empty() member function could clear up a bunch of bugs in your code:

Bugs

In your wraparound() and isCyclicDwrap() functions, you don't check for the case when the list is empty (when the head is pointing to nullptr). If the list is empty, derefrencing nullptr like this:

Node* cur = head;
while(cur->next)

is a segmentation fault error waiting to happen. The fix is to check if the list is empty before doing such operations.

Finally, I find your implementation of making the list acyclic (if it is cyclic) a little too heavy and breaks the principle that functions should only have one purpose. We could do something like this to split the two ideas of checking for a cycle and breaking one:

bool LinkedList::is_cyclic() const
{
    if (is_empty()) {
        return false;
    }

    Node *n1 = head, *n2 = head->next;
    while (n1 != n2) {
        if (!n2 || !n2->next) {
            return false;
        }
        n1 = n1->next;
        n2 = n2->next->next;
    }
    return true;
}

void LinkedList::make_acyclic()
{
    if (is_empty() || !is_cyclic()) {
        return;
    }

    Node *curr = head;
    while (curr->next != head) { // move to the end
        curr = curr->next;
    }
    curr->next = nullptr; // break the cycle
}

Simplify Some Functions

With the newly defined Node constructor, append() can become:

void LinkedList::append(int data){

    if(!head){
        head = new Node(data);
    }
    else{
        Node *cur = head;
        while (cur->next){
            cur = cur->next;
        }
        cur->next = new Node(data);
    }
    ++count;
}