Solved

List in C++

Posted on 2000-04-06
8
323 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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: 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.

Question has a verified solution.

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

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

761 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