Solved

Iteraotr of the Linked-List

Posted on 2003-11-29
11
383 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
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

Question has a verified solution.

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

Suggested Solutions

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

808 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