Linked lists questions

**Emeighty** · 09-09-2008

Since i am not hearing or understanding anything, I am going to start from scratch. I am aware there are pretty talented people on this site. If it takes me making myself look very ignorant to learn something, so be it. I don't now what questions to aks and how to ask them, so i will a question worded a few times.
So is the book grammer different than actually grammer used?

indent....is it?

Code:

     

function()
{        something;
}

or 

          function() {
       
         something;
}


or is it 


  function () 
{
            something

}

**matsp** · 09-09-2008

I write like this:

Code:

int function(paramters)
{
    do something;
    if (stuff)
    {
         do others
    }
    else if (x)
    {
        switch(y)
        {
           case 'a':
              Some code here
              break;
           default:
              break;
    }
    else
    {
        something else. 
    }
}

However, the most important part is that each new level is "deeper" than the previous level, and that the code is consistent. Most editors have a "auto-indent" feature that can be used to format your code (and that will maintain correct format for you, if you like - I use Emacs, and it's near on impossible to get it wrong, but you probably want to set "stroustrup" style instead of the default).

--
Mats

**Emeighty** · 09-09-2008

ok, I found the indent feature on the Dev-CPP compiler and the "find matching braces " feature and enabled it.

For the program, I am trying to fill the HeadPtr only if it is empty.
My questions are.
1. Is a new node an empty node?
2. Is a node pointing to NULL an empty node?
3. If 1, or 2 arent empty nodes what is an empty node?

My program below does not output what is in the if statement. The goal is to fill it only if the HeadPtr is empty.

Code:

#include <iostream>
using namespace std;

struct node
{
   int item;
   node *next;
};

void insertion( node *&HeadPtr, int NumberToInsert)
{    
     if (HeadPtr == new node)
     {
	  	cout << "Inside first if " << endl;
     } //end if
		
}// end insertion

int main() 
{   
    int number= -1;
    node *HeadPtr=new node;
   
    insertion (HeadPtr, number);
    system("pause");
    return 0;
} //end main

**matsp** · 09-09-2008

Code:

if (HeadPtr == new node)

This is almost certain NEVER be true - only if you recently did "delete HeadPtr" and you didn't set HeadPtr to 0 as well as being "lucky" enough to get the same address that you just deleted.

Your check should be:

Code:

if (HeadPtr == 0)
...

--
Mats

**Emeighty** · 09-09-2008

I changed up a few things and got the same result, the program skips the if and goes straight to the else.

How would an empty node be defined?
Also the equivilant operator == makes a difference, when
Is = used for variable numbers, and == used for other than integer variables

HeadPtr=0 the program freezes
HeadPtr==0 it skips the if and goes straight to else.

Code:

#include <iostream>
using namespace std;

struct node
{
   int item;
   node *next;
};

void insertion( node *HeadPtr, int NumberToInsert)
{    
     if (HeadPtr == 0)
     {
     	cout << "Inside first if " << endl;
	  	HeadPtr->item=NumberToInsert;
	  	cout << HeadPtr->item;
     } //end if
	
       else
    {
	 	cout << " In the else: " << endl;
    }//end else	
}// end insertion

int main() 
{   
    int number= -1;
    node *HeadPtr=new node;
    HeadPtr==0;
    while (number !=0) 
    {
    cout <<" Please input the number to insert: " ;
	cin >> number;
    insertion (HeadPtr, number);
    }
	
	system("pause");
    return 0;
} //end main

**matsp** · 09-09-2008

Meah, I expect it does:

Code:

    node *HeadPtr=new node;
    HeadPtr==0;

The first line of those above allocates memory and sets HeadPtr to the newly allocated memory. The second line compares HeadPtr with zero and throws away the result. If you enable compiler warnings (in the Dev-CPP compiler options settings - search for a recent post by Dino to find where they are if you can't find it), it should give you a warning about "statement has no effect" which is usually a good warning to tell you that the line probably doesn't do what you wanted it to do.

--
Mats

**Emeighty** · 09-12-2008

I finally (with lots of help) came up with the code for this linked. But the only thing i cant get right is the retrieve function. I am able to retrieve things that are in the list, but if it's not in the list, the program crashes. can anyone see whats going on in that function that i am not seeing?

Code:

#include <iostream>
using namespace std;


struct node
    {
    int  number;
    node *next;
    };

 class List
     {

     public:

      List();
     ~List();
      node *Head();
     node *createnode(int);
     void insert(node *, int);
     void traverse(node *);
     void retrieve(node *, int);
     
     private:
     node *TheHead;
    
     };

 List::List() 
     {
     TheHead = NULL;
     }

 node *List::Head()
      {
      return TheHead;
      }
 List::~List() {}  //Destructor

  node *List::createnode(int NumberToInsert)
     {        
        node *NewOne = new node;
        NewOne ->number = NumberToInsert;
        NewOne ->next = NULL;
        return NewOne;
     }

  void List::insert(node *pPointer, int ANumber) 
     {
     node *tmp = new node;
     
     tmp = createnode(ANumber);

     tmp -> next = pPointer;

     TheHead = tmp;
     } 

 void List ::traverse(node *CurPtr)
     {
           node *current = CurPtr;
           
           while (current !=NULL)
               {
               cout << current ->number << " ";
               current = current ->next;
                }           
           cout << "\n";
     }


 void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
        {
        node *tmp = pPointer;
        int position=0;

        while (tmp != NULL && tmp->number != XNumber)
            {
            tmp=tmp->next;
            position++;
            }
        
        if (tmp ->number != XNumber )
            {
            cout << XNumber << " Is at position " << position << endl;
            }
         else 
            {
             cout << XNumber << "Is not in the list " << end;
            }
     }
 int main()
     { 
     
     List s;
     node * pPointer = s.Head();
     
     int TheNumber=-1;
     int RetrievedNumber = -1;
     
     while (TheNumber != 0)
          {
          cout << "Please enter in a number: enter 0 to quit: " ;
          cin >> TheNumber;
          s.insert(s.Head() , TheNumber);
          }

     s.traverse(s.Head());

     while (RetrievedNumber !=0)
         {
         cout << "Please enter the number to be retrieved , 0 to quit: " ;
         cin >> RetrievedNumber ;
         s.retrieve(s.Head(), RetrievedNumber);
         }
   
     system("pause");
     return 0;
     }

**matsp** · 09-12-2008

That looks much better.

Here's a few "constructive criticism" comments:

Code:

  node *List::createnode(int NumberToInsert)
     {        
        node *NewOne = new node;
        NewOne ->number = NumberToInsert;
        NewOne ->next = NULL;
        return NewOne;
     }

Most of this would normally go into a node constructor. Basically all but the new and return lines, and with the middle of this function "disappearing", you'd probably not need a function at all, just use new in the actual code where you currently call createnode.

Code:

  void List::insert(node *pPointer, int ANumber) 
     {
     node *tmp = new node;
     
     tmp = createnode(ANumber);

     tmp -> next = pPointer;

     TheHead = tmp;
     }

This would make more sense if you didn't have a pPointer argument, but rather used TheHead - as that is what you are essentially doing anyways by using s.Head() in insert - and passing anyting else, such as a node in the middle of the list, TheHead would point at the new node, TheHead->next is then pointing to the middle of the list, so anything BEFORE the new node is lost.

Likewise, I doubt that traverse needs to have an argument of a node pointer - just use TheHead internally.

in retrieve:

Code:

        if (tmp ->number != XNumber )
            {
            cout << XNumber << " Is at position " << position << endl;
            }
         else 
            {
             cout << XNumber << "Is not in the list " << end;
            }

Not a good idea to test if tmp->number != XNumber, since if tmp is NULL, you'd be trying to read an invalid memory address. The better method would be to check if tmp is NULL - then you DIDN'T find it. [By the way, I expect this ALWAYS says "is not in the list", since either you FOUND the numer, OR XNumber is different from tmp->number.]

And again, I think retrievenumber should search based on TheHead, rather than using an argument.

Code:

     List s;
     node * pPointer = s.Head();

1. pPointer will always be NULL here.
2. pPointer is never used in main().

Code:

List::~List() {}  //Destructor

Sorry for the random order: Don't you think it would be a good idea to destroy any list you have in the destructor.

--
Mats

**Emeighty** · 09-12-2008

I changed up the code for the retrieve function , and it works like a charm !!!!
OH boy this was a challenging question. 2 more to go.

the new code is

Code:

void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
        {
        node *tmp = pPointer;
        int position=0;

        while (tmp != NULL && tmp->number != XNumber)
            {
            tmp=tmp->next;
            position++;
            }
        if (tmp == NULL )
            {
            cout << XNumber << " is not in the list " << endl;
            }
        else if (tmp->number = XNumber )
            {
            cout << XNumber << " is located in position " << position << endl;
            }
        else 
            {
            cout << " this is 0 " << endl;
            }

For the arguments of pPointer. My assignment has me bring in a node and a number as a parameter. Im not understanding how to bring in TheHead directly into the insert and retrieve functions. If i try , it says that i cannot and

illegal reference to non-static member 'List::TheHead displays.

i got changed up the parameters in the main.
but i am not sure what u mean by , destroying the list, do u mean using the delete command?

here is the full code after the mods i did. pPointer doesnt like me changing it at all.

Code:

#include <iostream>
using namespace std;


struct node
    {
    int  number;
    node *next;
    };

 class List
     {

     public:

      List();
     ~List();
      node *Head();
     node *createnode(int);
     void insert(node *, int);
     void traverse(node *);
     void retrieve(node *, int);
     
     private:
     node *TheHead;
    
     };

 List::List() 
     {
     TheHead = NULL;
     }

 node *List::Head()
      {
      return TheHead;
      }
 List::~List() {}  //Destructor

  node *List::createnode(int NumberToInsert)
     {        
        node *NewOne = new node;
        NewOne ->number = NumberToInsert;
        NewOne ->next = NULL;
        return NewOne;
      }
  void List::insert(node *pPointer, int ANumber) 
     {
     node *tmp = new node;
     
     tmp = createnode(ANumber);

     tmp -> next = pPointer;

     TheHead = tmp;
     } 

 void List ::traverse(node *CurPtr)
     {
           node *current = CurPtr;
           
           while (current !=NULL)
               {
               cout << current ->number << " ";
               current = current ->next;
                }           
           cout << "\n";
     }


 void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
        {
        node *tmp = pPointer;
        int position=0;

        while (tmp != NULL && tmp->number != XNumber)
            {
            tmp=tmp->next;
            position++;
            }
        if (tmp == NULL )
            {
            cout << XNumber << " is not in the list " << endl;
            }
        else if (tmp->number = XNumber )
            {
            cout << XNumber << " is located in position " << position << endl;
            }
        else 
            {
            cout << " this is 0 " << endl;
            }

         }
 int main()
     { 
     
     List s;
     
     s.Head();

     int TheNumber=-1;
     int RetrievedNumber = -1;
     
     while (TheNumber != 0)
          {
          cout << "Please enter in a number: enter 0 to quit: " ;
          cin >> TheNumber;
          s.insert(s.Head() , TheNumber);
          }

     s.traverse(s.Head());

     while (RetrievedNumber !=0)
         {
         cout << "Please enter the number to be retrieved , 0 to quit: " ;
         cin >> RetrievedNumber ;
         s.retrieve(s.Head(), RetrievedNumber);
         }
   
     system("pause");
     return 0;
     }

**matsp** · 09-12-2008

For the arguments of pPointer. My assignment has me bring in a node and a number as a parameter. Im not understanding how to bring in TheHead directly into the insert and retrieve functions.

Well, then it's likely that you shouldn't be doing this inside a class, and not have "TheHead" inside a class.

--
Mats

**Emeighty** · 09-15-2008

I am trying to insert numbers into this linked list recursively, but the only way that works is if the inserted number is less than the head. Can anyone exlain how i can fix my error?

Code:

  #include <iostream>
using namespace std;


struct node
    {
    int  number;
    node *next;
    };

 class List
     {

     public:

      List();
     ~List();
      node *Head();
     node *createnode(int);
     void insert(node *, int);
     void traverse(node *);
     void retrieve(node *, int);
     
     private:
     node *TheHead;
    
     };

 List::List() 
     {
     TheHead = NULL;
     }

 node *List::Head()
      {
      return TheHead;
      }
 List::~List() {}  //Destructor

  node *List::createnode(int NumberToInsert)
     {        
        node *NewOne = new node;
        NewOne ->number = NumberToInsert;
        NewOne ->next = NULL;
        return NewOne;
      } 
  void List::insert(node *pInsertedHead, int ANumber)    
     {
      
     node *tmp = new node;  // creates a new node for the new number(ANumber) to be inserted into
     
     tmp = createnode(ANumber); // ANumber is inserted into the new node tmp       

       if (TheHead ==NULL || TheHead ->number >=ANumber)
         {
         tmp->next = TheHead;
          TheHead =tmp;
         
       }
          
      else
          {
             if(pInsertedHead !=NULL && pInsertedHead->number <= ANumber)
               {
               insert(pInsertedHead->next, ANumber); 
               

               }
               
          } 
              
              
      }
       
      
 void List ::traverse(node *CurPtr)
     {
           node *current = CurPtr;
           
           while (current !=NULL)
               {
               cout << current ->number << " ";
               current = current ->next;
                }           
           cout << "\n";
     }


 void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
        {
        node *tmp = pPointer;
        int position=0;

        while (tmp != NULL && tmp->number != XNumber)
            {
            tmp=tmp->next;
            position++;
            }
        if (tmp == NULL )
            {
            cout << XNumber << " is not in the list " << endl;
            }
        else if (tmp->number = XNumber )
            {
            cout << XNumber << " is located in position " << position << endl;
            }
        else 
            {
            cout << " this is 0 " << endl;
            }

         }
 int main()
     { 
     
     List s;
     
     s.Head();

     int TheNumber=-1;
     int RetrievedNumber = -1;
     
     while (TheNumber != 0)
          {
          cout << "Please enter in a number: enter 0 to quit: " ;
          cin >> TheNumber;
          s.insert(s.Head() , TheNumber);
          }

     s.traverse(s.Head());

     while (RetrievedNumber !=0)
         {
         cout << "Please enter the number to be retrieved , 0 to quit: " ;
         cin >> RetrievedNumber ;
         s.retrieve(s.Head(), RetrievedNumber);
         }
   
     system("pause");
     return 0;
     }

**matsp** · 09-16-2008

Code:

     node *tmp = new node;  // creates a new node for the new number(ANumber) to be inserted into
     
     tmp = createnode(ANumber); // ANumber is inserted into the new node tmp

is definitely not right in the place it is, since you'd be leaking memory like the proverbial sieve if you have a long list and try to insert something at the tail of the list.

If you are passing in a node to insert at, you should not be using TheHead inside your function.

--
Mats

Thread: Linked lists questions

Thread Tools

Search Thread

Display

clueless

The final touches

Recusively inserting to list

Similar Threads

Linked Lists 101

Question On Linked Lists

How to use Linked List?

need help w/ linked lists

Linked Lists -- Again!!! Help!!