Traversing a non-STL linked-list in C++, possible?

Let's say I'm using a non-standard linked-list class, List.h. This class is functioning, template'd and has the typical features of add/remove to front and add/remove to back, isEmpty(), etc.

This list does not have any begin() and end() functionality. Also, does a linked-list class have to include iterator functionality? Or is that something I can create on my own when I create a new List?

I'm used to working with STL, so I would usually use this code:

typedef vector<OBJECT>::iterator QuoteIt;
for(QuoteIt i = deposits.begin(); i != deposits.end(); ++i)

Anyway, lets say I create a new "List".

List<int>deposits;

or even a List of Objects

List<OBJECT>deposits;

So let's say I addToBack() 20 different integers, so that creates the appropriate # of new nodes.

Now, how can I traverse this list so I can find a sum of all these ints? Is that possible, or does my current functionality prevent that? I would have to implement some sort of iterator to my List Class?

Now I know I could keep an outside variable, every time I do an addToB开发者_StackOverflowack() call to keep track of my sums. However, I want the code to be compatible with Lists of Objects as well. (I want to be able to search one value in a node, and retrieve another value in the same node eventually)

I'm so used to working with stl::list and creating a for loop with iterators, I really dont' know how to get this working with other classes.

btw here is the code for List():

template<class NODETYPE>
class List{

public:
List();
~List();
void insertAtFront(const NODETYPE &);
void insertAtBack(const NODETYPE  &);
bool removeFromFront( NODETYPE &);
bool removeFromBack( NODETYPE &);
bool isEmpty() const;

private:
ListNode< NODETYPE > *firstPtr; //pointer to first node
ListNode< NODETYPE > *lastPtr;
//Function to allocate a new node
ListNode< NODETYPE > *getNewNode ( const NODETYPE &);

};
//default constructor
template <class NODETYPE>
List< NODETYPE > ::List()
:  firstPtr(0),
   lastPtr(0)
{
cout<<"Creating Nodes! \n\n!"<<endl;
}
//deconstructor
template <class NODETYPE>
List<NODETYPE>::~List(){
    if(!isEmpty() ){
        cout<<"Destroying nodes!"<<endl;
        ListNode<NODETYPE> *currentPtr=firstPtr;
        ListNode<NODETYPE> *tempPtr;

        while( currentPtr !=0){
            tempPtr = currentPtr;
            currentPtr=currentPtr->nextPtr;
            delete tempPtr;
        }
    }
cout<<"All nodes destroyed! \n\n";
}

template <class NODETYPE>
bool List <NODETYPE>::removeFromFront( NODETYPE & value){
if ( isEmpty() )
    return false;
else{
    ListNode<NODETYPE> *tempPtr = firstPtr;

    if (firstPtr== lastPtr)
        firstPtr=lastPtr = 0;
    else
        firstPtr=firstPtr->nextPtr;

    value = tempPtr->data;
    delete tempPtr;

    return true;
}    
}     
template <class NODETYPE>
bool List<NODETYPE>::removeFromBack(NODETYPE &value)
{
    if (isEmpty())
        return false;
    else{
        ListNode< NODETYPE> *tempPtr = lastPtr;
        if( firstPtr == lastPtr)
            firstPtr = lastPtr = 0;
        else{
            ListNode<NODETYPE> *currentPtr=firstPtr;

            //Finds second to last element
            while(currentPtr->nextPtr !=lastPtr)
                currentPtr=currentPtr->nextPtr;

            lastPtr = currentPtr;
            currentPtr->nextPtr=0;
        }

        value = tempPtr->data;
        delete tempPtr;

        return true;
    }
}

//Checks to see if list is empty
template< class NODETYPE>
bool List< NODETYPE >::isEmpty() const{
return firstPtr == 0;
}
//returns a pointer to newly created Node
template<class NODETYPE>
ListNode<NODETYPE> *List<NODETYPE>::getNewNode(const NODETYPE &value){
return new ListNode<NODETYPE>(value);
}

In response to:

Now, how can I traverse this list so I can find a sum of all these ints? Is that possible, or does my current functionality prevent that? I would have to implement some sort of iterator to my List Class?

You need to implement a way to iterate over your list that does not (as a side-effect) destroy your list.

In response to:

Now, how can I traverse this list so I can find a sum of all these ints? Is that possible, or does my current functionality prevent that? I would have to implement some sort of iterator to my List Class?

No matter how you design a linked list, you must have some sort of pointer to the beginning of the list, and you have to have a way of knowing when you are at the end (e.g. when "next" is null, or by having a pointer to the end). By exposing those data one way or another, you can always set up a list traversal:

1. Start at the beginning. (In your case, get a hold of firstPtr.)
2. If you are not at the end, move to the next element. (In your case, get ->nextPtr.)

Using that pattern to accumulate a value as you visit each element you should be able to handle your task with ease.

If your list does not give you public access to its beginning, then it is certainly not a general-purpose list!

You can approach this many ways. You can either choose to create your own iterator or give public access to the list's head.

Option 1 is compatible with stl lists so you might want to go that route. An iterator is essentially a ptr that overrides the inc and dec operators to go to the next or previous position in the list.

If you studied basic data structures at all, you would know that traversing a list is trivial.

Node<type> t = head;
while (t != NULL)
{
   // process node here
   t = t->next;
}

The code can differ depending on if you use dummy nodes at all.

Since there is no functionality to just get the node without removing it from the list, you can't simply make an "add-on" iterator without changing the List class. The least you would need to do is to either

• friend the external ListIterator class
• friend free begin and end functions
• add begin and end functions to the List class

Without any of those three, you can't achieve what you want.

Your list seems to have 2 ways of iterating it (forwards and backwards)

List<int>deposits;
.. add stuff:

int o;
int sum = 0;
while(deposits.removeFromFront(o)) {
  sum+=o;
}

The bad thing though, is that iterating it, you also destroy the list, you could provide public accessors to List::firstPtr and ListNode::nextPtr in which case you could do:

List<int>deposits;
.. add stuff:


int sum = 0;

for(ListNode<int> *ptr = deposits.firstPtr; ptr ; ptr = ptr->nextPtr) 
  sum+=ptr->data;

However, use an existing STL container if you can.