Thread: Problem with creating a singly linked list

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    72

    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

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Looks like you have a recursive include. Perhaps one of those should be a forward declaration.

  3. #3
    Registered User
    Join Date
    Apr 2004
    Posts
    72
    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.

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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
    Callou collei we'll code the way
    Of prime numbers and pings!

  6. #6
    Registered User
    Join Date
    Apr 2004
    Posts
    72
    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;
    }
    Last edited by philvaira; 07-31-2007 at 01:14 PM.

  7. #7
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    There is absolutely nothing wrong with putting closely related classes like this in the same header.
    Callou collei we'll code the way
    Of prime numbers and pings!

  8. #8
    Registered User
    Join Date
    Apr 2004
    Posts
    72
    Okay, thanks for letting me know.

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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.

  10. #10
    Registered User
    Join Date
    Apr 2004
    Posts
    72
    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:fstream out("test", std::ios:ut | 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.
    Last edited by philvaira; 07-31-2007 at 02:45 PM.

  11. #11
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > // 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;

  12. #12
    Registered User
    Join Date
    Apr 2004
    Posts
    72
    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.
    Last edited by philvaira; 07-31-2007 at 03:48 PM.

  13. #13
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >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().
    Last edited by swoopy; 07-31-2007 at 03:54 PM.

  14. #14
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Quote Originally Posted by philvaira View Post
    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;

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    That's because your Forth function is wrong. Pay attention to the variable names used.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. I need help on this particular Linked List problem
    By sangken in forum C Programming
    Replies: 11
    Last Post: 08-06-2006, 12:26 AM
  3. Linked list problem
    By mr_glass in forum C Programming
    Replies: 4
    Last Post: 03-07-2006, 02:12 AM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM