🔒 Locked

Linklist problem

Started by horizon981 Sep 29, 2006 at 11:28 AM 3 replies 1k views

Original Post

Sep 29, 2006 at 11:28 AM

Hello. I was making a program that would accept data and store it in a linked list in ascendind order. Here's the code:


//Sorted linked list
#include <iostream>
using namespace std;

class linklist
{
      private:
              struct node
              {
               int data;
               node *link;
              }*p;
      public:
             linklist();
             void display();
             void append(int);
             void del(int);
             int count();
}list1;

linklist::linklist()
{
 p=NULL;
}

void linklist::display()
{
 node *temp;
 
 if(p==NULL)
  cout<<"\nEmpty List!\n";
 else
  {
   temp = new node[1];
   temp = p;
   
   cout<<"\nList is: ";
   while(temp)
   {
    cout<<temp->data<<" ";
    temp = temp->link;
   }
  }
}
      
void linklist::append(int num)
{
 node *temp = new node;
 node *r = new node;
 
 temp = p;
 r->data = num;
 
 if(p==NULL || p->data>num)
   {
    p = r;
    p->link = temp;
   }
 else 
 {
  while(temp->link)
  {
   if((temp->data<=num) 
    && (temp->link->data>num || temp->link==NULL)) 
    {
     r->link = temp->link;
     temp->link = r;
     return;
    }
   temp = temp->link;
  }
 } 
}
 
void linklist::del(int num)
{
     node *temp = new node;
     node *r = new node;
     temp = p;
     
     if(p==NULL)
      cout<<"Empty List. Nothing to delete...";
     else if(p->data == num)//first node to be deleted 
     {
      temp = p;
      p = p->link;
      delete temp;
     }
     else
      {
       while(temp->data != num)
       {
        r = temp;
        temp = temp->link;
       }
       
       r->link = temp->link;
       delete temp;
      }
}

int linklist::count()
{
    int count=0;
    node *temp;
    
    if(p==NULL)
     return 0;
    else
     {
      temp = new node;
      temp = p;
      
      while(temp)
      {
       count++;
       temp = temp->link;
      }
      
      return count;
     }
}  

int main()
{
    cout<<"\nAdding 10, 8, 34, 19, -4 to list.";
    cout<<"\nDone.";
    
    list1.append(10);
    list1.append(8);
    list1.append(34);
    list1.append(19);
    list1.append(-4);
    
    list1.display();
    
    cout<<'\n';
    system("PAUSE");
    return 0;
}

However, the list does not store numbers that should go to the last, as a sample run of the program might show: The List is: -4 8 10 Press any key to continue... Plz help me with it, any help is welcome.

Palidine

Sep 29, 2006 at 11:55 AM

couple observations

1) single letter variable names make your code extremely hard to follow. variable names should be meaningful to people other than yourself

2) you seem to use an excessive number of allocations. for instance, why do you allocate new memory just to display the list.

void linklist::display(){ node *temp;  if(p==NULL)  cout<<"\nEmpty List!\n"; else  {   temp = new node[1];  //why are you allocating memory here??? this is a memory leak   temp = p;      cout<<"\nList is: ";   while(temp)   {    cout<<temp->data<<" ";    temp = temp->link;   }  }}

the mantra with new is "use sparingly and wherever you use it be sure to call delete".

Your problem in the append function is simmilarly an excessive number of calls to new. the only thing you should ever be new'ing in your linklist is the p variable or the link variable.

//neither of these lines should exist.... node *temp = new node; node *r = new node;

the algorithm for append is:

if p is NULL then allocate memory for p and store num in p

if p is not NULL then iterate the list to find the last node. allocate memory for the link of the last node and store your result in the new node.

again for your program to be correct, the _only_ thing you should ever new is the p variable or a link variable.

-me

Zakwayda

Sep 29, 2006 at 11:55 AM

This looks kinda homework-y (?), so just a couple of hints. In the append function, look carefully at the following code:

  while(temp->link)  {   if((temp->data<=num)     && (temp->link->data>num || temp->link==NULL))     {     r->link = temp->link;     temp->link = r;     return;    }   temp = temp->link;  }

And think about what happens when the input value is larger than any existing values in the list. A couple of things in particular to consider are:

1. The conditional for the while loop is that temp->link is non-null, and yet you test it for equality to null a couple of lines later, which points to the problem (or at least part of it).

2. Even if temp->link were not guaranteed to be non-null when you reach the second conditional, you're accessing link's data before you check to see if it's valid.

3. It looks like you have some memory leaks and other errant bits of code that don't do anything (other than leak memory, that is).

4. Probably some other things that I didn't see right off.

Rainault

Sep 29, 2006 at 11:57 AM

After only a few seconds of looking at your code, it appears to leak memory like a sieve. I think you will want to study pointers and dynamic memory allocation a lot more before you attempt to create your own linked list class. When you make such a fundamental error as this...

node *temp = new node;// Two lines downtemp = p;

... you show that you don't have a firm grasp of these concepts. That first line creates a new node and has "temp" point at it. Then you leak memory when you have "temp" point at something else. You don't have to use "new" with every pointer you create. Remember, "new" and "delete" don't create/destroy pointers. They allocate/deallocate memory, and that memory is leaked if you don't have any pointers pointing to it any more.

Zakwayda

Sep 29, 2006 at 12:00 PM

Quote:
Original post by Palidine
the following should be a working version of append. but please study it and don't just copy-paste and call it done.

*** Source Snippet Removed ***

Note that the OP's 'append' function is actually a poorly named sorted insertion function, so the above doesn't actually do what he's wanting.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.