+ Reply to Thread
Results 1 to 2 of 2

Thread: Linked List in C++

  1. #1
    Junior Member
    Join Date
    Jun 2012
    Posts
    13

    Linked List in C++

    I've just started 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.

    Code:
    #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?

  2. #2
    Junior Member
    Join Date
    Jun 2012
    Posts
    13
    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 :

    Code:
    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
    //...
    };

+ Reply to Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts