C++ Pointer-based LinkedList

Question

I'm starting to learn C++ - in particular pointers. I thought I would attempt a basic linked-list. Here's my code:

#include <iostream>

using namespace std;

struct Linked {
    Linked *next;
    string val;
};

Linked newLinked(string val);
Linked addLinked(Linked l, string val);
void printLinked(Linked l);

Linked newLinked(string val) {
    Linked l;
    l.val = val;
    l.next = NULL;
    return l;
}

Linked addLinked(Linked l, string val) {
    Linked n = newLinked(val);
    n.next = &l;
    return n;
}

void printLinked(Linked l) {
    Linked *r = &l;
    while (r != NULL) {
        cout << (*r).val << endl;
        r = (*r).next;
    }
}

int main() {
    Linked list = newLinked("This is the root node.");
    list = addLinked(list, "This is the second node.");
    list = addLinked(list, "This is the third node.");
    list = addLinked(list, "This is the fourth, and final, node.");
    printLinked(list);
    return 0;
}

Sorry if my formatting is horrible or I'm breaking convention, still learning those. (If you wish please go ahead and point out how I can improve my codestyle, I am coming from a Java/JS background!)

When running, I get this:

This is the fourth, and final, node.
�;��R�;��R 
This is the fourth, and 
�;��R�;��R

My guess here is that the memory which contains the earlier strings is being overwritten -- the length of "This is the fourth, and " is the same as "This is the second node.".

Unfortunately I am stumped as to why this is... I am hoping someone here may be able to point me (haha) in the right direction.

In `addLinked` you write `n.next = &l;`. `l` is a parameter and only lives until the end of the function and then disappears. `n.next` will then point to garbage. The right direction would be somewhere [here](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — nwp, Sep 08 '17 at 22:28
Instead of a value factory function `newLinked`, just define a constructor of the class `Linked`. — Cheers and hth. - Alf, Sep 08 '17 at 22:35
-> notation is equivalent to "(*).", so you can (and should) do r->val instead of (*r).val — Matthew Woo, Sep 08 '17 at 22:40
There are a plethora of linked list examples and tutorials on the internet that you can compare your version with. — Thomas Matthews, Sep 08 '17 at 22:45
You don't need to forward declare functions if they are defined ahead of their first usage. Right now you have a potential bug should you change the definition of `Linked newLinked(string val)` to `Linked newLinked(const string &val);` while chasing a potential performance advantage and forget to also change the forward declaration. — user4581301, Sep 08 '17 at 22:49

score 0 · Answer 1 · answered Sep 09 '17 at 00:09

This is how you can make your code working.

struct Linked {
Linked *next;
string val;
};

Linked* newLinked(string val);
Linked* addLinked(Linked* l, string val);
void printLinked(Linked l);

Linked* newLinked(string val) {
   Linked *l = new Linked;
   l->val = val;
   l->next = NULL;
   return l;
}

Linked* addLinked(Linked* l, string val) {
   Linked *n = newLinked(val);
   n->next = l;
   return n;
}

void printLinked(Linked* l) {
    Linked *r = l;
    while (r != NULL) {
       cout << (*r).val << endl;
       r = (*r).next;
    }
}

int main(){
    Linked *list = newLinked("This is the root node.");
    list = addLinked(list, "This is the second node.");
    list = addLinked(list, "This is the third node.");
    list = addLinked(list, "This is the fourth, and final, node.");
    printLinked(list);

    return 0;
}

Note that this causes memory leaks as we do new but no delete. We'll need something like:

void destroyList(Linked *l){
   while(l){
      Linked *r = l->next;
      delete l;
      l = r;
   }
}

to avoid leaks. Call this destroyList at the end of main().

C++ Pointer-based LinkedList

1 Answers1