Solved

List in C++

Posted on 2000-04-06
8
325 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
Independent Software Vendors: 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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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.

738 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