Linked list

[rwill357]

My assignment was to write code to Delete an ith node on a linked list. Will this function accomplish that?

void deleteIthNode(int el){
	IntSLLNode *tmp;                         
	tmp = (IntSLLNode*)malloc(sizeof(IntSLLNode)); 
	tmp = head;                  
 
	IntSLLNode *oldTmp;                     
	oldTmp = (IntSLLNode*)malloc(sizeof(IntSLLNode));   
	oldTmp = tmp;
		for( int i = 1 ; i < i-1 ; i++ )
	{
      oldTmp = tmp;                    
	  tmp = tmp->next;                 
 
	}
	oldTmp->next = tmp->next;  
	free(tmp);
	}

[mrnutty]

This code causes a memory leak.

IntSLLNode *tmp;                         	
tmp = (IntSLLNode*)malloc(sizeof(IntSLLNode));
tmp = head;

So does this code :

IntSLLNode *oldTmp;                     	
oldTmp = (IntSLLNode*)malloc(sizeof(IntSLLNode));   	
oldTmp = tmp;

[Narue]

>Will this function accomplish that?
Oh, dear.

>tmp = (IntSLLNode*)malloc(sizeof(IntSLLNode));
Why are you allocating memory? This function deletes nodes.

>tmp = head;
Bye bye memory. Now you've lost your only pointer to the memory you just allocated. That's what we call a memory leak.

>oldTmp = (IntSLLNode*)malloc(sizeof(IntSLLNode));
>oldTmp = tmp;
I see a trend here. You've learned the lesson that pointers must point somewhere before being used, but because tmp is already a pointer that points somewhere, you can copy it into oldTmp and all is well. The whole allocation thing only matters when you start with nothing.

>for( int i = 1 ; i < i-1 ; i++ )
Um...what? i is never going to be less than 1 minus itself. But let's assume your loop isn't nonsensical for a moment:

for ( int i = 0; i < el; i++ )
{
  oldTmp = tmp;                    
  tmp = tmp->next;   
}

What happens when el is greater than the size of the list?

>oldTmp->next = tmp->next;
Looks risky to me.

>My assignment was to write code to Delete an ith node on a linked list.
Then you need to seriously consider a few critical cases:

• The list is empty.
• The selected index is the first node in the list.
• The selected index is the last node in the list.
• The selected index is bogus.
• The selected index is valid and not an edge case.

