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.

6 Years
Discussion Span
Last Post by fibbo

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


Sorry for being unclear :)


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

class 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

	node* _root;


and node looks the following:

#ifndef NODE_HPP
#define NODE_HPP

#include <cstdlib>

class node
	int _priority;
	node* _next;

	node(int priority);

	int get_priority() const;

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


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


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();

    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. ;)


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


This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.