Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Iteraotr of the Linked-List

Posted on 2003-11-29
11
Medium Priority
?
391 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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 200 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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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
 
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 1000 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

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

Question has a verified solution.

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

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

609 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