Linked List error!

[gaurav_13191]

Hi, I have the following code which compiles fine but does not produce any output..

using namespace std;

#include<iostream>
#include<cstdio>
#include<conio.h>

struct node
{
  int data;
  struct node *link;
};

void append(struct node *,int);
void addatbeg(struct node *,int);
void addafter(struct node *,int,int);
void display(struct node *);
int count(struct node *);
void Delete(struct node *,int);

int main(void)
{
   struct node *p;
   p=NULL;
   cout<<"No of elements in the linked list:"<<count(p);
   append(p,14);
   append(p,30);
   append(p,25);
   append(p,42);
   append(p,17);
   
   display(p);
   
   addatbeg(p,999);
   addatbeg(p,888);
   addatbeg(p,777);
   
   display(p);
   
   addafter(p,7,0);
   addafter(p,2,1);
   addafter(p,5,99);
   
   display(p);
   
   cout<<"\nNo of elements in the linked list:"<<count(p);
   
   Delete(p,99);
   Delete(p,1);
   Delete(p,10);
   
   display(p);
   
   cout<<"\nNo of elements in the linked list:"<<count(p);
   cin.get();
   getch();
   return 0;
}

void append(struct node *q,int num)
{
     struct node *temp,*r;
     if(q==NULL)
     {
      temp= new struct node; 
      temp->data=num;
      temp->link=NULL;
      q=temp;
     }
     else
     {
      temp=q;
      
      while(temp->link!=NULL)
       temp=temp->link;
       
      r= new struct node;;
      r->data=num;
      r->link=NULL;
      temp->link=r;
     }
}

void addatbeg(struct node *q,int num)
{ 
     struct node *temp;
     
     temp= new struct node;;
     temp->data=num;
     temp->link=q;
     q=temp;
}

void addafter(struct node *q,int loc,int num)
{
     struct node *temp,*r;
     int i;
     
     temp=q;
     
     for(i=0;i<loc;i++)
     {
      temp=temp->link;
      if(temp==NULL)
      {
       cout<<"\nThere are less than"<<loc<<"elements in the list";
       return;
      }
     }
     r= new struct node;;
     r->data=num;
     r->link=temp->link;
     temp->link=r;
}

void display(struct node *q)
{
     cout<<"\n";
     
     while(q!=NULL)
     {
       cout<<q->data;
       q=q->link;
     }
}

int count(struct node *q)
{
    int c=0;
    
    while(q!=NULL)
    {
      q=q->link;
      c++;
    }
    return c;
}

void Delete(struct node *q,int num)
{
     struct node *old,*temp;
     
     temp=q;
     while(temp!=NULL)
     {
       if(temp->data==num)
       {
         if(temp==q)
          q=temp->link;
         else
          old->link=temp->link;
          
         delete temp;
         return;
        }
        
        else
        {
          old=temp;
          temp=temp->link;
        }
      }
      cout<<"\nElement"<<num<<"not found";
}

Please help me out!!!

[Allophyl]

Just out of curiosity, why aren't you just using the linked list container provided in the standard library?

[caut_baia]

I think you should pass the nodes by reference.Or inside the functions which are supposed to modify a value try using the value of the object passed as an argument.

void change_things(object* to_suffer_changes)  {
  *to_suffer_changes=something_else;
 }
void change_things(object& to_suffer_changes)  {
  to_suffer_changes=something_else;
 }

[gaurav_13191]

For the first answer, I dont know what is a linked list container that you are referring to.. Please explain

For the second answer, just a doubt,why can't we use simple objects rather than references to objects.. Infact in the original program references to object were used.. But out of curiosity I made the modifications.. Please clear up the doubt..

[Allophyl]

For the first answer, I dont know what is a linked list container that you are referring to.. Please explain

For the second answer, just a doubt,why can't we use simple objects rather than references to objects.. Infact in the original program references to object were used.. But out of curiosity I made the modifications.. Please clear up the doubt..

This:
http://www.cplusplus.com/reference/stl/list/
you simply need to #include <list> to be able to use it.

[Rashakil Fol]

