11 Replies - 2239 Views - Last Post: 17 September 2009 - 12:48 AM Rate Topic: -----

#1 ellimist   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 14-September 09

Seg Fault in a linked list

Posted 16 September 2009 - 07:28 PM

My program was working fine and all my functions work accept this one.

 
		bool found = false;
		int searchValue;
		cout << "Please enter the employee's ID";
		cin >> searchValue;
		node *nodePtr, *previousNode;
		 
		// If the list is empty, do nothing.
		if (!start_ptr)
				return;
		
		// Determine if the first node is the one.
		if (start_ptr->emp.ID == searchValue)
		{
				nodePtr = start_ptr->nxt;
				delete start_ptr;
				start_ptr = nodePtr;
				found = true;
		}
		else
		{
				// Initialize nodePtr to head of list
				nodePtr = start_ptr;
				
				// Skip all nodes whose value member is
				// not  equal to searchValue.
				while (nodePtr != NULL && nodePtr->emp.ID != searchValue)
				{
						previousNode = nodePtr;
						nodePtr = nodePtr->nxt;
				}
				// If nodePtr is not at the end of the list,
				// link the previous node to the node after
				// nodePtr, then delete nodePtr.
				if (nodePtr->emp.ID == searchValue)
				{
						previousNode->nxt = nodePtr->nxt;
						delete nodePtr;
						found = true;
				
				}
		}
		if (found == false)
		  cout << "ID not found";




I keep getting hit with a seg fault. Just seeing if a fresh set of eyes can find my mistake

Is This A Good Question/Topic? 0
  • +

Replies To: Seg Fault in a linked list

#2 poncho4all   User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,422
  • Joined: 15-July 09

Re: Seg Fault in a linked list

Posted 16 September 2009 - 07:34 PM

1. When do you get the segmentation fault, meaning in wich condition?
2. Is it a double linked list?
3. What does the segmentation fault says.

[EDIT]nodePtr is never gonna be Null, but nodPtr->nxt is so change this line
 while (nodePtr->nxt != NULL && nodePtr->emp.ID != searchValue)

This post has been edited by poncho4all: 16 September 2009 - 07:37 PM

Was This Post Helpful? 0
  • +
  • -

#3 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,233
  • Joined: 14-September 07

Re: Seg Fault in a linked list

Posted 16 September 2009 - 07:35 PM

Here's how i wrote a search function for a linkedlist project I'm working on:

template<class T>
bool LinkedList<T>::contains(T element){
	//O(n) search
	curNode = head;
	while(curNode != NULL){
		if(curNode->getData() == element){
			return true;
		}
		curNode = curNode->getNext();
	}
	return false;
}



Pseduo algorithm:

set your iterator (usually a temp ptr or some other handle) equal to head
check the data
if found, delete ptr and return (mine only returns ifFound)
else temp ptr is passed the address of the curNode's->next value
loop


As for the seg fault, your comments here:

// If nodePtr is not at the end of the list,
				// link the previous node to the node after
				// nodePtr, then delete nodePtr.
				if (nodePtr->emp.ID == searchValue)
				{
						previousNode->nxt = nodePtr->nxt;
						delete nodePtr;
						found = true;
			   
				}



indicates that this should NOT occur if its the end of the list. There is no check for that.
Was This Post Helpful? 0
  • +
  • -

#4 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,233
  • Joined: 14-September 07

Re: Seg Fault in a linked list

Posted 16 September 2009 - 08:01 PM

Apologizes for a double post, but i wanted to share this code snippet with you. I wasn't going to write this for my little tutorial pet project until tomorrow, but since it was relevant, here is how I approached the problem:

template<class T>
void LinkedList<T>::removeNode(T element){
	Node<T>* temp, *previous; //we'll need these later
	curNode = head; //default assignment
	//O(1) check (head node)
	if (head->getData() == element) { //remove head
		head = head->getNext();
		delete curNode;
		cout << element << " was the head node, it was successfully removed" << endl;
	}
	else {
		while(curNode != NULL){
			//check data
			if(curNode->getData() == element){
				temp = curNode->getNext();
				if (temp == NULL){
					previous->setNext(NULL);
				}
				else{
					previous->setNext(temp);
				}
				delete curNode;
				curNode = temp;
				size--;
				cout << element << " a non head node, was successfully deleted!" << endl;
				break;
			}
			else {
				previous = curNode;
				curNode = curNode->getNext();
			}
		}
	}
}




EDIT: I had a dangling pointer issue, its resolved now. If the item in question is the tailnode, we want to set the previous node's next to NULL. If the element in question is in between two nodes (anything but the head or tail), we want to set previous' next to the element that matched's next.

This post has been edited by KYA: 16 September 2009 - 08:06 PM

Was This Post Helpful? 0
  • +
  • -

#5 poncho4all   User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,422
  • Joined: 15-July 09

Re: Seg Fault in a linked list

Posted 16 September 2009 - 08:08 PM

That's pretty cool. What is the size-- doing?
Was This Post Helpful? 0
  • +
  • -

#6 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,233
  • Joined: 14-September 07

Re: Seg Fault in a linked list

Posted 16 September 2009 - 08:09 PM

