Checking if a linked list is circular with smart pointers

[Paul]

Checking if a linked list is circular is a standard problem. My attempted solution is below. Could anyone advise on a smart pointer approach using unique_ptr or shared_ptr? Also, please let me know if there are any problems with this approach. I know it leaks memory but I'm looking to a smart-pointer implementation to fix that.

Thanks a lot, Paul.

#include <cstdio>

struct Node
{
int data;
Node* next;

};

// A fast pointer and a slow pointer are both initiated at the head.
// Circular if the slow pointer is ever ahead of the fast pointer.
bool isCycle(Node* head)
{
Node* slowPointer = head;
Node* fastPointer = head;

while(fastPointer && fastPointer->next && fastPointer->next->next)
{
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;

if(fastPointer == slowPointer || fastPointer->next == slowPointer)
return true;
}

return false;
}

// Test against the expected results.
void testCycle(Node* head, bool expected)
{
printf(isCycle(head) == expected ? "Results as expected\n" : "This test case failed\n");
}

// Set up tests for small numbers of nodes
void smallTests()
{
Node* emptyList = nullptr;
testCycle(emptyList, false);

Node* List1 = new Node;
Node* ListCircular2 = new Node;
Node* ListNonCircular2 = new Node;
Node* ListCircular3 = new Node;
Node* ListNonCircular3 = new Node;

List1->next = nullptr;
List1->data = 1;
testCycle(List1, false);

ListCircular2 = List1;
ListCircular2 -> next = ListCircular2;
testCycle(ListCircular2, true);

ListNonCircular2 = ListCircular2;
ListNonCircular2->next = new Node;
ListNonCircular2->next->data = 2;
ListNonCircular2->next->next = nullptr;
testCycle(ListNonCircular2, false);

ListNonCircular3 = ListNonCircular2;
ListNonCircular3->next->next = new Node;
ListNonCircular3->next->next->data = 3;
ListNonCircular3->next->next->next = nullptr;
testCycle(ListNonCircular3, false);

ListCircular3 = ListNonCircular3;
ListCircular3->next->next->next = ListCircular3;
testCycle(ListCircular3, true);

}

int main()
{
smallTests();
return 0;
}

[Öö Tiib]

On Thursday, 25 June 2015 13:03:22 UTC+3, Paul wrote:
> Checking if a linked list is circular is a standard problem.

Linked list is *rather* rarely used container in practice.

> My attempted solution is below. Could anyone advise
> on a smart pointer approach using unique_ptr or shared_ptr?

Navigation in containers goes with *iterators* in C++.
Do *not* use smart pointer for navigating around in
container, regardless if it is based on smart pointers.
Smart pointer is terrible for navigation.

> Also, please let me know if there are any problems with
> this approach.

I don't see any problems in the algorithm.

> I know it leaks memory but I'm looking to a
> smart-pointer implementation to fix that.

You can use raw pointers like crappy substitution
to iterators (assuming list is made with smart pointers)
No much rewrite needed to your algorithm:

Node* slowIterator = head.get();
...
slowIterator = slowIterator->next.get();
...
if ( /* ... */ fastIterator->next.get() == slowIterator )
...

[Paul]

Thanks Oo. But isn't it a problem to have new without delete? I thought that was a memory leak? Thanks.

Paul

[Öö Tiib]

Leaks were in your 'smallTests' function. It was indeed crap.
That you can get fixed by using smart pointer for 'next'.

I meant your 'isCycle' that did neither 'new' nor 'delete' and
so you should keep. Iterators should not manage the object
they navigate. Smart pointers (that automatically manage)
are therefore very bad iterators.

[Öö Tiib]

Additional warning ... making reference cycle with smart
pointers prevents these from managing the memory properly.

It is because 'unique_ptr' denotes private ownership and
'shared_ptr' denotes shared ownership. Circular ownership
does not make sense and so these are not designed to
work in such a situation. So if you make cycles with those
then you should also break the cycles manually (but better
just avoid it).

[Paul]

I'm sorry but I'm not sure how to proceed to get the whole thing (including the test) to work. Should I simply rewrite the Node class so that next is a std::shared_ptr<Node>?

Many thanks
Paul

[Öö Tiib]

It is lot better idea to add constructors and destructors to
'Node' to see when those are called.
Then rewrite your 'smallTests' in a way that it works and
does not leak 'Node's (nor does delete 'Node's twice) with
raw pointers.

Then save it and then try to achieve same with smart pointer
as 'next' in 'Node'. Cycles are slightly tricky to deal with smart
pointers and so you will find out what is better ... if to use
fully manual management with raw pointers or to use smart
pointers and compensate the shortcoming.

[Christopher Pisz]

Why are you creating your own list data stucture? Is this an academic
exercise?



