Bool function always true & Tail Node Removal in Singly-Linked List creates infinite loop

Question

ok this is me training on singly-linked lists, being a newbie... However, somewhere I must be messing things up. My code is pretty straight forward containing all the typical procedures you would expect..

Problems:

My boolean function is always true even when I type in numbers that are not in the list

Here's my code, look at the main function as well to get an idea of the order in which things happen. Ooh and thank you for your help!! :)

#include <string>
#include <iostream>

using namespace std;

class Node
{
    public:
         int n;
         Node* link;
};

void display(Node* head)
{

    cout<<head->n<<" ";

    while(head->link!=NULL)
    {
        head=head->link;
        cout<<head->n<<" ";
    }
    cout<<endl;

}

void addnode(Node*& head, int x) 
{
    if(head==NULL)
    {
        head=new Node;
        head->n=x;
        head->link=NULL; // Necessary? Why?
    }

    else
    {
        Node* p=new Node;
        p->n=x;
        p->link=head;
        head=p;
    }
}

bool found(Node* head, int x)
{                            
    if(head->n==x) return true;

    while(head->link!=NULL)
    {
        head=head->link;
        if(head->n==x) return true;
    }

    return false;
}


void addtail(Node*& head, int x) 
{                                
    if(head==NULL)          
    {                        
        head=new Node;  
        head->n=x;
        head->link=NULL;
    }

    else
    {
        Node* q=NULL; 
        q=head;       
        while(q->link!=NULL) q=q->link;

        Node* r=new Node;
        r->n=x;
        r->link=NULL;
        q->link=r;
    }
}

int removehead(Node*& head) 
{
    if(head==NULL)
    {
        cout<<"The list is empty";
        return 0; 
    }             

    int x;

    if(head->link==NULL)
    {
        x=head->n;
        head=NULL;
        return x;%0stackoverflow.com 
    Node* p=NULL;    
    p=head;
    head=head->link;
    x=p->n;
    delete p;
    return x;
}

int removetail(Node*& head) 
{
    if(head==NULL)
    {
        cout<<"The list is empty";
        return 0;
    }

    int x;

    if(head->link==NULL)
    {
        x=head->n;
        delete head;
        Node* head=NULL;
        return x;
    }

    Node* p=NULL; 
    p=head;
    while(p->link!=NULL) p=p->link;

    x=p->n;
    delete p;
    return x;
}



int main()
{

    int y; int z;

    Node* p=NULL;

    while(cin>>y)
    {
        addnode(p,y);
    }

    cin.clear(); cin.ignore(); 


    cout<<endl;

    display(p);

    cout<<endl;

    cout<<removehead(p)<<" ";

    cout<<removetail(p)<<endl;

    display(p);

    cout<<endl<<"give me a number:";

    cin>>z;

    if(found) cout<<endl<<"found"; 

    else cout<<endl<<"not found";

}

Answer 1

.(when I remove the tail node, is the link of the previous one now just pointing at some random part of the memory? Is that the problem? And why the infinite loop?

Looks like it:

int removetail(Node*& head) 
{
    // base cases elided

    Node* p=NULL; 
    p=head;
    while(p->link!=NULL) p=p->link;

    x=p->n;
    delete p;
    return x;
}

The previous link, that pointed to the p you are deleting, still points to p. Bad. It should be something like this:

int removetail(Node*& head) 
{
    // base cases elided

    Node* p=NULL; 
    p=head;
    while(p->link->link!=NULL) p=p->link;

    x=p->link->n;
    delete p->link;
    p->link = NULL;     // maintain linked list integrity
    return x;
}

This is safe to do (assuming memory isn't corrupted for other reasons) because you've already checked if head==NULL and head->link == NULL in one of the base cases, so an initial call to p->link->link = head->link->link will not give you any improper pointer access. If head->link->link == NULL, that's ok.

---

And why the infinite loop?

An interesting question.

For a slightly flawed philosophical explanation: assuming you don't get an illegal memory access error caused by accessing a bad pointer, you're talking about a pointer value that randomly points somewhere. Real memory is finite, so any sequence of pointer references in a finite set have to repeat at some point in a cycle (otherwise the set would not be finite). Of course, that could include a NULL which would stop the infinite loop.

More likely you're hitting some bad memory pattern reserved by the OS memory manager, like 0xcdcdcdcd which points to 0xcdcdcdcd. In which case it is a bad choice: default memory patterns should probably be designed so that if they show up in a pointer, they are likely to cause a bad memory exception.

You could stop the program in a debugger and tell us what the pointer value is, and that would answer that part of the question.

Answer 2

You should turn on warnings when you compile. Here is what the compiler says:

% g++ -Wall list.cc
list.cc: In function ‘int removetail(Node*&)’:
list.cc:120:15: warning: unused variable ‘head’ [-Wunused-variable]
list.cc: In function ‘int main()’:
list.cc:166:13: warning: the address of ‘bool found(Node*, int)’ will always evaluate as ‘true’ [-Waddress]

The first error points out that you declared a local variable head in function removetail (with Node* head=NULL;), while you probably meant to update the argument's value (with just head=NULL;).

The second error explains why found (an address) is always true. You probably meant to call the function found(...) with some arguments.

Answer 3

The first thing is that you do

if(found) cout<<endl<<"found"; 

which should probably be

if(found(p,z)) cout<<endl<<"found";

The first version is basically checking if the function pointer to "found" is not null, ie that it has a value. The second actually calls the function as you probably wanted.

The second thing is that when you remove the tail. you're not actually removing it from the list, you're just deleting it. You need to unlink it from the list too or you'll point to uninitialized memory.