I take it you mean that display(...) is not producing any output, other than a newline. You could figure out your problem by adding a few statements to that function that print out useful information like whether the list in question is empty or not. You could add a display(...) call after a single operation of one of your functions, to see whether it should work. You could try constructing a list of size one manually, in the main function, and see if you can display that.

The problem with your code is that you don't understand the semantics of how passing parameters to functions works. You seem to think that modifying the parameter 'q' will modify the variable you passed as an argument. This will not happen.

[JasonHippy]

Are you sure that compiles?? The 'using namespace std;' is before the #includes. So unless I'm mistaken, nothing in the std:: namespace will be visible to the compiler until after the first #include.

Anyway that aside, as Rash has already pointed out; inside your append function you cannot reassign the passed-in pointer to point to another memory address...
Well... You can, but because of the way that parameters are passed to functions, this change will only be visible inside the function. Outside the function, the change to the pointers address will have had no effect.

e.g.
In main you are creating a 'struct node' pointer p, which initially points to nothing/NULL. You are then passing the pointer into your append function. Because the passed-in pointer is NULL, you are creating a new 'struct node' instance and then assigning the passed-in pointer to point to the new instance.. Inside the append function that's fine, but this does not change the pointer in the calling function(i.e. in main). The pointer here will still be pointing to nothing / NULL.

There is a quick solution using your existing code but it is a bit hacky looking. If you alter your append function to return a 'struct node*' like this:

struct node* append(struct node *q,int num)
{
	// In both instances you were creating a new node, 
	// so may as well factor this outside of the if..else!
	struct node *r= new struct node;
	r->data=num;
	r->link=NULL;

	//if(q==NULL)
	if(!q) // equivalent to the above
		return r;
	else
	{
		struct node *temp=q;

		while(temp->link)// no need for the !=NULL part!
			temp=temp->link;
		temp->link=r;
		return NULL;
	}
}

If the passed-in pointer is NULL, the function returns a pointer to a new instance of the node structure, otherwise new node is added to the list and NULL is returned.

So now, in your main function; on your first call to append (and only on the first call) you could do this:

p = append(p,14);

NOTE: The rest of your appends should NOT be altered, only the first call to append should be made in this way!

Using the above code, p initially points to NULL, we assign p the value returned by calling append(), passing the pointers current address (NULL) and a value (14!).
Inside append, a new node is created and it's address is returned, this value is assigned to the pointer p in main. So now p points to the first node in the list.

Subsequent calls to append will now cause new nodes to be added to the list.

As mentioned, this solution is the quickest, hackiest solution to your problem. But personally I'd say the best way would be to clean up the logic of your solution a bit.

My suggestions are:
1. Keep your node structure (that's absolutely fine!).
2. Create a class for your linked list.
3. In the linked list class use a node pointer to keep track of the first item in the list (the head of the list)
4. Perhaps also use a pointer to the last item (the tail), to save having to traverse the list each time you want to append something.
5. Add your append function and the other functions to be members of the linked list class.

Hopefully that's given you an idea of the sort of direction to take with your code.
Cheers for now,
Jas.

[gaurav_13191]

Well thanks JasonHippy and others too for all of your answers. But the fact is I am a bit weak in programming and that is why I could not understand some of the answers.

Like the last answer posted has been explained in detail,but as I am new to it.. I was able to understand it partially..

However, I am working on that and in a period of time would be able to grasp all these concepts.. Thanks for now..

[gaurav_13191]

Just another question on this:

if my append () function was like:

void append(struct node **q,int num)

{
struct node *temp,*r;
if(*q==NULL)
{

temp= new struct node;
temp->data=num;
temp->link=NULL;
*q=temp;
}
else
{
temp=*q;
while(temp->link!=NULL)
temp=temp->link;

r= new struct node;;
r->data=num;
r->link=NULL;
temp->link=r;
}
}

I think then also p should remain NULL outside when I pass it to this function.If I am wrong please correct me..

[JasonHippy]

No that's different, in this case p will actually be modified. Hmm, this is gonna be tricky to explain!

I'll try not to confuse you too much, but this is as I understand it! (I'm sure one of the more senior guru types here will jump in and save me if I am off slightly!)

