Recurisve LinkList Problem

[Planet_EN]

Hello, I am studying Data Structures and Algorithms, and I've been ordained by the instructor to make a recursive LinkList ADT. Well, I am almost there but still having certain problems, like I am inserting digits from 0 to 10 in the list and i am getting an extra zero at the end of traversal() function.

Can anyone please help me out, here's the code:


[syntax="cpp"]
#include<iostream>
#include<cstdlib>
#include<cstring>

typedef struct node
{
int data;
node* next;
}*List;

void initialize( List X )
{
X->data = 0;
X->next = NULL;
}

void initialize( List X , List Y )
{
X->data = Y->data;
X->next = Y->next;
}

int count( List X )
{
if( X == 0 ) return 0;
return ( 1 + count( X->next ));
}

void traverse( List L )
{
if( L == 0 )
return;
else
traverse( L->next );
std::cout << L->data << std::ends ;
}

void traverse_reverse( List L )
{
if( L->next == 0 ) return;
std::cout << L->data << std::ends ;
traverse( L->next );
}

void insert( List L , int value )
{
List Temp = new node;
if( Temp == NULL )
std::cerr << "Out of Space" << std::endl;
if( L == NULL )
L = new node;

Temp->data = value;
Temp->next = L->next;
L->next = Temp;
}

void remove( List& L , int value )
{
while( L != 0 && L->data == value )
{
List Tmp = L;
L = L->next;
delete[] Tmp;
}

if( L != 0 ) remove( L->next , value );
}

int rFind( List L , int value )
{
if( L->data != value || L->next == NULL ) return 0;
else
return 1 + rFind( L->next, value );
}

int main()
{
List x = new node;
initialize(x);
for ( int i=1; i<=10;i++ )
insert(x,i);
std::cout << count(x) << std::endl;
traverse(x);
std::cout << std::endl;
traverse_reverse(x);
std::cout << std::endl;
std::cout << rFind(x,11);
return 0;
}
[/syntax]

[Darryl]

You insert numbers 1 - 10. the 0 comes from your Initialize() function, it create a node with the value 0. Then your insert function doesn't preserve the order of the 0.
list = 0 after initialization
list = 0,1 after insert of 1
list = 0,2,1 after insert of 2
...
list = 0, 10,9,8,7,6,5,4,3,2,1 after insert of 10


Now your traversal is actually printing your list in reverse and your reverse_traveral is also printing in reverse but only because you didn't call it recursively, you call the regular traverse instead. If you call it recursively, it will print the list forward.

Ahh 1 more problem in reverse_traverse: if( L->next == 0 ) return; This return causes the last node not to print it's data, so once you fix your reverse_traverse, you will see it leaves off the 1 at the end

ok just found something else. In your remove function you do delete[] Tmp;
delete[] is for deleting arrays not single pointers and it's behavior is undefined. Use just delete tmp;

ok, this is last edit: in your insert function you have a check if the list is null and if so you create the first node. You set the next value to the temp you create but you leave the data member uninitialized. Therefore you 1st node data will be garbage.

I lied, this is last edit. Your find function won't find the last node because you are checking ->next == NULL. So even though there is a value in this node, ->next==NULL will be true and cause your search to end without finding the value. if you switch your or statement around, and check for the node == NULL on the left side of the || it will short circuit the statement preventing your other check from being evaluted using a null pointer.

[Planet_EN]

ok, this is last edit: in your insert function you have a check if the list is null and if so you create the first node. You set the next value to the temp you create but you leave the data member uninitialized. Therefore you 1st node data will be garbage.

I lied, this is last edit. Your find function won't find the last node because you are checking ->next == NULL. So even though there is a value in this node, ->next==NULL will be true and cause your search to end without finding the value. if you switch your or statement around, and check for the node == NULL on the left side of the || it will short circuit the statement preventing your other check from being evaluted using a null pointer.

I am serious dude... I seriously couldnt figure out what you meant in the last paragraph ...

[Darryl]

I was saying that your find won't work if the value you are looking for is in the last node, however I was wrong. Your find won't work at all!!