1

My add function clearly has a problem as it is dereferencing first and first is pointing to nothing because of that. I just don't know how to fix it so that it isn't a null pointer.

    struct Node
    {
        int data;
        Node *next;
    };

    class LinkedList
    {
        Node *first;
        Node *last;
        int count;
        public:

        LinkedList()
        {
            first = NULL;
            last = NULL;
            count = 0;
        }


        void Add(int item)
        {
            if (first == NULL)
            {
                first->data = item;
                last->data = item;
                last->next = NULL;
                first->next = last;
                count = 1;
            }
            else
            {
                Node *newNode = new Node;
                newNode->data = last->data;
                newNode->next = last;
                last->data = item;
                last->next = NULL;
                count ++;
            }
        }
3
  • If you don't want first to be null, then point it to something. You already know how to create a Node (as shown in your else block), so do: first = new Node;.
    – jamesdlin
    Apr 9, 2013 at 2:53
  • 6
    Your conditional says if first is null, then use first. This is incorrect. You can't use first if its null. Apr 9, 2013 at 2:54
  • You can make it not NULL by allocating memory for it, just like you did in the else case (Node *newNode = new Node;).
    – MatthewD
    Apr 9, 2013 at 2:57

3 Answers 3

6

You have a lot of code in common between the if and the else.

        if (first == NULL)
        {
            first->data = item;
            last->data = item;
            last->next = NULL;
            first->next = last;
            count = 1;
        }
        else
        {
            Node *newNode = new Node;
            newNode->data = last->data;
            newNode->next = last;
            last->data = item;
            last->next = NULL;
            count ++;
        }

In the if, you increment count from 0 to 1. In the else, you also increment it.

count is always getting incremented. So you don't need to type it twice.

        if (first == NULL)
        {
            first->data = item;
            last->data = item;
            last->next = NULL;
            first->next = last;
        }
        else
        {
            Node *newNode = new Node;
            newNode->data = last->data;
            newNode->next = last;
            last->data = item;
            last->next = NULL;
        }
        count ++;

You're also setting last->data to item in both of them.

And you're setting last->next to NULL in both of them.

        if (first == NULL)
        {
            first->data = item;
            first->next = last;
        }
        else
        {
            Node *newNode = new Node;
            newNode->data = last->data;
            newNode->next = last;
        }
        last->data = item;
        last->next = NULL;
        count ++;

You also forgot to create a new Node when it's the first new node.

        if (first == NULL)
        {
            Node *newNode = new Node;   // Added
            first = newNode;            // Added
            last = newNode;             // Added
            first->data = item;
            first->next = last;
        }
        else
        {
            Node *newNode = new Node;
            newNode->data = last->data;
            newNode->next = last;
        }
        last->data = item;
        last->next = NULL;
        count ++;

The first->data = item in your if is redundant. first is the same as last there, and last->data = item is already happening.

        if (first == NULL)
        {
            Node *newNode = new Node;
            first = newNode; 
            last = newNode;
            // Removed
            first->next = last;
        }
        else
        {
            Node *newNode = new Node;
            newNode->data = last->data;
            newNode->next = last;
        }
        last->data = item;
        last->next = NULL;
        count ++;

And since first and newNode have the same value in that if, we can use the variable names interchangeably.

        if (first == NULL)
        {
            Node *newNode = new Node; 
            first = newNode;            // These two pointers are equal!
            last = newNode;
            newNode->next = last;       // (same pointer)
        }
        else
        {
            Node *newNode = new Node;
            newNode->data = last->data;
            newNode->next = last;
        }
        last->data = item;
        last->next = NULL;
        count ++;

Now, almost everything in your else is also in your if. It can all be moved out.

        Node *newNode = new Node; 
        if (first == NULL)
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            newNode->data = last->data;
        }
        newNode->next = last;
        last->data = item;
        last->next = NULL;
        count ++;

That code should be more understandable now, too. The lesson: Don't Repeat Yourself. :)

1
  • 1
    Excellent post with plenty of detail and good explanations so the OP can follow along. +1 Apr 9, 2013 at 4:58
3
if (first == NULL)
{
    /* if first is NULL dereference it. Hooray! */
    first->data = item;
    ...
5
  • I think the OP might already know that ("it is dereferencing first and first is pointing to nothing") but doesn't understand how to fix it.
    – jamesdlin
    Apr 9, 2013 at 2:58
  • What about just simply first = new Node;?
    – kccqzy
    Apr 9, 2013 at 3:00
  • @BdkFivehunna you're going to need a new Node regardless of whether it's NULL or not. Apr 9, 2013 at 3:00
  • @jamesdlin considering that the else part of the loop allocates a new node, that seems unlikely. But you never know. Apr 9, 2013 at 4:58
  • @NikBougalis: Actually the OP replied to this answer and confirmed what I said, but for some reason deleted the comment.
    – jamesdlin
    Apr 9, 2013 at 5:34
0

Have a look at linked list

There are few details, to start with when first == NULL you need to create first, insert it into linked list and hook it up, see linked article for some algorithms.

I would say the simplest is single linked list with a header node (instead of first *) which could point to itself, but there are many ways to implement linked list and it depends on what you choose how to hook up the elements.

It depends on what you are after but if you just need something working then you could pick up from boost intrusive circular slist algorithms where you just define your own struct with data and next pointer, tell it how to access next and use provided algorithms to do all the work (link and unlink nodes).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.