Linked lists; My first attempt

Alright, well I tried my first attempt at creating a linked list. It didn't work out so well.

Code:

#include <iostream>

using namespace std;

struct node {
    int key_value;
    node *next;
};

class list {
    public:
        list();
        void list_insert(int);
        void list_output();
    private:
        node *root;
};

list::list() {
    root = new node;
    root->next = NULL;
    root->key_value = 0;
}

void list::list_insert(int value) {
    node *pos;
    pos = root;


    while (pos->next != NULL) {
        pos = pos->next;
    }

    if (pos->next == NULL) {
        pos->key_value = value;
    }
}

void list::list_output() {
    node *pos;
    pos = root;
    int count = 1;

    do {
        cout << "Position " << count << ": " << pos->key_value;
        count += 1;
    }
    while (pos->next != NULL);
}

int main() {
    list lista;

    lista.list_insert(3);
    lista.list_insert(4);

    lista.list_output();

    return 0;
}

There is the code. I know it's not going to be the most proficient way to do it, but just ignore that, if you please.

If you run it, it only outputs the last value added to the list. Any ideas as to why?

Code:

void list::list_output() {
    node *pos;
    pos = root;
    int count = 1;

    do {
        cout << "Position " << count << ": " << pos->key_value;
        count += 1;
    }
    while (pos->next != NULL);
}

Well, you never actually go

Code:

pos = pos->next

which you probably intended, so you'll get the first element printed over and over again infinitely. Also, that code doesn't handle the case where the list is empty -- you'd get a segmentation fault. It's perhaps better to use something like this:

Code:

pos = head;
while(pos) {
    /* handle pos */
    pos = pos->next;
}

Or, if you prefer,

Code:

for(pos = head; pos; pos = pos->next) {
    /* handle pos */
}

That's assuming, of course, that the list can be empty. As written, you've designed it so that the list always has at least one element. You can do it that way, if you want to -- it makes the code a bit simpler because you don't have to handle the special case of an empty list most of the time -- but it does take up more memory, and it can be annoying because you often have a spurious node in the list that you didn't mean to insert. It's best to allow empty lists and initialize the list with something like this:

Code:

root = NULL;

This code is . . . very broken.

Code:

void list::list_insert(int value) {
    node *pos;
    pos = root;


    while (pos->next != NULL) {
        pos = pos->next;
    }

    if (pos->next == NULL) {
        pos->key_value = value;
    }
}

So, first you advance pos to the end of the list. Then, after a redundant check to make sure you really are at the end of the list (when you just went there!), you change the value of the last element in the list to your value. What you need to do instead at this point is to create a new node, assign your value to that, and add that node to the end of the list.

Actually, it's a whole lot simpler if you just assign new elements to the beginning of the list, because you don't have to transverse the list first to find its end. Unless, of course, the order of the nodes matters, and you intend to keep the list sorted or something. In which case you transverse the list until you find the position to insert the new node.

So, something like this might work:

Code:

void list::list_insert(int value) {
    node *latest = new node;

    latest->value = value;
    latest->next = root;
    root->next = latest;
}

Really. It's that simple. That code handles empty linked lists as well.

There's also many linked list tutorials around, such as this one: http://www.cprogramming.com/tutorial/lesson15.html

Ah, thank you for the help.

I completely re-wrote it and came up with:

Code:

#include <iostream>

using namespace std;

struct node {
        int value;
        node *next;
};

class list {
    public:
        list();
        void node_add(int);
        void list_output();
    private:
        node *root;
        node *endpos;
};

list::list() {
    root = new node;
    root->next = NULL;
    endpos = root;
}

void list::node_add(int value) {
    endpos->next = new node;
    endpos = endpos->next;
    endpos->value = value;
    endpos->next = NULL;
}

void list::list_output() {
    node *position;
    position = root;
    int count = 0;

    do {
        cout << "Node " << count << ": " << position->value << endl;
        position = position->next;
        count += 1;
    }
    while (position != NULL);
}

int main() {
    list lista;

    lista.node_add(1);
    lista.node_add(2);
    lista.node_add(3);
    lista.node_add(7);
    lista.node_add(5);

    lista.list_output();

    return 0;
}

And it seems to work fine.

I think there's still an issue with your code . . .

Code:

list::list() {
    root = new node;
    root->next = NULL;
    endpos = root;
}

void list::node_add(int value) {
    endpos->next = new node;
    endpos = endpos->next;
    endpos->value = value;
    endpos->next = NULL;
}

As you can see, in list::list(), an "empty" linked list is initialized to contain one element, with endpos pointing at this new element. Then node_add() sets endpos->next->value, after allocating space for endpos. But this leaves the first value, root->value, unset.

However, when you go to print the data in the linked list, you start by printing root->value.

Code:

void list::list_output() {
    node *position;
    position = root;
    int count = 0;

    do {
        cout << "Node " << count << ": " << position->value << endl;
        position = position->next;
        count += 1;
    }
    while (position != NULL);
}

This first value will probably be uninitialized, or at least spurious.

It's a variation of the problem I mentioned earlier. If you always have one element in your linked list, you have to ignore that element when you iterate over the linked list, for example to print it. This can get convoluted and hard to read. The alternative is to allow an empty linked list, that is one that is initialized like this:

Code:

root = endpos = NULL;

It means you still have to add some special cases, but they can generally be of the form

Code:

if(!root) return;

or a simple first insertion.

Code:

root = endpos = NULL;

So, when you're doing that, I'm not sure what exactly it's doing. Is root still a pointer to a node? What happens when you set the pointer to NULL. It simply points to nothing?

That's right. It points to nothing at all. This makes sense, because the list is supposed to be empty. The beginning of the list is nothing; the beginning of the list is the end. This concept should make sense to you -- after all, you set endpos->next to NULL on numerous occasions.

It doesn't make sense for a list to contain an element if the list is empty. And when you allocate memory for root to point to, you're putting a node into the list.

Okay, so I should set root to point to a new node, and then just set the root->next value? What about root->value? Isn't it still unitialized? 'root' isn't supposed to contain a 'value', correct?

[edit]

Okay, so I should set root to point to a new node, and then just set the root->next value? What about root->value? Isn't it still unitialized? 'root' isn't supposed to contain a 'value', correct?

Don't point root to a new node. Point it to NULL. That way root->value can be a real value in your list, rather than being a sentenial. [/edit]

Think of it this way. Say you had an array, and you were using it as a stack.

Code:

int data[MAX], pos;

What you're doing is something like this:

Code:

void init_stack() {
    data[0] = -1;
    pos = 0;
}

You set data[0] to something, in this case -1, but in your case a new node. Then you set pos to reference to the last element in the stack, in this case, data[0].

Then you insert stuff into this data structure like this.

Code:

void insert_value(int value) {
    pos ++;  /* "allocate" new node */
    data[pos] = value;
}

Now you've added a value to the array/list, and pos once again points to the last element.

But, as you can probably see, you've skipped over data[0]. Here's the same code laid out in linear fashion.

Code:

    data[0] = -1;
    pos = 0;

    pos ++;  /* "allocate" new node */
    data[pos] = value;

You can see that data[0] is not set to a proper value. Sure, it's set to -1. But when you go to print the list or something, you'll get -1 and then your real values.

You could get around this by having your printing functions start printing at data[1]. But this is just an ugly hack. It would make much more sense to allow an empty data structure.

In this case, because pos has to point to the last element, an empty structure is represented with pos=-1.

Code:

void init_stack() {
    pos = -1;
}

The insert_value() code would work in this case, although with your linked list you'd have to add a special case, for when the list is empty, to assign the new node to root.

The printing code just then has to make sure there's something in the list. In this case, something like

Code:

for(x = 0; x <= pos; x ++)

would handle things automatically. You can do this with linked lists, too, if you're careful.

Code:

void print_list() {
    node *pos = root;

    while(pos) {
        print_node(pos);
    }
}

Ah, OK. That clears it up. Now, I have this:

Code:

list::list() {
    root = endpos = NULL; // Sets root to NULL, and endpos to NULL
}

void list::node_add(int value) {
    endpos = new node; // Makes root, or whatever the current last node->next is, a new node
    endpos->next = NULL; // Sets the root->next to NULL
    endpos->value = value; // Sets the value...
    endpos = endpos->next; // Then sets endpos to the empty node at the end
}

void list::list_output() {
    node *pos = root;

    while(pos) {
        cout << pos;
        pos = pos->next;
    }
}

Is the code right in the node_add() function? Because, at the moment, I get nothing when I output. 'pos' shouldn't be NULL, I don't think. Obviously I'm not seeing something...

This doesn't quite work, as you have seen.

Code:

void list::node_add(int value) {
    endpos = new node; // Makes root, or whatever the current last node->next is, a new node
    endpos->next = NULL; // Sets the root->next to NULL
    endpos->value = value; // Sets the value...
    endpos = endpos->next; // Then sets endpos to the empty node at the end
}

You set endpos to a new node, fill in that node, and then set endpos to endpos->next (which is NULL). The trouble is, when you initially set endpos to a newly allocated node, you're not changing the list. You're just changing what endpos points to.

You have to set endpos->next in order to actually modify the linked list. This can be difficult, of course, if endpos is NULL, so you have to allow for this.

Code:

void list::node_add(int value) {
    if(!head) {  /* start of the linked list */
        head = endpos = new node;
    }
    else {  /* not the start of the linked list */
        endpos->next = new node;
        endpos = endpos->next;
    }

    /* endpos now points to the newly allocated node */
    endpos->next = NULL;
    endpos->value = value;  /* sets the value */

    /* the next time this function is called, endpos->next (which is currently NULL)
        will be assigned to point to a newly allocated node */
}

The code has to be this complicated because, when head and endpos are NULL, the list is empty, and head has to be assigned to the new node. But when there is already something in the linked list, you can just assign endpos->next to the new node.

Another way of looking at it is this: endpos has to point to the previous element in the linked list, so that you can assign endpos->next to a new element. Of course, when there is nothing in the linked list, there is no previous element, and so this case has to be handled specially.