A simple Linked List implementation in C++

Question

I am trying to implement a simple linked list using c++. I am probably making a silly mistake somewhere.Through this i want to learn classes and pointers in C++. For the code

#include <iostream>
using namespace std;

class node
{
public: 
    node* next;
    int data;

    node(int d);
    void append(int d);
}; 

node::node(int d)
{
    data = d;
    next = NULL;
}


void node::append(int d)
{
    node nw = node(d);
    if(next==NULL)
        next = &nw;
    else
    {
        node *n = next;
        while((*n).next!=NULL)
        {
            n = (*n).next;
        }
        (*n).next = &nw;
    }
}

I am getting 81 as the node next to 1.

int main()
{
    node n = node(1);
    n.append(3);
    n.append(2);
    n.append(81);
    n = *(n.next);
    cout<< n.data << '\n';
}

Please help me figure out where am i making mistake.

Aasmund Eldhuset · Accepted Answer · 2011-06-17 10:15:45Z

6

There might be other errors, but this is extremely dangerous: You are creating a local variable to represent the new node: node nw = node(d);, and then you make the last node in the list point to nw. However, since nw is a local variable, it will cease to exist when the function returns. So the next pointer of the last node now points to something that no longer exists. You need to use new node(d) (which returns a pointer to a node) in order to create an object that will continue to exist after the function has returned.

answered Jun 17, 2011 at 10:15

Aasmund Eldhuset

38.1k4 gold badges74 silver badges85 bronze badges

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

Comments

ypnos · Accepted Answer · 2011-06-17 10:16:02Z

3

You error is that you create an object on the stack, then store a pointer to it. The stack gets overwritten, your object gets overwritten, your pointer is invalid.

In your case the node that holds 3 is in the end overwritten by the node that holds 81.

answered Jun 17, 2011 at 10:16

ypnos

53k14 gold badges104 silver badges151 bronze badges

Comments

MGZero · Accepted Answer · 2011-06-17 13:42:40Z

1

Might I also suggest that you make a LinkedList class separate from the Node class? You can then move the append() method to that class and have it manage your nodes.

answered Jun 17, 2011 at 13:42

MGZero

6,0225 gold badges33 silver badges47 bronze badges

Comments

Gleb Varenov · Accepted Answer · 2011-06-17 10:34:29Z

0

void node::append(int d) {
    node *nw = new node(d);
    node *last = this;

    while((*last).next!=NULL) 
        last = (*last).next;

    (*last).next = nw;
}

Yes, if your object are meant to stay around after function finishes you should create them on the heap (the new keyword), not on stack.

answered Jun 17, 2011 at 10:34

Gleb Varenov

2,8453 gold badges20 silver badges18 bronze badges

2 Comments

Nitin Garg Over a year ago

I had to use node * nw = (node*) operator new (sizeof(node)); new (nw) node(d);

Gleb Varenov Over a year ago

@Nitin thats pretty weird. What compiler do you use?

user1899563 · Accepted Answer · 2013-07-06 09:14:00Z

0

by using

node *nw=new node(d);

gives pointer to the same location every time which leads to the over-writing of the data. so even by using new , the output is 81

Collectives™ on Stack Overflow

A simple Linked List implementation in C++

5 Answers 5

Comments

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related