Iteraotr of the Linked-List

To C++ experts,

    I am still struggling with the Linked-List ...... Here is the question I encountered this time :

Say I already have the Linked-list template which has the ListNode and Iterator as inner classes. Now I have the main program :
--------------------------------
#include <iostream>
#include <string>
#include "List_tp.h"

int main()
{
  List<string> Friends_Roommate, Friends_Sports ;

  Friends_Roommate.push_back("Natali") ;
  Friends_Roommate.push_back("Judy") ;
  Friends_Roommate.push_back("Amanda") ;

  Friends_Sports.push_back("Richard") ;
  Friends_Sports.push_back("Andy") ;
  Friends_Sports.push_front("Hermann") ;

  Friends_Roommate.print() ;
  Friends_Sports.print() ;

  return 0 ;
}
------------------------------------------------------
Now, how do I declare an Iterator which points to "Richard" ? so that I can insert "Thomas" before "Richard" ......

Thanks very much !!!

meow.
LVL 1
meow00Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

tinchosCommented:
Sorry Meow

What is List_tp.h, how is List defined? as an stl List?

Tincho
0
tinchosCommented:
meow00,

In case you're using an stl list this is the way to insert "Pepe" before "Richard"



#include <iostream>
#include <string>
#include <list>

using namespace std;

int main()
{
      list<string> Friends_Roommate, Friends_Sports ;

      Friends_Roommate.push_back("Natali") ;
      Friends_Roommate.push_back("Judy") ;
      Friends_Roommate.push_back("Amanda") ;

      Friends_Sports.push_back("Richard") ;
      Friends_Sports.push_back("Andy") ;
      Friends_Sports.push_front("Hermann") ;

      list<string>::iterator it;

      for( it = Friends_Sports.begin(); it != Friends_Sports.end(); ++it )
      {
            if( *it == "Richard" )
            {
                  // Insert "Pepe" before "Richard"
                  Friends_Sports.insert( it, "Pepe" );
            }
      }

      for( it = Friends_Sports.begin(); it != Friends_Sports.end(); ++it )
            cout << *it << endl;

      system("PAUSE");

      return 0 ;
}
0
meow00Author Commented:
Hi,

   Sorry ..... I am not quite sure whether the <list> in the STL containing iterator and listnode .... so I include a template
------------------------------------
template <class T>
class List
{ protected :
    class Node
    { blah blah
    } ;

    Node* _ ; // dummy node
    int _size ;
  public :
    class Iterator
    { blah blah
    } ;
   blah blah .......
} ;
--------------------------------------------
  Please give me some suggestions  if there are more elegant ways to do things. Thanks !

meow.
0
Cloud Class® Course: Microsoft Exchange Server

The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

DexstarCommented:
@meow00:

> Now, how do I declare an Iterator which points to "Richard" ? so that I can
> insert "Thomas" before "Richard" ......

Like tinchos said...  It depends on how List works...  It looks similiar to STL, so let's go with that, and you tell me where it doesn't match.  You may have to post your linked list code.

After each insert, your list looked like this:
   Richard
   Richard Andy
   Hermann Richard Andy

