Where is the mistake ?

Question

Hi ...

i am implementing a simple linked list in c++. I have a mistake and i don't see it :(

#include <stdexcept>
#include <iostream>

struct Node {

    Node(Node *next, int value):
    next(next), value(value) {
    }
    Node *next;
    int value;
};

class List {
    Node *first;
    int len;
    Node *nthNode(int index);

public:

    List():first(0),len(0){
    }

    // Copy - Konstruktor 
    List(const List & other){

    };

    // Zuweisungs - Operator O(len +other.len)
    List &operator=(const List &other) {
        clear();
        if(!other.len) return *this;
        Node *it = first = new Node(0,other.first->value);
        for (Node *n = other.first->next; n; n = n->next) {
            it = it->next = new Node(0, n->value);
        }
        len = other.len;
        return *this;
    }

    // Destruktor 
    ~List(){

    };


    void push_back(int value){

    };

    void push_front(int value){
        Node* front = new Node(0,value);

        if(first){
            first  = front;
            front->next = 0;
        }else{
            front->next = first;
            first = front;

        }
        len++;
    };

    int &at(int index){
        int count = 0 ;
        int ret ;
        Node *it = first;
        for (Node *n = first->next; n; n = n->next) {
            if(count==index) ret = n->value;
            count++;
        }
        return ret ;
    };

    void clear(){


    };

    void show() {
        std::cout << " List [" << len << " ]:{ ";
        for (int i = 0; i < len; ++i) {
            std::cout << at(i) << (i == len - 1 ? '}' : ',');
        }
        std::cout << std::endl;
    }
};

/*
 * 
 */
int main() {

    List l;
 //   l. push_back(1);
 //   l. push_back(2);
    l. push_front(7);
    l. push_front(8);
    l. push_front(9);
    l.show();
   // List(l). show();
}

it works ... but the output is :

List [3 ]:{ 0,134520896,9484585}

Answer 1

The push_front logic is wrong. It should look like this:

void push_front(int value){
    first = new Node(first, value);
    ++len;
}

While we're at it, your operator= isn't exception-safe. Implement copying in the copy-constructor and assign using the copy-and-swap idiom:

List& operator=(List other) { swap(other); return *this; }
void swap(List& other) {
    Node* tnode = first; first = other.first; other.first = tnode;
    int tlen = len; len = other.len; other.len = tlen;
}

On another note, don't implement the at member function; random access is very inefficient, and should not be encouraged. Implement iterators instead.

Answer 2

You are returning a reference to a local variable in at. The variable goes out of scope when the function exits. Accessing it afterwards is undefined behavior. You are lucky it does not crash.

You should also reconsider your implementation of show (O(n*n) seriously?) and push_front (if (first) ?).

Here is a better implementation of at:

Node *at(int index){
    int count = 0 ;
    for (Node *n = first; n; n = n->next) {
        if(count==index) 
            return n;
        count++;
    }
    return NULL;
};

It does not return a reference. You can not return a NULL-reference if index is larger than the length of the list. I also changed the return type to Node, so the caller can change value.