In this case, I'm assuming that you've declared a pointer to a node called p and set it to point to null as per your original code.

struct node *p=NULL;

This creates a node pointer on the stack which initially contains the memory address of NULL (0x00000000).
For the purposes of this example, I'll use an arbitrary hexadecimal value to represent the location in memory of p:

---------------------------
address      |   contents
===========================
0x45ab34da   |   0x00000000
---------------------------

So that's the variable 'p' pointing to null.

When you call the new version of your append function, it wants a pointer to a pointer. At the moment 'p' is just an ordinary pointer, so to pass a pointer to a pointer into the function you have to pass the address of 'p' (in other words &p) when you call the function:

append(&p, 14);

When the append function is called and its stack-frame is initialised, a pointer to a node pointer (q) is created, this points to the location in memory of the pointer p.
So q looks like this: (Again, I'll use an arbitrary address)

---------------------------
address      |   contents
===========================
0x5432abcd   |   0x45ab34da   (NOTE: this is the address of 'p' in main)
----------------------------

so now when you do your:

if(*q==NULL)

You're dereferencing the pointer pointed to by q, in other words you are essentially dereferencing the same memory location as p in main.
i.e. The pointer 'p' in main points to exactly the same memory address as *q.

So now, where you create a new node object and assign *q to point to the address of the new node (temp)
e.g.

*q=temp

This is what happens:
(we'll assume that the new node was created at memory address 0x654321ab)
contents of q:

---------------------------
address      |   contents
===========================
0x5432abcd   |   0x45ab34da   
----------------------------

contents of *q:

---------------------------
address      |   contents
===========================
0x45ab34da   |   0x654321ab (*q contains the address of the new object)
---------------------------

contents of p in main:

---------------------------
address      |   contents
===========================
0x45ab34da   |   0x654321ab 
---------------------------

p in main and *q have the same base address (0x45ab34da) and are pointing to the same location (0x45ab34da), therefore they both point to the new node object.
The address of q stayed the same throughout the function.

So in this case, you've actually successfully modified the address that the pointer p in main is pointing to because p in main and *q point to the same memory locations.

By contrast, here's what was happening in your original append function when you were passing a single pointer:

You created a node pointer and initialised it to NULL:

struct node *p=NULL;

So this is the location and content of p:

---------------------------
address      |   contents
===========================
0x45ab34da   |   0x00000000 (points to null)
---------------------------

And then in your append function call you pass the pointer p to the function:

append(p, 14)

Now this is where the difference lies. When the stack frame is initialised for the append function, a pointer (q) is created which contains the address contained in the passed in pointer.
So this is what q looks like:

---------------------------
address      |   contents
===========================
0x5432abcd   |   0x00000000 (points to null)
---------------------------

Now the thing to note here is that although both of the pointers point to null, p and q are separate pointers. They are in different memory locations, but they both point to the same address..i.e.null.

So now, when you assign q to point to the new node:

q=temp;

We'll use 0x0x654321ab again as the address for the new node.
This is what q looks like:

---------------------------
address      |   contents
===========================
0x5432abcd   |   0x0x654321ab (points to null)
---------------------------

Now compare that with p in main:

---------------------------
address      |   contents
===========================
0x45ab34da   |   0x00000000
---------------------------

So that is why the original function failed to alter the address that p pointed to.

When you pass a pointer to a function, a copy of that pointer variable is created in memory. The pointer allows you to modify the contents of the object it points to, but altering the address that the pointer points to inside the function will not change the address of the equivalent pointer outside of the function if you catch my meaning.

But when you used your pointer to a pointer to an object, you altered the address of the pointer to the object, but you did not alter the address of the 'base' pointer... Not sure if I'm explaining this particularly clearly, but I hope you get what I'm driving at!

Although it worked, using that extra level of indirection is still a bit hacky IMHO. I still think you'd be better served creating a class for your linked list!

Cheers for now,
Jas.

[gaurav_13191]

Thanks a lot Jasonhippy for your detailed explanation, it cleared my several confusions regarding the program and pointers.. your earlier explanation was also good but this was what i was looking forward to.. and yes I will definitely try your method(making a class)..