Going Through A Priority Queue Using Singly Linked List

[fibbo]

I just cant get my head around it.

Is there another way going through a singly linked list without using some kind of helper function? The header file wants me to implement:

size_t priority_queue::size() {
/* code here */
}

Now I just could create a helper function that has a node as parameter and as long as node->get_next() != 0 I recursively call the helper and add 1 to a counter.
But is there actually a way to get through a singly linked list without a helper function?

I hope I was clear enough.

[Narue]

I think you're expecting us to be psychic. Can you provide a little context here instead of starting somewhere in the middle?

[fibbo]

Sorry for being unclear :)

#ifndef PRIORITY_QUEUE_HPP
#define PRIORITY_QUEUE_HPP

#include <vector>
#include "node.hpp"


class priority_queue
{
public:
    priority_queue();
    
	void insert(node*);
	void insert_helper(node* root_, node* insert); // I added this one
	node* pop();
	
	size_t size() const;
	size_t size_helper(node* c) const; //I added this one too

private:
	node* _root;
};

#endif

and node looks the following:

#ifndef NODE_HPP
#define NODE_HPP

#include <cstdlib>

class node
{
private:
	int _priority;
	node* _next;

public:
	node(int priority);

	int get_priority() const;

	node* get_next();
	void set_next(node*);
};

#endif

So if I want the size of this list I check if root is 0, if not I have 1 element, then I check if _root->get_next() is 0, if not I got 2 elements. Now is there a way to go through the whole list without using a helper function with a node parameter (which gets called as long as node_->get_next() != 0).

[Narue]

You shouldn't need a helper with this interface unless the algorithm is recursive. If it's recursive, a helper that takes the current node as an argument is the cleanest solution. In terms of the size member function, it's as simple as a loop (no helper or recursion needed):

size_t priority_queue::size() const
{
    if (_root == 0)
        return 0;

    node *it = _root;
    size_t n = 1;

    while (it->get_next() != 0) {
        it = it->get_next();
        ++n;
    }

    return n;
}

I'm strongly against using recursion for linear problems, so I'd recommend against using recursion in a linked list even if it weren't silly. ;)

[fibbo]

thats exactly what I was looking for. Thank you!
Also thanks for the hint with the linearity ;)

fibbo