To get the size of a list you could iterate through it to get a total, but that's a O(n) operation. Using an int (size) I simply initialize it to zero when the list is made, increment when a node is added, and decrement when one is taken away. Then I simply call that number in the getSize() function, which is now a constant O(1) evaluation.


It also functions as a really cheap memory leak detector. If the value of size isn't zero after the destructor is called (I actually call for size at the end after freeing all of the list's memory), then there is some memory leaking. :)

This post has been edited by KYA: 16 September 2009 - 08:11 PM

Was This Post Helpful? 0
  • +
  • -

#7 ellimist   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 14-September 09

Re: Seg Fault in a linked list

Posted 16 September 2009 - 08:22 PM

Is there anyway you can read the code I posted and tell me what might be wrong with it.
Was This Post Helpful? 0
  • +
  • -

#8 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,233
  • Joined: 14-September 07

Re: Seg Fault in a linked list

Posted 16 September 2009 - 08:35 PM

You iterate with the while loop, but only break if the element is found and then you do a conditional check. Why not just do it inside the while loop? Saves a step and gets rids of any problems with the tail node. Check out what I posted for guidance.


There's no guarantee that the node in question isn't the last node. It would really help if I could see what you created with the list, what you appended (if anything) and what you're trying to remove.

This post has been edited by KYA: 16 September 2009 - 08:35 PM

Was This Post Helpful? 0
  • +
  • -

#9 ellimist   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 14-September 09

Re: Seg Fault in a linked list

Posted 16 September 2009 - 08:48 PM

Tried it. And it's really nothing too hard. The list looks something like:

1001 Hulin,Seth 2252764669 19
1003 Philley,Erin 2252025136 24

etc.

The ID, name, phone number, and age are each in a struct withing the node. I'm just trying to search by ID then delete that employee. It was working fine not long ago. I don't know what I messed with but now it won't work. I printed out my head pointer and it's in the right spot and my logic makes perfect sense so I don't know I'm getting a seg fault
Was This Post Helpful? 0
  • +
  • -

#10 learnplaycreate   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 119
  • Joined: 27-August 09

Re: Seg Fault in a linked list

Posted 16 September 2009 - 09:40 PM

i just struggled through a deleting nodes in a linked list problem my-self.
the fix i found was to account for three possibilities
if the node to be deleted was the head of the list, you need to set the second node as the head of the list
e.g
list * to_del
list * temp
list *node_before_to_del;

//locate node to del
if (to_del=head)
temp = to_del;
head = to_del->next;
to_del = head;					   //not sure if this is necessary but it's better to be safe then to have a seg fualt
delete temp; 


if the node is the last node you need to set the second last nod as te last node
temp = to_del;
node_before_to_del->next=NULL;
to_del = head;					   //not sure if this is necessary but it's better to be safe then to have a seg fualt
delete temp;


if the node to delete is neither first or last
temp = to_del;
node_before_to_del->next=to_del->next
to_del=to_del->next;			   //not sure if this is necessary but it's better to be safe then to have a seg fualt
delete temp;


all three possibilities need to be taken into account or you are in grave danger of getting a segnemtation fualt, i think your problem is that you didn't take all three possibilities into account. i had heaps of problems learning this, but i think i've got it now. if your still stuck, post your entier code and i'll have a look at it tonite. this is for a list with a one way link, i you have both next, and prev links you'll have to adjust the prev as well, this will add extra code to each of the possibilities, if it's a circular list, i don't really know but i think there really is no end so you will have to only look at the other two option.
PS. i'm in Australia so when i say tonite i mean in about 8 - 10hours, I'm at work at the moment so i really can't do much more at the moment.

This post has been edited by learnplaycreate: 16 September 2009 - 09:44 PM

Was This Post Helpful? 0
  • +
  • -

#11 ellimist   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 32
  • Joined: 14-September 09

Re: Seg Fault in a linked list

Posted 16 September 2009 - 11:12 PM

That totally makes sense man. I can't try it out right now by it definitely makes sense. But just a question: is there a reason only declaring 2 cases (key being the first node then key being any other node) would work in all my other routines (printing out just one node, updating the info on a specific node ) but then wouldn't work for the delete? The only reason I ask is because I did it like that (only declaring 2 cases) in all my other routines and they work beautifully. It's just the delete that's hitting me with a seg fault
Was This Post Helpful? 0
  • +
  • -

#12 learnplaycreate   User is offline

  • D.I.C Head

Reputation: 7
  • View blog
  • Posts: 119
  • Joined: 27-August 09

Re: Seg Fault in a linked list

Posted 17 September 2009 - 12:48 AM

i believe (and that should not be considered definitive as i only recently learned linked lists and i struggled with the deleting of a node.) the difference between all the other operations on a linked list and deleting a node on a linked list, is that when your just searching for a particular node and modifying it in some way, or printing it, there is no need to change the structure of the list i.e. all the pointers stay pointing to the same thing they were before the modification. when you add a node to the end of the list all that needs to change is the pointer of the previous last node changes to point to the last node. when deleting a node different changes to the list structure are required for the following different case,delete first node,delete last node,delete any other node. if there are not possibilities for all three cases the wrong changes will be applied in the case that is neglected which will result in a seg fault. see my post above to see what the differences are between the 3 different cases.

hope this was helpful

This post has been edited by learnplaycreate: 17 September 2009 - 12:55 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1