Problem with creating a singly linked list

I was carefully going through the examples in a book of mine. Everything was going fine until I created the SListIterator class. It keeps pointing at its constructor. I tried everything but no luck. Here are the errors:

error C2143: syntax error : missing ';' before '<'
error C2501: 'X3D::SListIterator<Datatype>::SLinkedList' : missing storage-class or type specifiers
error C2238: unexpected token(s) preceding ';'
error C2143: syntax error : missing ')' before '<'
error C2143: syntax error : missing ';' before '<'
error C2059: syntax error : ')'
error C2334: unexpected token(s) preceding '{'; skipping apparent function body

Any help would be appreciated. Thanks.

SListNode.h:

Code:

---

#ifndef SLISTNODE_H
#define SLISTNODE_H

namespace X3D
{
        template <typename Datatype> class SListNode
        {
        public:
                Datatype m_data;
                SListNode<Datatype> *m_next;

                // Inserts a new data value in the linked list. This is
                // not sorted nor put at the very end of the list.
                void InsertAfter(Datatype data)
                {
                        // create the new node and assign its given value.
                        SListNode<Datatype> *newNode = new SListNode<Datatype>;
                        newNode->m_data = data;
            // have the new node point to the next node.
                        newNode->m_next = m_next;
                        // make the previous node point to the new node.
                        m_next = newNode;
                }
        };
}

#endif

---

SLinkedList.h:

Code:

---

#ifndef SLINKEDLIST_H
#define SLINKEDLIST_H

#include "SListNode.h"
#include "SListIterator.h"

namespace X3D
{
        template <typename Datatype> class SLinkedList
        {
        public:
                SListNode<Datatype> *m_head;
                SListNode<Datatype> *m_tail;
                int m_count;

                SLinkedList()
                {
                        m_head = 0;
                        m_tail = 0;
                        m_count = 0;
                }

                ~SLinkedList()
                {
                        SListNode<Datatype> *itr = m_head;
                        SListNode<Datatype> *next;

                        while (itr != 0)
                        {
                                // save the pointer to the next node
                                next = itr->m_next;
                                // delete the current node
                                delete itr;
                                // make the next node the current node
                                itr = next;
                        }
                }

                void Append(Datatype data)
                {
                        if (m_head == 0)
                        {
                                m_head = m_tail = new SListNode<Datatype>;
                                m_head->m_data = data;
                        }
                        else
                        {
                                // insert a new node after the tail and reset the tail.
                                m_tail->InsertAfter(data);
                                m_tail = m_tail->m_next;
                        }

                        m_count++;
                }

                // adds a new node at the beginning of the list.
                void Prepend(Datatype data)
                {
                        // create a new node
                        SListNode<Datatype> *newNode = new SListNode<Datatype>;
                        newNode->m_data = data;
                        newNode->m_next = m_head;
                        // set the head node and the tail node if needed.
                        m_head = newNode;
                        if (m_tail == 0)
                                m_tail = m_head;
                        m_count++;
                }

                void RemoveHead()
                {
                        SListNode<Datatype> *node = 0;

                        if (m_head != 0)
                        {
                                node = m_head->m_next;
                                delete m_head;
                                m_head = node;

                                if (m_head == 0)
                                        m_tail = 0;

                                m_count--;
                        }
                }

                void RemoveTail()
                {
                        SListNode<Datatype> *node = m_head;

                        while (m_head != 0)
                        {
                                if (m_head == m_tail)
                                {
                                        delete m_head;
                                        m_head = m_tail = 0;
                                }
                                else
                                {
                                        while (node->m_next != m_tail)
                                                node = node->next;
                               
                                        m_tail = node;
                                        delete node->m_next;
                                        node->m_next = 0;
                                }

                                m_count--;
                        }
                }

                // Creates a new iterator pointing to the head in the
                // current list.
                SListIterator<Datatype> GetIterator()
                {
                        return (SListIterator<Datatype>(this, m_head));
                }
        };
}

#endif

---

SListIterator.h:

Code:

---

#ifndef SLISTITERATOR_H
#define SLISTITERATOR_H

#include "SLinkedList.h"

namespace X3D
{
        template <typename Datatype> class SListIterator
        {
        public:
                SListNode<Datatype> *m_node;
                SLinkedList<Datatype> *m_list;

                // Initializes the iterator.
                SListIterator(SLinkedList<Datatype> *list = 0,
                        SListNode<Datatype> *node = 0)
                {
                        m_list = list;
                        m_node = node;
                }

                // Resets the iterator to the head node of the list.
                void Start()
                {
                        if (m_list != 0) 
                                m_node = m_list->m_head;
                }

                // Moves the iterator towards the next node in the list.
                void Forth()
                {
                        if (m_list != 0)
                                m_node = m_node->m_next;
                }

                // Returns a reference of the item stored in the node
                // that the iterator is pointing to.
                Datatype& Item()
                {
            return (m_node->m_data);
                }

                // Returns true if the current node being pointed to is
                // valid. Returns false otherwise.
                bool Valid()
                {
                        return (m_node != 0);
                }
        };
}

#endif

