Thread: Need urgent help in linked list

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    2

    Unhappy Need urgent help in linked list

    I encounter some problem in linked list coding. I extarcted part of the coding from a C++ book and I have been studied it for so long but still cant fix the error.
    The error is the variable "counter". In the book, "counter" is the variable to store the number of elements in the linked list and it's defined in private part of the class. In the constructor, they let counter=0 where the compiler shows that it's an error. Another errors are all the "counter++" in "insert2". I tried to correct those errors but i just can't fix them... Below are my coding. I'm struggling in this coding and i hope someone can help me...

    Code:
    #include <iostream>
    using namespace std;
    
    class linkedList
    {
    	private:
             struct node
             {
                int info;			//integer to be stored in the pointer
    			int counter;		//variable to store the number of elements in the list
                node *link;
             }*p;
    
    	public:
             linkedList();
             void insert(int num);
    		 void insert2(int num);	//insert node at a particular position
             void del(int num);
    		 void sort();			//insertion sort
    		 bool search(int num);
             void display();
             int count();
    		 void destroyList();
             ~linkedList();
    };
    
    linkedList::linkedList()
    {
        p = NULL;
    	counter = 0;
    }
    
    void linkedList::insert(int num)
    {
       node *q, *t;
    
       if(p==NULL)
       {
          p = new node;				//create a new node, p
          p->info = num;
          p->link = NULL;
       }
       else
       {
            q = p;
    		while(q->link != NULL)
    		q = q->link;			//advance q to the next node
    
          t = new node;
          t->info = num;
          t->link = NULL;
          q->link = t;
       }
    }
    
    void linkedList::insert2(int num)
    {
    	node *q, *r, *s;			//q = pointer to traverse the list
    								//r = pointer just before q
    								//s = pointer to create a node
    	bool found;
    	s = new node;
    
    	if(s!=NULL)
    	{
    		s->info = num;			//store the new item in the node
    		s->link = NULL;			//set the link field to NULL
    	}
    
    	if(p==NULL)					//case1: the list is initially empty and the node in it is the only node,
    	{							//so the first node in the list
    		p = new node;
    		//counter++;
    	}
    
    	else
    	{
    		q = p;
    		found = false;
    
    		while(q!=NULL && !found)		//search the list
    			if(q->info >= num)
    				found = true;
    			else
    			{
    				r = q;
    				q = q->link;
    			}
    
    		if(q==p)			//case2: the list isn't empty and the new item is smaller than the smallest item in the list.
    		{					//the new item goes in front of the list 
    			s->link = p;
    			p = new node;
    			//counter++;
    		}
    
    		else				//case3: the list isn't empty and the new item is larger than the first item in the list.
    		{					//the new item is to be inserted somewhere in the list
    			r->link = s;
    			s = new node;
    			//counter++;
    		}
    	}
    }
    
    void linkedList::del(int num)
    {
       node *q, *r;
       q = p;
    
       if(q->info == num)
       {
          p = q->link;				//make p points to the next node of q
          delete q;
          return;
       }
    
       r = q;
       while(q!=NULL)
       {
            if(q->info == num)
          {
             r->link = q->link;
             delete q;
             return;
          }
    
          r = q;
          q = q->link;
       }
    
       cout<<"\nElement "<<num<<" not Found."<<endl;
    }
    
    void linkedList::display()
    {
       node *q;
    
       for(q = p; q!=NULL; q=q->link)
            cout<<endl<<q->info;
    }
    
    int linkedList::count()
    {
       node *q;
       int c=0;
       for(q=p; q!=NULL; q=q->link)
       c++;
    
       return c;
    }
    
    void linkedList::sort()
    {
    	node *q, *r, *s, *t;		//q = the pointer to the last node of the sorted list
    								//r = the pointer to the node that is to be moved to its proper location
    								//s = current pointer
    								//t = the pointer which points to the node just before current pointer, s
    	q = p;
    
    	if(p==NULL)
    		cout<<"Cannot sort an empty list."<<endl;
    	else if(p->link==NULL)
    		cout<<"The list is of length 1. "
    			<<"It is already in order."<<endl;
    	else
    		while(q->link!=NULL)
    		{
    			r = q->link;
    
    			if(r->info < p->info)
    			{
    				q->link = r->link;
    				r->link = p;
    				p = r;
    			}
    			else
    			{
    				t = p;
    				s = p->link;
    				while(s->info < r->info)
    				{
    					t = s;
    					s = s->link;
    				}
    
    				if(s!=r)
    				{
    					q->link = r->link;
    					r->link = s;
    					t->link = r;
    				}
    				else
    					q = q->link;
    			}
    		}
    }
    
    bool linkedList::search(int num)
    {
    	node *q;				//pointer to traverse the list
    	bool found;
    	q = p;					//set current to point to the first node
    	found = false;
    
    	while(q!=NULL && !found)			//search the list
    		if(q->info==num)				//the item is found
    			found = true;
    		else
    			q = q->link;				//make current point to the next node
    
    	return found;
    }
    
    void linkedList::destroyList()
    {
    	node *q;			//pointer to deallocate the memory occupied by the node
    
    	while(p!=NULL)		//while there are nodes in the list
    	{
    		q = p;
    		p = p->link;	//advance p to the next node
    		delete q;
    	}
    }
    
    linkedList::~linkedList()
    {
       node *q;
       if(p==NULL)
    	return;
    
       while(p!=NULL)
       {
          q = p->link;
          delete p;
          p = q;
       }
    }
    
    int main()
    {
       linkedList list;
       int choice, i, x;
    
    start:
       cout<<"*****************************************************"<<endl;
       cout<<"                    ~ Main menu ~                    "<<endl;
       cout<<"    (1) Insertion of an integer into a sorted list.  "<<endl;
       cout<<"    (2) Delection of an integer in a list.           "<<endl;
       cout<<"    (2) Searching integer in a list.                 "<<endl;
       cout<<"    (3) Sorting integers in a list.                  "<<endl;
       cout<<"    (4) Exit.                                        "<<endl;
       cout<<"*****************************************************"<<endl;
       cout<<endl;
    
       cout<<"Please choose an operation that you would like to perform: "<<endl;
       cin>>choice;
       cout<<endl;
    
       if(choice==1)
       {
    	   cout<<"Enter integers ending with -1:"<<endl;;
    	   cin>>i;
    	   
    	   while(i!=-1)
    	   {
    		   list.insert(i);
    		   cin>>i;
    	   }
    
    	   cout<<endl;
    
    	   cout<<"The sequence of integers before sorting is:";
    	   list.display();
    	   cout<<endl;
    	   
    	   list.sort();
    	   cout<<"The sequence of integers after sorting is:";
    	   list.display();
    	   cout<<endl;
    
    	   cout<<"Enter an integer that you want to insert into the list: ";
    	   cin>>x;
    	   cout<<endl;
    
    	   list.insert2(x);
    	   cout<<"The sequence of integers after insertion of integer "<<x<<" is:";
    	   list.display();
    	   cout<<endl;
    
    	   list.destroyList();
    	   goto start;
       }
    
       else if(choice==2)
       {
    	   cout<<"Enter integers ending with -1:"<<endl;;
    	   cin>>i;
    	   
    	   while(i!=-1)
    	   {
    		   list.insert(i);
    		   cin>>i;
    	   }
    	   
    	   cout<<endl;
    	   cout<<"Number of integers entered is: "<<list.count();
    	   list.display();
    	   cout<<endl<<endl;;
    
    	   cout<<"Enter the integer to be deleted: ";
    	   cin>>i;
    	   
    	   list.del(i);
    	   cout<<endl;
    	   
    	   cout<<"The remaining integers are: "<<endl;
    	   list.display();
    	   cout<<endl;
    
    	   list.destroyList();
    	   goto start;
       }
    
       else if(choice==2)
       {
    	   cout<<"Enter integers ending with -1:"<<endl;
    	   cin>>i;
    	   
    	   while(i!=-1)
    	   {
    		   list.insert(i);
    		   cin>>i;
    	   }
    		
    		cout<<endl;
    		
    		cout<<"Enter the integer that you want to search: ";
    		cin>>x;
    		cout<<endl;
    		
    		list.search(x);
    		
    		if(x==i)
    			cout<<"The search integer is found in the list."<<endl<<endl;
    		else
    			cout<<"The search integer is not found in the list."<<endl<<endl;
    
    		list.destroyList();
    		goto start;
       }
    
       else if(choice==3)
       {
    	   cout<<"Enter integers ending with -1:"<<endl;
    	   cin>>i;
    	   
    	   while(i!=-1)
    	   {
    		   list.insert(i);
    		   cin>>i;
    	   }
    		cout<<endl;
    		
    		cout<<"The sequence of integers before sorting is:";
    		list.display();
    		cout<<endl<<endl;
    
    		list.sort();
    		cout<<"The sequence of integers after sorting is:";
    		list.display();
    		cout<<endl;
    
    		list.destroyList();
    		goto start;
       }
    
       else if(choice==4)
       {
    	   cout<<"See you next time! Bye Bye!"<<endl;
    	   system("PAUSE");
       }
    
       else
       {
    	   cout<<"Wrong input!!!"<<endl;
    
    	   goto start;
       }
    
       return 0;
    }

  2. #2
    Not stupid, just stupider yaya's Avatar
    Join Date
    May 2007
    Location
    Earthland
    Posts
    204
    I'm guessing:

    Code:
    counter = 0; // is wrong... it should be:
    p->counter = 0;
    Because counter is a member of node, not linkedList. Same goes for all those counter++'s.

  3. #3
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Logically, if counter refers to the number of items in the entire linked list, it should be a member of class linkedlist, not linkedlist::node.

    Once you fix that problem, the most obvious solution to correctly implementing the node count is to simply add one to counter every time a node is inserted, and decrement one every time a node is removed.

    Also, the linkedlist::count() function does not need to do an inefficient manual count by iterating through the list. You have a count variable, just return that. Fast and easy.
    Last edited by MacNilly; 03-12-2009 at 05:06 PM.

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    2
    Quote Originally Posted by MacNilly View Post
    Logically, if counter refers to the number of items in the entire linked list, it should be a member of class linkedlist, not linkedlist::node.

    Once you fix that problem, the most obvious solution to correctly implementing the node count is to simply add one to counter every time a node is inserted, and decrement one every time a node is removed.

    Also, the linkedlist::count() function does not need to do an inefficient manual count by iterating through the list. You have a count variable, just return that. Fast and easy.
    If it should be a member of class linkedlist, does it mean that it should be put under private but not in linkedlist::node?

    I don't really understand by 'return the count variable'. Can you pls explain to me?

    I'm sorry if I asked many silly questions but i'm a beginner in C++ and I'm trying my best to learn and cope up with it asap.

  5. #5
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    If it should be a member of class linkedlist, does it mean that it should be put under private but not in linkedlist::node?
    Yes.

    I don't really understand by 'return the count variable'. Can you pls explain to me?
    The code would be something like this, assuming count is a member variable of class linkedlist:

    Code:
    unsigned int linkedlist::size()
    {
        return count;
    }
    I'm sorry if I asked many silly questions but i'm a beginner in C++ and I'm trying my best to learn and cope up with it asap.
    No problem; I remember when I stayed up all night trying to implement a linked list using C with a recursive list definition. In your C++ code, it would be like making your linkedlist class have another linkedlist class as a member. This stuff takes a while to understand.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM