Return element of linked list

Question

Please delete.

I want to implement a linked list. Unfortunately I'm not sure whether I'm on the right track.

#include <iostream>
using namespace std;

class Node {
    friend class List;
public:
    int value;
private:
    Node *next;
};

class List {
public:
    List ();
    ~List ();
    Node * first() const;
    Node * next(const Node * n) const;
    void append (int i);

    Node* head;
};

List::List() {
    Node* head = new Node();
}

List::~List() {
    while(head != NULL) {
        Node * n = head->next;
        delete head;
        head = n;
    }
}

Node * List::first() const {
    return head; // this could also be wrong
}

Node * List::next(const Node * n) const {
    return n + 1; // ERROR
}

void List::append(int i) {
    Node * n = new Node;
    n->value = i;
    n->next = head;
    head = n;
}

int main(void) {
    List list;
    list.append(10);

    return 0;
}

When I try to return an element in next() I get this error:

In member function ‘Node* List::next(const Node*) const’:|
error: invalid conversion from ‘const Node*’ to ‘Node*’ [-fpermissive]|

Could somebody please help me?

EDIT:
I've updated the error-line.

What are you trying to do in List::next? Are you trying to advance n nodes? — zdan
– zdan, Commented Apr 30, 2013 at 1:35
My fault. I'have updated this function, but still get an error. — Evgenij Reznik
– Evgenij Reznik, Commented Apr 30, 2013 at 1:38

tbondwilkinson · Accepted Answer · 2013-04-30 01:41:21Z

2

I think what you mean to be doing is returning the Node's next:

Node * List::next(const Node * n) const {
   return n->next;
}

You would use pointer arithmetic if this were an array where the size of each object was constant, but linked lists can't use pointer arithmetic. If you have an iterator, you could use the '++' operator to get the next object, but with this just stick to returning the node's next field.

I'm assuming this will also work because even though next is declared as private, you've made List a friend.

answered Apr 30, 2013 at 1:41

tbondwilkinson

1,0872 gold badges8 silver badges16 bronze badges

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

4 Comments

Evgenij Reznik Over a year ago

Do you also know, how to insert a new value between other values? Something like insert (Node * n, int i);. The new value should be before n.

tbondwilkinson Over a year ago

Sure. Save the next value of n, create a new Node with the value for i, then set n->next to the new node and the new node's next to the old value of n's next.

Evgenij Reznik Over a year ago

I get an infinit loop here: Node * temp = n->next; Node * n2 = new Node; n2->value = i; n->next = head; n2->next = temp;

tbondwilkinson Over a year ago

You don't want to be setting it to the head - you're inserting this node in some arbitrary location remember. You want to be setting it to your new node.

ithenoob · Accepted Answer · 2013-04-30 01:38:03Z

0

You are thinking that consecutive nodes are in consecutive blocks of memory, and they are not. Linked lists have nodes in random places in memory, which is why "next" points to the NEXT node. You cannot increment or add as you are trying (well you can, but semantically it would be incorrect.)

answered Apr 30, 2013 at 1:38

ithenoob

3261 gold badge2 silver badges11 bronze badges

2 Comments

Evgenij Reznik Over a year ago

Could you please tell me how to improve it?

ithenoob Over a year ago

You would have to cycle through all the nodes in a for loop until you get to the requested node

Collectives™ on Stack Overflow

Return element of linked list

2 Answers 2

4 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related