How to correctly implement a linked list class in C++

Question

I'm trying to implement a simple list in C++ but I'm stuck with writing the add function

When adding one element it works fine but then it just keeps adding the element indefinitely

This is weird because I'm making sure to only add to the tail of the linked list and the last element is always NULL.

The result is correct only if we add to a list containing just one element.

#include <iostream>

using namespace std;

class List {

    int value;

    public:
    List(int value);
    List* next;
    List* tail();
    void add(int value);
    void reverse();
    void echo();
};


List::List(int value){
    List::value = value;
    List::next = NULL;
}
List* List::tail(){
    List* tail = this;
    for(;tail->next!=NULL; tail = tail->next);
    return tail;
}
void List::add(int value)
{
    List next (value);
    List* tail = List::tail();
    tail->next = &next;
}
void List::echo()
{
    cout << List::value << "    ";

    if(next!=NULL){
        next->echo();
    }
}

int main(){
    List list (3);
    list.add(1);
    list.add(2);

    list.echo();
}

&next is a pointer to a local variable so causes undefined behaviour when it is dereferenced later — Alan Birtles
– Alan Birtles, Commented Jul 20, 2021 at 10:32

CiaPan · Accepted Answer · 2021-07-20 10:32:09Z

1

The variable

List next (value);

is automatic, so it exists from the line of its declaration till the end of the add() function. Once the function returns, the variable no longer exists and the pointer you assigned with

tail->next = &next;

becomes invalid.

You should allocate the 'next' item at a heap:

List* next = new List(value);

and append it to the list with

tail->next = next;

answered Jul 20, 2021 at 10:32

CiaPan

9,5802 gold badges23 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

t.niese Over a year ago

new does not necessarily allocate on the heap. The important part is that new creates an object with dynamic storage duration.

Alan Birtles Over a year ago

might be an idea to mention deleteing the created nodes

prehistoricpenguin Over a year ago

To avoid the memory leak.

CiaPan Over a year ago

@AlanBirtles Yup, I might also mention appropriate design of List and ListNode to separate responsibilities, as well as lacking methods to seek and remove items, possible adding at front and at end of a list and even at arbitrary place anywhere inside a list. And not forget a missing implementation of Reverse() method (which requires separating List from ListNode or at least a double linking, so it can find the true start of the list). But I didn't like writing a programming manual. Not this time at least.

CiaPan Over a year ago

@Tawfik So you want to reverse a list? You need to know the first item of the list then. Having the List class representing a list's node is bad in this situation, as the node has no ability to find out, whether it is is the first node or it is a 'next' after some other node. As a result it can't reliably do reversing in general.

|

ShadowMitia · Accepted Answer · 2021-07-20 10:48:05Z

1

The problem is this part of add : List next (value);. Overall your add function is correct, but you're creating an object that once you exit the function, will be destroyed. When you're assigning tail->next = &next;, inside the add function it's fine, but once you exit the function, that piece of memory doesn't exist anymore.

You have to create a new piece of memory somehow, for example using List* next = new List(value);.

And now that you have manually allocated memory, you need to delete all of them once your object is destroyed, to release the memory, otherwise you'll get a memory leak.

edited Jul 20, 2021 at 10:48

answered Jul 20, 2021 at 10:32

ShadowMitia

2,5531 gold badge24 silver badges26 bronze badges

3 Comments

Tawfik Over a year ago

why should I deallocate it? it's part of my list

ShadowMitia Over a year ago

Right, I should've been more precise. When you're object is destroyed you should deallocate it.

ShadowMitia Over a year ago

I4ve modified my answer.

Collectives™ on Stack Overflow

How to correctly implement a linked list class in C++

2 Answers 2

8 Comments

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

3 Comments

Related