Solved

List in C++

Posted on 2000-04-06
8
317 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
 

Author Comment

by:fcogilgo
ID: 2698018
Adjusted points from 55 to 85
0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

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

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
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.
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.

760 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

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now