---

Looks like you have a recursive include. Perhaps one of those should be a forward declaration.

Each class is in its own header file. I wonder if it's just the wrong includes on top? The syntax looks fine, so if its just having a problem with SListIterator, it seems that its not the code but the includes somehow.

Yes, you have a recursive include. That means that one header includes another, and that header includes the first. That won't work, because the source file can only include one of them first.

Do you know what a forward declaration is? You have to change one of the header files to not include the other, but instead use a forward declaration of some sort.

Check the headers. The problem is that you have recursive #includes.

SLinkedList.h:

Code:

---

#ifndef SLINKEDLIST_H
#define SLINKEDLIST_H

#include "SListNode.h"
#include "SListIterator.h"

// ...

---

SListIterator.h:

Code:

---

#ifndef SLISTITERATOR_H
#define SLISTITERATOR_H

#include "SLinkedList.h"

---

This is a nontrivial workaround, because both classes rely on the methods of each other, but it's template code so you can't put the implementation in .cpp files. I suggest this...

• File SList_declarations.h contains the declarations (no implementation) for SLinkedList and SListIterator.
• File SListIterator.h is written as an implementation for the SListIterator methods, all inline and includes SList_declarations.h and SLinkedList.h
• File SLinkedList.h is written as an implementation for the SListIterator methods, all inline, and includes SList_declarations.h and SListIterator.h

Thanks for the responses. It was too difficult for me to get two files talking to each other, so I combined both classes in one file, added a forward declarion, and it compiled fine. I don't know if its bad practice or not, but hey, I'm trying to learn data structures right now. I'll try what you suggested later again. Thanks for the help.

By the way, this outputs 10, 20, 30 then crashes. With the code above, any idea why? It seems to keep going and then says nothing is there.

Code:

---

#include <iostream> 
#include "Console.h" 
#include "SLinkedList.h"

int main()
{   
        X3D::SLinkedList<int> list;
        list.Append(10);
        list.Append(20);
        list.Append(30);

        X3D::SListIterator<int> itr = list.GetIterator();

        for (itr.Start(); itr.Valid(); itr.Forth())
        {
                wl("Item: " << itr.Item());  // output the item value
        }

        itr.Start();  // resets the iterator

        X3D::Console::Pause();
        return 0;
}

---

There is absolutely nothing wrong with putting closely related classes like this in the same header.

Okay, thanks for letting me know.

Since you added the forward declaration, you can easily separate them into separate files if you'd like to do that. In this case I would think either way is fine.

Okay.

I'm still wondering why the for loop keeps going. It could be the forth() method perhaps.

Edit: ah ha, it's not the for loop but the destructor. I wonder what would be causing it. It's pointing at the first statement within the while loop.

Code:

---

                ~SLinkedList()
                {
                        SListNode<Datatype> *itr = m_head;
                        SListNode<Datatype> *next;

                        while (itr != 0)
                        {
                                // save the pointer to the next node
                                next = itr->m_next;
                                // delete the current node
                                delete itr;
                                // make the next node the current node
                                itr = next;
                        }
                }

---

Edit: I did some horrible testing solutions but I wrote this at the end of the while loop:
std::ofstream out("test", std::ios::out | std::ios::app);
out << next->m_data << std::endl;
out.close();

It is outputing this:
20
30

So, I'm assuming it's off by one somewhere in this.

> // have the new node point to the next node.
> newNode->m_next = m_next;
I would make this:

Code:

---

                        newNode->m_next = 0;

---

Code:

---

>                void Append(Datatype data)
>                {
>                        if (m_head == 0)
>                        {
>                                m_head = m_tail = new SListNode<Datatype>;
>                                m_head->m_data = data;
>                        }

---

Here you need to set the next member to NULL, or have make an SListNode constructor to do it for you:

Code:

---

>                                m_head->m_next = 0;

---

That's getting there. I didn't get any crashes this time around.

I was expecting:
10
20
30

Instead, I got:
0
20
30

I'll keep looking around.

Edit:
Okay, it works now.

m_head = m_tail = new SListNode<Datatype>;
m_head->m_data = data;

If the head is null, it is creating a new node. To put 0 where data is would stop the real data from being stored. That is why I was getting 0 back.

Thanks for the help everyone.

>out << next->m_data << std::endl;
Well, you're outputting next, so I can see why you'd get:
20
30
I would think you'd want:
out << itr->m_data << std::endl;

Unless you're talking about what it outputs in main().

Quote:

---

Originally Posted by philvaira

Edit:
Okay, it works now.

m_head = m_tail = new SListNode<Datatype>;
m_head->m_data = data;

If the head is null, it is creating a new node. To put 0 where data is would stop the real data from being stored. That is why I was getting 0 back.

Thanks for the help everyone.

---

I could be wrong, but it seems like you would need this:
m_head = m_tail = new SListNode<Datatype>;
m_head->m_data = data;
m_head->m_next = 0;

That's because your Forth function is wrong. Pay attention to the variable names used.

>That's because your Forth function is wrong.
Yeah, you're right. In fact I had to stare at it for a minute before I saw it.