problem implementing simple linked list in c++, no output

Question

For my C++ programming course, my task is to implement a simple linked list using my own functions of addElement(), printList() and deleteList().

When I compile and run the following program, nothing happens. I get no warnings and using valgrind I couldn't find anything wrong.

The program code I am working with is as follows:

#include <iostream>
using namespace std;

struct Node {
  int data;
  Node *next;
  Node(int i) : data(i), next(nullptr) {}
  friend ostream &operator<<(ostream &os, const Node &n) {
    os << "Node\n"
       << "\tdata: " << n.data << "\n\tthis: " << &n << "\n\tnext: " << n.next;
    return os;
  }
};

void addElement(Node **head, int data);
void printList(Node *head);
void deleteList(Node *head);

void deleteList(Node *head) {
  Node *next = head;
  while (next) {
    Node *deleteMe = next;
    next = next->next;
    delete deleteMe;
  }
}

void addElement(Node **head, int data) {
  Node *n = new Node(data);
  n->next = *head;
  head = &n;
}

void printList(Node *head) {
  Node *next = head;
  while(next) {
    cout << next->data;
    next = next->next;
  }
}

int main() {
  Node *list = nullptr;
  addElement(&list, 1);
  addElement(&list, 2);
  addElement(&list, 3);
  addElement(&list, 4);
  printList(list);
  deleteList(list);
  return 0;
}

I have no idea why my code does not work and produce output. Please help and kind regards

Answer 1

void addElement(Node **head, int data) {
  Node *n = new Node(data);
  n->next = *head;
  head = &n;
}

Wrong in a couple of ways:

• head is a local variable in this function, changing it will have no effect on the outside world, you should be changing *head; and
• n is already a pointer to a node, you should use it directly, rather than using the address of it.

In other words, that final line of code should be:

*head = n;

---

And, a few other points. First, you can avoid all those double-pointer issues prevalent in C if you just learn to use references in C++, that's one of the great advantages of the latter language. Your code then becomes:

void addElement(Node *&head, int data) {
  Node *n = new Node(data);
  n->next = head;
  head = n;
}

// Call with: "addElement(list, 1)".

Second, if you want your items appended to the end of the list (a more usual requirement), you can do that in a couple of ways. The first is the search for the final one then append it after there:

void addElement(Node *&head, int data) {
  Node *n = new Node(data);
    if (head == nullptr) {
        head = n;
    } else {
        Node *curr = head;
        while (curr->next != nullptr) {
            curr = curr->next;
        }
        curr->next = n;
    }
}

The second (more efficient) is to maintain the tail element as well so that it is always available and you don't have to search for it on every insertion. That's best done with a split of functionality into separate List and Node classes, such as with:

#include <iostream>

using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int i) : data(i), next(nullptr) {}
};

struct List {
    Node *head;
    Node *tail;
    List() : head(nullptr), tail(nullptr) {}
};

void deleteList(List *&list) {
    Node *curr = list->head;
    while (curr != nullptr) {
        Node *deleteMe = curr;
        curr = curr->next;
        delete deleteMe;
    }
    delete list;
    list = nullptr;
}

void addElement(List *list, int data) {
    Node *n = new Node(data);
    if (list->head == nullptr) {
        list->head = list->tail = n;
    } else {
        list->tail->next = n;
        list->tail = n;
    }
}

void printList(List *list) {
    Node *curr = list->head;
    while (curr != nullptr) {
        cout << curr->data;
        curr = curr->next;
    }
    cout << '\n';
}

int main() {
    List *list = new List();

    addElement(list, 1);
    addElement(list, 2);
    addElement(list, 3);
    addElement(list, 4);

    printList(list);

    deleteList(list);

    return 0;
}

---

And, finally, though I realise you're still a relative beginner, you should at least be aware of the benefits of encapsulation (information hiding). A proper implementation would have the data in each class as private members, modifiable only by functions within the class itself (although at the request of outside callers, of course).

As it stands at the moment, I could write code that could easily modify the internal data of your class (data and next), causing serious issues. If the internal data was private, you could better protect against that.

Although I wouldn't suggest using this code for your assignment (assuming this is educational work), I'll include it anyway for your examination:

#include <iostream>
#include <functional>

using namespace std;

// Only used within List and private there so leave as public.

struct Node {
    Node(int value) : m_data(value), m_next(nullptr) {}
    int m_data;
    Node *m_next;
};

// Properly encapsulae to protect memebrs.

class List {
public:
    List() : m_head(nullptr), m_tail(nullptr) {}
    ~List() { clearAll(); }
    void clearAll();
    void addElement(int data);
    void traverse(const std::function<void(int)> &callback);
private:
    Node *m_head;
    Node *m_tail;
};

// Clear all items in list.

void List::clearAll() {
    Node *curr = m_head;
    while (curr != nullptr) {
        Node *deleteMe = curr;
        curr = curr->m_next;
        delete deleteMe;
    }
    m_head = m_tail = nullptr;
}

// Add an item to list.

void List::addElement(int data) {
    Node *node = new Node(data);
    if (m_head == nullptr) {
        m_head = m_tail = node;
    } else {
        m_tail->m_next = node;
        m_tail = node;
    }
}

// Traverse list, calling a callback for each item.

void List::traverse(const std::function<void(int)> &callback) {
    Node *curr = m_head;
    while (curr != nullptr) {
        callback(curr->m_data);
        curr = curr->m_next;
    }
}

// Test harness for the code above.

int main() {
    List list; // could also 'new' this but not needed.

    list.addElement(1);
    list.addElement(2);
    list.addElement(3);
    list.addElement(4);

     // Advanced lambda stuff for callback.

    std::cout << "Items are:";
    list.traverse([](int i) -> void {
        std::cout << " " << i;
    });
    std::cout << "\n";

    return 0;
}