Solved

Iteraotr of the Linked-List

Posted on 2003-11-29
11
381 Views
Last Modified: 2013-12-14
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.
0
Comment
Question by:meow00
  • 5
  • 3
  • 3
11 Comments
 
LVL 9

Expert Comment

by:tinchos
ID: 9842943
Sorry Meow

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

Tincho
0
 
LVL 9

Assisted Solution

by:tinchos
tinchos earned 50 total points
ID: 9842965
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
 
LVL 1

Author Comment

by:meow00
ID: 9842978
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
 
LVL 19

Expert Comment

by:Dexstar
ID: 9842980
@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
 
LVL 19

Expert Comment

by:Dexstar
ID: 9842987
@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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 9

Expert Comment

by:tinchos
ID: 9842995
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
 
LVL 1

Author Comment

by:meow00
ID: 9843056
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
 
LVL 19

Expert Comment

by:Dexstar
ID: 9843167
@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
 
LVL 19

Expert Comment

by:Dexstar
ID: 9843174
@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
 
LVL 1

Author Comment

by:meow00
ID: 9843198
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
 
LVL 19

Accepted Solution

by:
Dexstar earned 250 total points
ID: 9843219
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

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now