A remove_duplicates() function in my linked list class: Is this right?

[Jamin2112]

I'm making a generic linked list class. For reference, firstNodePtr and lastNodePtr are pointers to the nodes at the beginning and end of the list. I'm trying to make a function that removes duplicate elements, which in turn calls a function for deleting a particular node. I think it does what I want (or does it?) but I also feel like this is overly complicated and I could simplify it somehow. Thoughts?

template <class T> void List<T>::remove_duplicates() {
	std::set<T> thisSet;
	node* curNodePtr = firstNodePtr;
	while (curNodePtr) {
		if (!thisSet.count(curNodePtr->val)) {
			thisSet.insert(curNodePtr->val);
			curNodePtr = curNodePtr->next;
		} else { 
			node* curNodePtrCopy = curNodePtr;
			curNodePtr = curNodePtr->next;
			delete curNodePtrCopy;
		}
	}
	
}

template <class T> void List<T>::remove_node(node* thisNodePtr) {
	if (thisNodePtr == firstNodePtr) {  
		firstNodePtr = firstNodePtr->next;
	} else { 
		node* prevNodePtr = firstNodePtr;
		while (prevNodePtr->next != thisNodePtr)
			prevNodePtr = prevNodePtr->next;
		prevNodePtr->next = thisNodePtr->next;
		if (thisNodePtr == lastNodePtr)
			lastNodePtr = prevNodePtr;
	}
	delete thisNodePtr;	
}

 

[.Scott]

The obvious problem is that you have no efficient way of backing up through the list. When you code to remove "thisNodePtr", you're stuck having to return to the start of the list and search forward through each preceding node.

There are basically two ways of doing what you're looking to do. The most obvious is to create and maintain two node pointer per node - not just Next, but Next and Previous.

The other way is to code a "remove_next_node" instead of a "remove_node". The parameter would be a pointer to the node before the node to be deleted. If you do that, use a null value for your input pointer when you want to remove the first node. Also, check for the last node being passed - since the "Next" pointer on that node is null because there's no "Next" after the last node.

 

[voko]

Just for the record, the current implementation of remove_duplicates() does not call remove_node(). Instead it does something very bad: it deletes nodes without unlinking them from the list.

If you intend to call remove_node() from that place, it will be quite inefficient, because for each removed node the list is rescanned from the beginning.

One way to deal with that is by maintaining a pointer to the previous node - not in the list, but in remove_duplicates().

 

[Jamin2112]

Thanks, guys. I think I've made all the necessary fixes.