So, Richard is now the 2nd element in the list.  Your list class probably has a method for getting an iterator to the beginning of the list (in STL, it's called "begin()").  So, you can do this:
   iterator itr = Friends_Sports.begin();

Then, you can move to the next record by incrementing the iterator (assuming your iterator class supports this!).
   itr++;

Now, you can insert "Thomas".
   Friends_Sports.insert( itr, "Thomas" );

Try that.

Hope That Helps,
Dex*
0
DexstarCommented:
@meow00:

>  Sorry ..... I am not quite sure whether the <list> in the STL containing
> iterator and listnode .... so I include a template

Okay, so you're not using STL, so my example probably won't help you.  I can't re-write it for your template class because you stripped out all the important parts.  Don't cut out the details of the class.  Better yet, if you got it off the web, paste a link so we can review the code and help you.

Dex*
0
tinchosCommented:
Dexstar,

As Dexstar said and his post shows, like mine

that's the way to use with the stl list

I'm not quite sure how your list works
and without that I'm not sure if we can really help you

Tincho
0
meow00Author Commented:
Hi,
  The following is the template I used. Then I couldn't do :
  Iterator it ; or
  List::Iterator it ; or
  List<string>::Iterator it ;
  none of them works .......
 
  BTY, is that true that there is no way I can point the iterator "directorly" to "Richard" ? (Say if I know Thomas later and decided to insert "Thomas" right in front of "Richard" .....)

  Thanks very much !
  ---------------------------------------
template <class T>
class List
{ protected :
    class Node
    { public :
        Node(const T& data = T(), Node* prev =0, Node* next=0):
        _data(data), _prev(prev), _next(next){
           if (_prev==0) _prev = this ;
           if (_next==0) _next = this ;
        }

        T _data ;
        Node *_prev, *_next ;
    } ; //Inner Class Node

    Node* _ ; // dummy node
    int _size ;

  public :
    class Iterator
    {
      friend class List ;
     public :
      Iterator(Node* p) : _(p){}
      T& operator*() {return _-> _data ;}
      void operator=(const Iterator& it) {_= it._ ;}
      bool operator==(const Iterator& it) {return _==it._ ;}
      bool operator!=(const Iterator& it) {return _!=it._ ;}
      Iterator operator++(int){
          Iterator it(_) ;
          _ = _-> _next ;
          return it ;
      }
      Iterator& operator++(){
          _ = _-> _next ;
          return *this ;}

      Iterator operator--(int){
          Iterator it(_) ;
          _ = _-> _prev ;
          return it ;
      }
      Iterator& operator--(){
          _ = _-> _prev ; return *this ;}

    protected :
      List<T>::Node* _ ;
   } ;  //Inner Class Iterator

   List() ;
   List(const List&) ;
   List(int) ;
   List(int, const T&) ;
   List(Iterator&, Iterator&) ;
   ~List() ;

   int size() const ;
   bool empty() const ;
   T& front() const ;
   T& back() const ;
   Iterator begin() ;
   Iterator end() ;
   void push_front(const T&) ;
   void push_back(const T&) ;
   void pop_front() ;
   void pop_back() ;

   Iterator insert(Iterator&, const T&) ;
   Iterator insert(Iterator&, int, const T&) ;

   void erase(Iterator&) ;
   void erase(Iterator&, Iterator&) ;
   void clear() ;
   void print() ;
   void print_cir() ;
   void splice(Iterator, List&, Iterator) ;

} ;

template <class T>
List<T>::List(): _size(0)
{ _ = new Node() ;
}

template <class T>
List<T>::List(const List& l) : _size(l._size)
{ _ = new Node() ;
  Node* pp = _ ;
  for(Node* p=l._->_next ; p != l._ ; p = p->_next, pp=pp->_next){
   pp->_next = pp->_next ->_prev = new Node(p->_data, _ , pp);}
}

template <class T>
List<T>::List(int n) : _size(n)
{  _ = new Node() ;
   Node* p = _ ;
   for(int i=0; i<n; i++) p = p->_prev = new Node(T(),_,p) ;
   _ ->_next = p ;
}

template <class T>
List<T>::List(int n, const T& t): _size(n)
{ _ = new Node() ;
  Node* p = _ ;
  for(int i=0; i<n; i++) p = p->_prev = new Node(t,_,p) ;
   _ ->_next = p ;
}
template <class T>
List<T>::List(Iterator& it1, Iterator& it2) : _size(0)
{ _ = new Node() ;
  Node* pp = _ ;
  for(Node* p = it1._ ; p!= it2._ ; p = p->_next, pp=pp->_next)
  { pp-> _next = new Node(p->_data, pp, _) ;
    ++_size ;
  }
  _->_prev = pp ;
}

template <class T>
List<T>::~List()
{ Node* p = _->_next ;
  while (p!= _)
  { Node* pp= p -> _next ;
    delete p ;
    p = pp ;
  }
  delete _ ;
}

template <class T>
int List<T>::size() const
{  return _size ;
}

template <class T>
bool List<T>::empty() const
{  return _size == 0 ;
}

template <class T>
T& List<T>::front() const
{  return _->_next->_data ;
}

template <class T>
T& List<T>::back() const
{  return _->_prev->_data ;
}

template <class T>
List<T>::Iterator List<T>::begin()
{   return Iterator(_->_next) ;
}

template <class T>
List<T>::Iterator List<T>::end()
{   return Iterator(_) ;
}

template <class T>
void List<T>::push_front(const T& x)
{  _-> _next = _-> _next -> _prev = new Node(x,_,_-> _next) ;
   ++_size ;
}

template < class T>
void List<T>::push_back(const T& x)
{  _-> _prev = _-> _prev -> _next = new Node(x, _-> _prev, _) ;
   ++_size ;
}

template <class T>
void List<T>::pop_front()
{  Node* p = _-> _next ;
   _->_next = p-> _next ;
   p->_next->_prev =_ ;
   delete p ;
   --_size ;
}

template <class T>
void List<T>::pop_back()
{  Node* p = _-> _prev ;
   _-> _prev = p->_prev ;
   p-> _prev -> _next = _ ;
   delete p ;
   --_size ;
}

template <class T>
List<T>::Iterator List<T>::insert(Iterator& it, const T& x)
{   it._->_prev = it._ -> _prev -> _next = new Node(x, it._->_prev, it._) ;
    it._ = it._ -> _prev ;
    ++_size ;
}

template <class T>
List<T>::Iterator List<T>::insert(Iterator& it, int n, const T& x)
{  Node* p = it._, *q = p-> _prev ;
   for(int i=0; i< n; i++) p=p->_prev = new Node(x,p,q) ;
   it._ = it._ -> _prev = q-> _next = p ;
   _size += n ;
}

template <class T>
void List<T>::erase(Iterator& it)
{  if(_size==0) return ;
   Node* p = it._ ;
   p-> _prev -> _next = p-> _next ;
   p-> _next -> _prev = p-> _prev ;
   it._ = p-> _next ;
   delete p ;
   --size ;
}

template <class T>
void List<T>::erase(Iterator& it1, Iterator& it2)
{  it1._-> _prev -> _next = it2._ ;
   it2._-> _prev = it1._ -> _prev ;
   Node* p = it1._ -> _next ;
   while (it1._ != it2._)
    { delete it1._ ;
      it1._ = p ;
      p = p -> _next ;
      --size ;
    }
}

template <class T>
void List<T>::clear()
{  Node* p =_, *q = p->_next ;
   while (q!=p)
   {  p-> _next = q-> _next ;
      q-> _next -> _prev = p ;
      delete q ;
      q = p -> _next ;
   }
   _size = 0 ;
}

template <class T>
void List<T>::print()
{  Node* p=_ ; Node* q= p-> _next ;
   while(q!=p){
     cout << q-> _data << endl ;
     q= q-> _next;}
}

template <class T>
void List<T>::splice(Iterator it1, List& l, Iterator it2)
{  Node* p = it1._, *pp = it1._ -> _prev, *q = it2._ ;
   p-> _prev = p-> _next =q ;
   q-> _prev -> _next = q -> _next ;
   q-> _next -> _prev = q -> _prev ;
   q-> _prev = pp ;
   q-> _next = p ;
   ++_size ;
   --l._size ;
}




0
DexstarCommented:
@meow00:

Okay, the following code should work for you.  If it doesn't, please post the errors or invalid output that you get.

Dex*
---

#include <iostream>
#include <string>
#include "List_tp.h"

int main()
{
  List<string> Friends_Roommate, Friends_Sports ;
  List<string>::Iterator itr;

  Friends_Roommate.push_back("Natali") ;
  Friends_Roommate.push_back("Judy") ;
  Friends_Roommate.push_back("Amanda") ;

  Friends_Sports.push_back("Richard") ;
  Friends_Sports.push_back("Andy") ;
  Friends_Sports.push_front("Hermann") ;

  itr = Friends_Sports.begin();
  itr++;
  Friends_Sports.insert( itr, "Thomas" );

  Friends_Roommate.print() ;
  Friends_Sports.print() ;

  return 0 ;
}
0
DexstarCommented:
@meow00:

> is that true that there is no way I can point the iterator "directorly" to "Richard" ?

Yes, this is true.  The list class only remembers the location of the beginning (and sometimes the end) node of the list.  To get to any other node, it has to move through each entry, one at a time.

That is why you shouldn't use a linked list when you need random access to the elements.

Dex*
0
meow00Author Commented:
Hi Dex*,

  The above code does not work for me. Here is the error message I got :
where line 9 in the main.C
is "List<string>::Iterator itr;" (all on Cray machine).

   I am not quite sure what I have missed .....?!?

   Thanks very much !

meow.
  ---------------------------------------
main.C: In function `int main()':
main.C:9: no matching function for call to `List<basic_string<char,string_char_t
raits<char>,__default_alloc_template<false,0> > >::Iterator::Iterator ()'
List_tp.h:24: candidates are: List<basic_string<char,string_char_traits<char>,__
default_alloc_template<false,0> > >::Iterator::Iterator(List<basic_string<char,s
tring_char_traits<char>,__default_alloc_template<false,0> > >::Node *)
List_tp.h:48:                 List<basic_string<char,string_char_traits<char>,__
default_alloc_template<false,0> > >::Iterator::Iterator(const List<basic_string<
char,string_char_traits<char>,__default_alloc_template<false,0> > >::Iterator &)
---------------------------------
0
DexstarCommented:
REMOVE line 9 all completely, and then change this line:
     itr = Friends_Sports.begin();
to this:
     List<string>::Iterator itr = Friends_Sports.begin();


[You could also Changed line 9 to this:  
     List<string>::Iterator itr(NULL);

But I think it is better to not initialize an iterator to be NULL.  Better to always keep it valid...]

Dex*
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Editors IDEs

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.