Solved

List in C++

Posted on 2000-04-06
8
322 Views
Last Modified: 2010-04-01
Hello,

I tried to make a list, and it is working fine, but Im getting some problems when I try to delete an element from it.

I provide all the code, but the problem is likely to be in the DeleteFromTheList method. So, dont be afraid if you see a lot of code: its easy (should be)

The list is made of elements of this class:

class CEnsemble: public CObject
{
protected:
      CString Name;
      CEnsemble *nextNode;
        int number;
public:
      int NoOfSCs;
      DWORD Identifier;
      CListe *SCList;
      CEnsemble(CString);
      void WriteName (CString);
        CString ReadName ();            
      void WriteNameR (CString);
      CString ReadNameR ();            
        CEnsemble* GetNextPtr();      
      void SetNextPtr (CEnsemble*);      
      void SetNumber (int);
      int GetNumber();
      SC ListOfSC[20];
      stSC ListOfSCst[20];
};

The code for the list is:

HEADER FILE:
------------
class CListe: public CDialog
{
protected:
      CEnsemble* listHead;
      int NoOfNodes;
public:
      CListe();
      void init();
      void displayList();
      void deleteList();
        void InsertList(CString,DWORD);
      void DeleteFromTheList(int);
      int GetNoOfNodes();
      void SetNoOfNodes(int);
      CEnsemble* SearchList(int);
};

.CPP FILE
---------
//(I give only the important methods)

CListe::CListe(void){     //contructor
      listHead = NULL;
      NoOfNodes=0;
}

void CListe::init(){
      listHead = NULL;
      NoOfNodes=0;
}

}
void CListe::InsertList(CString name, DWORD identifier){
      int counter=NoOfNodes;
      CEnsemble* temp = new CEnsemble(name);
      temp->Identifier=identifier;
      temp->SetNextPtr(listHead);
      listHead=temp;
      NoOfNodes++;
      CString auxi;
      CEnsemble* currLink = listHead;
      while(currLink)
      {
                      currLink->SetNumber(counter);
            counter--;                    currLink=currLink->GetNextPtr();
      }

}

CEnsemble* CListe::SearchList(int number){
      CEnsemble* currLink= listHead;

      if (currLink == NULL)
            return currLink;
      while(currLink)
      {
            if (currLink->GetNumber() == number)
                  return currLink;
            currLink = currLink->GetNextPtr();
      }
      return (NULL);
}

void CListe::DeleteFromTheList(int which){
      CEnsemble* currLink = listHead;
      bool exit=false;

      if (currLink == NULL){
            return;
      }

      if ((currLink->GetNextPtr==NULL)&&(which==0)){
            listHead=NULL;                             //the list is now empty
            MessageBox("2");
            return;
      }

      while ((currLink->GetNextPtr != NULL)&&(!exit)){
            CEnsemble* nextLink=currLink->GetNextPtr();
            exit=false;
            if (nextLink->GetNumber()==which){
                  currLink->SetNextPtr(nextLink->GetNextPtr());
                  delete (nextLink);
                  exit=true;
            }
      }
      NoOfNodes=NoOfNodes-1;
      currLink = listHead;
      int counter=NoOfNodes;
      while(currLink)
      {
            currLink->SetNumber(counter);
            counter--;
            currLink = currLink->GetNextPtr();
      }      
}


I repeat: I get only problems when I try to delete an element from the list: the program terminates.
Help!!

Thanks in advance.
0
Comment
Question by:fcogilgo
  • 5
  • 3
8 Comments
 
LVL 22

Accepted Solution

by:
nietod earned 100 total points
ID: 2689901
The root of the problem is the line

