NERD STUFF: Pointer fun

First attempt at writing a linked list:
(First attempt at writing in C++, for that matter)

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class List {
    Node head;
    Node tail;
    int len;

public:

    List() {

        head.data = 0;
        head.next = &tail;

        tail.data = 0;
        tail.next = NULL;

        len = 0;
    }

    void addBeg (int n) {
        Node addMe;

        addMe.data = n;
        addMe.next = head.next;
        head.next = &addMe;

        len++;
    }

    void output () {

        Node *current = &head;

        while (current -> next != NULL) {
           cout << current -> data << endl;
           current = current -> next;
        }

        cout << current -> data;
    }

    int returnLen () {
        return len;
    }

};

int main()
{
    List list;

    list.addBeg(3);
    list.addBeg(2);
list.addBeg(1);

    list.output();
}

And this is what it outputs:

0
-858993460

Awesome.

So.. one of the reasons this doesn't work is because, in addBeg, a node is being created on the stack (rather than the heap). So after list.addBeg(2) is called in main and we actually go into the addBeg procedure, newNode is created which we squish between head and tail. BUT, after the closing brace } in addBeg, since newNode was created on the stack, it gets destroyed and now head points to ridiculousness and we have a memory leak in tail (data still there, but no way to access it).

I have to build a constructor for the Node object so I can call Node* nodeName = new Node in addBeg to create a node on the heap.
So, 2nd try:

#include <iostream>
using namespace std;

class Node {
public:
    Node() {};
    int data;
    Node* next;
};

class List {

    Node head;
    Node tail;
    int len;

public:

    List() {

        head.data = 0;
        head.next = &tail;

        tail.data = 0;
        tail.next = NULL;

        len = 0;
    }

    void addBeg (int n) {

        Node* addMe = new Node();

        addMe -> data = n;
        addMe -> next = head.next;

        head.next = addMe;
        len++;
    }

    void output () {

        Node *current = &head;
        current = current -> next;

        while (current -> next != NULL) {
           cout << current -> data << endl;
           current = current -> next;
        }
    }

    int returnLen () {
        return len;
    }

};

int main() {
    List list;

    list.addBeg(3);
    list.addBeg(2);
    list.addBeg(1);
    list.output();

    return 0;
}

And this is what it outputs:

1
2
3

Yes! That's what I wanted!

I know this still isn't perfect (my brother complained about the sentinel nodes head and tail, and that I declared list on the stack rather than the heap, and that I didn't have a destructor, or a remove first procedure, and that my names were weird), but BLEHH it's my first c++ thing

That was fun! Pointers make me want to pull my hair out sometimes but I kind of like struggling with problems. The more you struggle, the better it feels when you actually get it

November 08, 2012

Pointer fun