Solved

Iteraotr of the Linked-List

Posted on 2003-11-29
11
380 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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
@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
Comment Utility
@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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 9

Expert Comment

by:tinchos
Comment Utility
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
Comment Utility
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
Comment Utility
@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
Comment Utility
@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
Comment Utility
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
Comment Utility
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

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…
Here is a helpful source code for C++ Builder programmers that allows you to manage and manipulate HTML content from C++ code, while also handling HTML events like onclick, onmouseover, ... Some objects defined and used in this source include: …
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 use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

762 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

13 Experts available now in Live!

Get 1:1 Help Now