if ((currLink->GetNextPtr==NULL)&&(which==0)){

The problem there is that "GetNextPtr" is never NULL.  That is a pointer to a fuction and that pointer is never NULL.  You meant to  place parenthses behind it to call the function.  Then you might get a return valeu that is NULL, like

if ((currLink->GetNextPtr() ==NULL)&&(which==0)){

You seem to insist that that is all you are interested in fixing. (you said "I repeat: I get only problems when I try to delete")    However, I do see lots of things that are--well at best--questionable.  If you are interested.
0
 

Author Comment

by:fcogilgo
ID: 2690588
Thanks nietod.
Of course it would be very kind from you if you told me any improvement of my "questionable" code. So please tell me if there're some other things to correct. Thanks again.

(I wait until you give me further details, so that I can increase the points I give)
0
 
LVL 22

Expert Comment

by:nietod
ID: 2691821
I wasn't sure if that was what you wanted...

1. Small point, but in

>> void CListe::InsertList(CString name, DWORD identifier)

the "name" parameter could be constant and in fact could be a reference, like

void CListe::InsertList(const CString &name, DWORD identifier)

You just get a little extra security against mistakes by making it constant and a little extra speed (usually) by making it a reference.)

2. small point again, but the code

>> CEnsemble* temp = new CEnsemble(name);
>> temp->Identifier=identifier;

suggests that CEnsemble should have an overloaded cosntructor that takes an Identifier, like

CEnsemble* temp = new CEnsemble(name,identifier);

3.  The code
>> CEnsemble* currLink = listHead;
>> while(currLink)
>> {
>>    currLink->SetNumber(counter);
>>    counter--;        
>>    currLink=currLink->GetNextPtr();
>> }

suggests a "weak" design.  The advantage to linked lists is that you can quickly insert or delete anywhere in the list without having to access a lot of other items in the list.  Since you are numbering items you are loosing this benefit.   Since you want to refer to items by an index value, a dynamic array class (like STL's vector<>) would be more convenient (the code would be simpler) and could possible be faster.  If you choose to continnue with a linked list--which is very efficient when you have to do lots of insertions and deletions--then you might want to consider using an alternate scheme to identify items in the list.  For example, use a pointer to an item.  That will tend to be easier as you don't have to addjust every item in the lsit after an insert or delete.

This point applies to much of the code you've show.

4.  Your delete logic could be simplified.  The initial part of the procedure (before the settign of the counters ould be written as

void CListe::DeleteFromTheList(int which){

CEnsemble* currLink = listHead;
CEnsemble* PrevLink = NULL;

while (currLink)
{
    if (currLink->GetNumber()==which)
       break;
   PrevLink = currrLink;
   currLink = currLink->GetNextPtr();
}
// 3 posibilities.  Item was not found, item was found
// and was at the head.  item was found and was not
// at the head.

if (!currlink) // If item was not found
   return; // return without deleting.
if (PrevLink) // If item was not the nead item
   Prevlink = CurrLink->getNextPtr(); // skip item in the list.
else // If item was the head
   listHead = CurrLink->GetNextPtr(); // 2nd item is new head.
// Note how the code will wtill work when the item to be deleted is
// the LAST item.

That is the standard pattern you should follow for deleting from a singly linked list.  it is much simpler.

Note however, that a doubly linked list almost certainly better.  A doubly linked list allows deletes at any position without a search.  (well, if you keep using these numbers, you still need to search, thoug).  A singly linked list should usually be used only for cases where you add to or delete from the head position only.  Use a doubly linked list when you might add to or delete from the middle of the list.  (Or just use a double linked list period.)
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 

Author Comment

by:fcogilgo
ID: 2698018
Adjusted points from 55 to 85
0
 

Author Comment

by:fcogilgo
ID: 2698019
the code you propose to delete an item from the list doesnt work. In fact, I cant see in which point is the item to delete "skipped". I think you have to use somewhere a "SetNextPointer" method (defined somewhere) to set the new pointer. By updating Prevlink you dont manage to do it. I think this sentence is wrong:

Prevlink = CurrLink->getNextPtr(); // skip item in the list.

because the pointer of the object you are handling isnt updated (Thats what I think)

Anyway, it doesnt work. Know why??
0
 
LVL 22

Expert Comment

by:nietod
ID: 2698060
Right,

if (PrevLink) // If item was not the nead item
   Prevlink = CurrLink->getNextPtr(); // skip item in the list.

should be

if (PrevLink) // If item was not the nead item
   Prevlink->SetNextPtr(CurrLink->getNextPtr()); // skip item in the list.

0
 

Author Comment

by:fcogilgo
ID: 2700352
Adjusted points from 85 to 100
0
 

Author Comment

by:fcogilgo
ID: 2700353
OK, thanks a lot. Now Im an expert in linked lists!!
Gracias!
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question