Review your algorithm and see for yourself if it covers all of those cases. (Hint: It doesn't)

[rwill357]

I have ammended my code is this closer to what I'm trying to do.

IntSLLNode* deleteIthNode(IntSLLNode *head, int info)
{
IntSLLNode *tmp = NULL;
IntSLLNode *prev = NULL;

for(tmp = head; tmp != NULL; prev = tmp, tmp = tmp->next)
{
if(tmp->info == info)
{

if(prev == NULL)
{
head = head->next;
free(tmp);
return head;
}

prev->next = tmp->next;
free(tmp);
return head;
} 
}
return head;
}

[Narue]

>is this closer to what I'm trying to do.
No, it's completely different. You're deleting a node with matching info , not the ith node. But your logic is better in this one, you can modify it to do what you want.

By the way, you should be testing and debugging your own code. If you're just typing up code and asking us if it's correct, that's not going to get you very far.

[rwill357]

I have made some adjustments but I'm still having issues with the following :
edge cases for deleteIthNode function
printall function

#include<iostream>
#include <assert.h>
#include<stdio.h>
#include<conio.h>

using namespace std;

 class IntSLLNode {
public:
    int info;
    IntSLLNode *next;
    IntSLLNode() {next = 0; }
    IntSLLNode(int el, IntSLLNode *ptr = 0) {
	info = el; next = ptr;
    }
};

class IntSLList {
public:
	IntSLList() {
		head = tail = 0;
	}
	
	void addToHead ( int el){
		head = new IntSLLNode(el, head);
		if (tail ==0)
			tail = head;
	}

	void addToTail(int el) {
	 if (tail !=0)
		{
			tail->next = new IntSLLNode(el);
			tail = tail ->next;
		}
	 else 
		head = tail = new IntSLLNode (el);
	}

	int deleteFromHead(){
		assert(head!=0);

			int el = head -> info;
			IntSLLNode *tmp = head;
			if (head == tail)
				head = tail = 0;
			else 
				head = head -> next;
		   delete tmp;
			
			return el;
		
	}
   
	int deleteFromTail (){
		int el = tail->info;
		if (head == tail) {
			delete head;
			head = tail = 0;
		}
		else {
			IntSLLNode *tmp;
			for (tmp = head; tmp->next != tail; tmp=tmp->next);
			delete tail;
			tail = tmp;
			tail->next =0;
		}
		return el;
	}
	int deleteIthNode(int i)
{
	IntSLLNode *tmp,*prev;
		
	if (head == tail)
		head = tail = 0;
			
	tmp = head;                  
	prev = tmp;

		for( int c = 1 ; c < i-1 ; c++ )
	{
   	  prev = tmp;                    
	  tmp = tmp->next;                 
 
	}
	prev->next = tmp->next; 
	delete(tmp);
	return i;
}

  void printALL(IntSLLNode *p)
  { 
  if(p == NULL)
		printf("\n Empty Linked List\n");
  else {
		while(p != NULL)
		{

	//printf("\n%d\",p->info,p->next);
    p = p->next;
		}
		printf("\n ");

       }
  }
private:
	IntSLLNode *head, *tail;
};


int main() {
   IntSLList list1, list2, list3;
  /*write the codes to add some nodes by using addtoTail function*/
 
   
		list1.addToHead(3); 
        list1.addToHead(2); 
        list1.addToHead(1); 
        list1.addToTail(4); 
 
        //list1.printALL(); 

		list2.addToHead(3); 
        list2.addToHead(2); 
        list2.addToHead(1); 
        list2.addToTail(4); 
 
        //list2.printALL();

		list3.addToHead(3); 
        list3.addToHead(2); 
        list3.addToHead(1); 
        list3.addToTail(4); 
 
        //list3.printALL();
 
        //int err = list1.deleteIthNode(2); 
 
        cout<<"deleting node "<<endl; 
        //list1.printALL(); 
 
        return 0;
   
   //list1.deleteIthNode(2);
   cout<<"deleting node "<<endl;
   //list1.printAll();
   
		system ("PAUSE");

  
   return 0;
}

[Lerner]

I noticed you have commented out all the calls to display(). I suspect that's because when you try to display the lists you don't get what you expect because the addToHead() function is wrong and all the lists you create in main() use addToHead(). You always assign the new node to head, but you pay no heed to what head may already be pointing to. Therefore, after you call addToHead() the list will contain just a single node, head, since you can no longer access the memory for any other node previously since head->next will always be NULL.

addToHead(int el)
  //create node to add
  IntSLLNode *tmp = new IntSLLNode(el);
 
  //if empty list
  if(head == NULL)
     head = tail = tmp;
  else //if not empty node
     tmp->next = head; //now tmp is temporarily the first node
     head = temp; //now head is first node again and head->next points to the second node in the list (which was the first node in the list until the previous line)

Before moving on be sure you understand the above logic. Logic to delete the ith node could go something like this:

if empty list
   cout << "empty list";
else 
   //find ith node, if you can
   int counter = 1;
   tmp = head->next;
   prev = head
   while(tmp != tail && counter < i)
      prev = tmp
      tmp = tmp->next;
   //now check to see why loop ended
   if counter != i //ith node not found
     cout << list isn't i nodes long
   else //ith node found
     if(i == 1)
        //delete first node in list
     else if(tmp = tail)
       //delete last node from list
     else 
       //delete from interior of list using tmp and prev