Member Avatar for 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.

  • 2 Contributors
  • 4 Replies
  • 387 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by fibbo

Dani AI

Generated

Nice thread — , your instinct to walk the list rather than force recursion is right, and 's iterative approach is the usual, practical choice for a singly linked list. Recursion for a linear traversal only adds call/stack overhead and risks stack overflow on long lists, so prefer iteration unless you have a strong reason to be recursive.

A few practical points that are easy to miss in this exact setup:

  • const correctness: your size() is declared const. If node::get_next() is non-const your size() const will not compile. Provide a const accessor (or overloads) such as node* get_next() and const node* get_next() const, or at minimum make the getter itself const. That keeps traversal usable from const member functions.
  • O(1) alternative: if size() will be called often, keep a size_t _size member in priority_queue and update it on every insert/pop. This avoids an O(n) traversal every time; just be careful to update _size only after a successful insert/remove and handle copy/move/destructor semantics.
  • ownership and safety: decide whether pop() transfers ownership or the queue deletes nodes. Document it. Modernize where sensible — use nullptr instead of 0, initialize _root in the constructor, and consider std::unique_ptr for node ownership to avoid leaks (with next as a smart pointer the destructor work disappears, but the API design changes slightly).

Small design helpers that reduce edge cases: a dummy/sentinel head simplifies insert/pop logic, and keeping a tail pointer (or a cached size) can give O(1) operations where needed. These changes keep the implementation simple, efficient, and robust without relying on recursion.

Recommended Answers

All 4 Replies

Member Avatar for Narue

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

Member Avatar for 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).

Member Avatar for 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. ;)

Member Avatar for fibbo

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

fibbo

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.