Member Avatar for TimC

I am having a small problem removing ALL items from a linked list. I have written a function that will remove all discharged patients from the linked list.

for(int a=1;a<(S.size()+1);a++)
               {
               int x=S.retrieve_status(a);
                        if (x==5)
                        {
                        S.remove(a);
                        }
               }

in this function I check to see if the status of the patient is =5 and if it is I remove it from the linked list.

typedef patient SeqItemType;  
 
class ListNode
    {
	    public:
	    SeqItemType item;
	   ListNode *next;

	   };



    class Sequence
	  { 
	
	   public:
       Sequence();                  


   	   bool isEmpty();
   	   int size();
   	   void insert(int index, SeqItemType newItem);
   	   void remove(int index);
   	   void alter_status(int index, int change);
               int  retrieve_status(int index);
   	  void display(int index, int a,int b, int c, int d,
                                                    int e, int f,int g); 
   	   void move(int from, int to);
   	   void alter_priority(int index);
               int retrieve_ward(int index);
               void alter_ward(int index, int change);
              void alter_doctors_name(int index, int y);
       
  	  private:
	  ListNode *find(int index);
              int length;       	
              ListNode *head;
  
               };



void Sequence::remove(int index) 
{   
    
	ListNode *cur;

   	
		// remove the first node in the list
		if (index == 1)
      	{ 
      		cur = head;
     		head = head->next;   	
     		
      	}
		else{
        	ListNode *prev = find(index-1);	
        		
			cur = prev->next;
			prev->next = cur->next;
		}	
		
		// clean things up!
		length--;
		cur->next = NULL;
		delete cur;
	
  
}

HOWEVER when I check my linked list after it will always contain 1 patient. even though the status of the patient is ==5. It delelts all but 1.

When I run the function again it will remove the last element.

Why do I have to run the function twice to remove all the elements from the linked list? is there a problem with my remove method in my linked list. or am I specifing the wrong parameters in my for loop function at the top of screen?

any suggestions greatly appreciated.

  • 2 Contributors
  • 2 Replies
  • 207 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by TimC

Dani AI

Generated

was right to question indexing and correctly noticed the real cause: removing while stepping forwards by index makes the list shrink and the next node slides into the index just visited. The loop then increments past it, so every time a node is removed the following node is skipped — which explains why a second pass cleans up the leftover. The root problem is not a buggy delete per se, but doing index-based removals in a forward loop.

A quick, robust fix for a 1-based Sequence API is to iterate backwards so removals do not affect unvisited indices:

for (int i = S.size(); i >= 1; --i) {
    if (S.retrieve_status(i) == 5)
        S.remove(i);
}

A better approach — both correct and faster on large lists — is a single-pass removal that walks the nodes with a previous/current pointer and deletes matches in-place. That avoids repeated index lookups (and the O(n^2) cost if remove() uses find()). Example pattern to embed in Sequence:

void Sequence::removeIfStatusIs(int target) {
    ListNode *prev = nullptr;
    ListNode *cur  = head;
    while (cur) {
        if (/* test cur->item for target status */) {
            ListNode *toDelete = cur;
            cur = cur->next;            // step forward before deleting
            if (prev) prev->next = cur;
            else head = cur;
            delete toDelete;
            --length;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
}

Notes and cautions: ensure bounds checking in remove(index), keep length and head consistent, and always read next (or move cur) before deleting the node to avoid dangling pointers. The static wx workaround is fragile and unnecessary; either reverse-index removal or a single-pass pointer-based method is clearer, safer, and more efficient.

Recommended Answers

All 2 Replies

Member Avatar for Clinton Portis

This is what I am thinking...

Your loop condition is based on a=1 and will increment while a < size()+1.

for(int a=1;a<(S.size()+1);a++)

But my guess is.. your linked list is "zero based".. much like how an array is.. which would account for why all other elements would be deleted.. except for your very first one.. which is, "node zero" or the head node..

try this and see what happens:

for(int [b]a=0[/b]; a<S.size()+1; a++)
Member Avatar for TimC 
try this and see what happens:


 for(int [b]a=0[/b]; a<S.size()+1; a++)

Clinton thanks for the response. I tryed that but unfortunately it did not work. HOWEVER you got me thinking about the for loop and I came up with a solution.

What I forgot is.... when it comes to removing a node from a linked list the size of that linked list will automatically chage size. So on the question I asked above

for(int a=1;a<(S.size()+1);a++)
               {
               int x=S.retrieve_status(a);
                        if (x==5)
                        {
                        S.remove(a);
                        }
               }

If X==5, S.remove(a) would remove the node AND the size of the list S.size() would automatically change. This then caused complications with my for loop as size started to decrease and "a" was still being incremented.

this is the soloution I came up with and works fine.

static int wx=0;

for(int a=1;a<(S.size()+1+wx);a++)
               {
               int x=S.retrieve_status(a-(wx));
               if (x==5)
                              {
                             
                              S.remove(a-(wx));
                              wx++;
                              }
               }   
               
               wx=0;
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.