--
I have chosen to troll filter/ignore all subthreads containing the
words: "Rick C. Hodgins", "Flibble", and "Islam"
So, I won't be able to see or respond to any such messages
---

[Paul]

Yes, it's an academic exercise. But I'm self-learning. I'm not enrolled in any course.

Paul

[Paul]

This is my revised code which uses smart pointers. I also coded another direct way of testing for cycles by seeing if the pointers repeat. Does this seem ok? Thanks a lot for your feedback.

#include <cstdio>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <memory>

struct Node
{
int data;
std::shared_ptr<Node> next;

};

// A fast pointer and a slow pointer are both initiated at the head.
// Circular if the slow pointer is ever ahead of the fast pointer.

bool isCycle(std::shared_ptr<Node> head)
{
auto slowPointer = head;
auto fastPointer = head;

while(fastPointer && fastPointer->next && fastPointer->next->next)
{
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;

if(fastPointer == slowPointer || fastPointer->next == slowPointer)
return true;
}

return false;
}

// A direct algorithm to tell if a cycle is present by seeing if a pointer address repeats.
bool isCycleDirect(std::shared_ptr<Node> head)
{
std::unordered_set<std::shared_ptr<Node>> nodePointers;

while(head)
{
// If trying to insert something already inserted, then must contain cycles.
if(nodePointers.find(head) != nodePointers.end())
return true;

nodePointers.insert(head);
head = head->next;

}

return false;
}

// Test against the expected results.

void testCycle(std::shared_ptr<Node> head, bool expected)

{
printf(isCycle(head) == expected ? "Results as expected\n" : "This test case failed\n");
}

// Set up tests for small numbers of nodes
void smallTests()
{

std::shared_ptr<Node> emptyList;
testCycle(emptyList, false);

std::shared_ptr<Node> List1(new Node);
std::shared_ptr<Node>ListCircular2(new Node);
std::shared_ptr<Node>ListNonCircular2(new Node);
std::shared_ptr<Node>ListCircular3(new Node);
std::shared_ptr<Node>ListNonCircular3(new Node);

List1->next = nullptr;
List1->data = 1;
testCycle(List1, false);

ListCircular2 = List1;
ListCircular2 -> next = ListCircular2;
testCycle(ListCircular2, true);

ListNonCircular2 = ListCircular2;

ListNonCircular2->next = std::shared_ptr<Node>(new Node);

ListNonCircular2->next->data = 2;
ListNonCircular2->next->next = nullptr;
testCycle(ListNonCircular2, false);

ListNonCircular3 = ListNonCircular2;

ListNonCircular3->next->next = std::shared_ptr<Node>(new Node);

ListNonCircular3->next->next->data = 3;
ListNonCircular3->next->next->next = nullptr;
testCycle(ListNonCircular3, false);

ListCircular3 = ListNonCircular3;
ListCircular3->next->next->next = ListCircular3;
testCycle(ListCircular3, true);

}

int main()
{
smallTests();
return 0;

}

Paul

[Öö Tiib]

You decided to use smart pointers as iterators in 'isCycle'. I already did
try to explain why smart pointers are terrible iterators. If you don't
make or accustom a class for iterator then raw pointer is still better
than smart pointer.

Your 'isCycleDirect' seems quite expensive to make 'unordered_set' of
whole list. You should perhaps try and compare the two with list of
million of entries.

Your 'smallTests' is still broken in sense that it leaks memory.

[Christopher Pisz]

I didn't examine the code too closely, but I don't really see any reason
to use shared_ptr. Just use a raw pointer.

Consider these things :

The pointers should be private to the list class and its nodes, no user
should ever see them.

shared pointers are for when ownership of the object is going to be
"shared", which should not be the case for objects in the list

ownership of the stored elements should not be shared. The list should
own them and maintain them.

When access to an element from the outside is requested, a copy should
be made. Thus the need to a constructor and copy constructor on any type
being contained.

raw pointer is faster (and simpler) than shared pointer.

It's easy enough to identify the operations that require a new or delete
when the list completely maintains itself.

[Paul]

Yes, I did understand your advice but some companies seem a bit dogmatic about always using smart pointers and I'm trying to learn to please them.

Thanks to all who have taken the time to help me.

Paul

[Christopher Pisz]

"Always use smart pointers" is an ignorant rule and their bug trackers
will show it.

Use raw pointers when it makes sense to use raw pointers.
Use shared_ptr when it makes sense to use shared_ptr.
Use weak_ptr when it makes sense to use weak_ptr.
Use unique_ptr when it makes sense to use unique_ptr.

Those companies are going to spend just as much, if not more, man hours
debugging "why didn't X get released" and circular references, as they
will from people using raw pointers poorly.

It's always some guy that thinks, it is a good idea to use shared_ptrs
like a C# garbage collector.