C++ Generic Linked List and Iterator

Question

I've just started with learning C++ and I need to write a generic linked list and iterator. This is the code that I wrote (list.h), but I think it is not correct. It does not work and I am not sure that it is generic.

#include <iostream>        
#include <cassert>


using namespace std;        
using namespace ListExceptions;

class List;    
class Iterator;

template<class T>

class Node{    
private:    
   T data;    
   Node* previous;    
   Node* next;    
   friend class List;    
   friend class Iterator;    
public:    
   Node(T element){    
       data = element;    
       previous = NULL;    
       next = NULL;    
   }    
};    

class List{    
private:    
   Node* first;    
   Node* last;    
public:    
   List(){    
       first = NULL;    
       last = NULL;    
   }    
   void pushBack(T element);    
   void insert(Iterator iter, T element);    
   Iterator remove(Iterator i);    
   Iterator find(const Predicate& predicate);    
   void sort(const Compare& comparer);    
   int getSize() const;    
   Iterator begin();    
   Iterator end();    
};    

class Iterator{    
private:    
   Node* position;    
   Node* last;    
   friend class List;    
public:    
   Iterator();    
   void next();    
   T getElement()const;    
   bool equals(Iterator b) const;    
   bool notEquals(Iterator b) const;    
};

If someone can help me?

Wow, that's badly formatted. Can you use the code formatting option. — Steve Walsh
– Steve Walsh, Commented Jun 21, 2011 at 10:12
You need to tell us what doesn't work. Are there error messages? Is the behaviour wrong (and if so, what does it do vs. what you were expecting it do)? Also, if this is homework it should be tagged as such (not sure if it is). — Sven
– Sven, Commented Jun 21, 2011 at 10:13
I'd suggest you to look in to the implementation of std::list class. (mochima.com/tutorials/STL.html) — sarat
– sarat, Commented Jun 21, 2011 at 10:15
@Ozair: If you don't format URLs as code, SO will make links of them automatically. — Björn Pollex
– Björn Pollex, Commented Jun 21, 2011 at 10:28

David Rodríguez - dribeas · Accepted Answer · 2011-06-21 10:20:47Z

5

First thing is that the List and Iterator are non-templated classes, and you probably want to create Lists of a given type. You might consider refactoring the code so that both the Node and the Iterator are internal classes to the List type (it will make things simpler):

template <typename T>
class List {
public:
   typedef T value_type;

   class Iterator;
   struct Node {           // Internal to List<T>, so there will be different
                           // List<T>::Node for each instantiationg type T
                           // But you don't need the extra <T> parameter for List
                           // or Iterator
      value_type data;
      Node* next;
      Node* last;

      friend class List;       // Inside List<T>, List by itself refers to List<T>
      friend class Iterator;
   };
   //...
};

The alternative is a little more complex in code:

template <typename T> class List;
template <typename T> class Iterator;
template <typename T> class Node {
   T data;
   Node * next;
   Node * last;
   friend class List<T>;
   friend class Iterator<T>;
};
template <typename T>
class List {
   Node<T>* first;              // note <T> required
//...
};

answered Jun 21, 2011 at 10:20

David Rodríguez - dribeas

209k23 gold badges304 silver badges497 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Kijewski Over a year ago

@user808176: Please don't ask questions that where answered hundreds of times on SO. Use the search function. (lmgtfy is blacklisted, who knew?)

user808176 Over a year ago

In an allternative Way above when I use Node<T>* and when i have to use T?Thanks a lot!

David Rodríguez - dribeas Over a year ago

@user808176: Difference between iterator and pointer is out of the scope of this question and comments, and would take quite a while. As to when you need to use Template<T> and when Template suffices, you can use the former in all contexts, you can use the later only inside the Template class template definition, i.e. inside the Node<T> definition (and member functions). Using T is not wrong, but it is common to generate typedefs like value_type inside containers.

user808176 Over a year ago

Multiple markers at this line - previous non-function declaration template<class T> class List' - previous declaration of template<class T> class List'

user808176 Over a year ago

This is a problem that I received from the compiler about the next lines: template <typename T> class List; template <typename T> class Iterator;

|

Collectives™ on Stack Overflow

C++ Generic Linked List and Iterator

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related