algorithm for finding a node in a linked list

Question

what is the algorithm used to write Snode* find and set& operator=( set &rhs) I just can't understand these two. I can read the code but I can't figure out why are they there. I can't understand the steps of the used algorithm. Things I already figured out: 1. Snode is a function that gets a value and returns the node with the same data.but what do prev and previous do and what is **previous and why ahould we create a pointer to a pointer? 2. set& operator= is for overriding the = operator. but I can't understand what does it do after overriding.and why should we swap the heads of temp and rhs sets. here's the code:

#include <iostream>
using namespace std;
struct Snode //Snode class defines a node in a list
{
 char data;//a node includes a character
 int count;//an integer to count the occurrence
 Snode *next = NULL;//and a pointer to the next node
 Snode(char data, Snode* next) : data(data), next(next) {}
};
class set
{
private:
 Snode *head;//first node in the list
 Snode *tail;//last node of the list
public:
 set() : head(NULL), tail(NULL)
 {
 }
 set( set &src) : head(NULL), tail(NULL)//copy constructor method
 {
 Snode *temp = src.head;//set head of the second list as temp to travers
 while (temp)//untill the end of the list
 {
 // insert(temp->data);
 Snode *newNode = new Snode(temp->data,NULL);//create a new node with the same data and count
 newNode->count = temp->count;
 //now puts it in the right place
 if (!head)//if head = NULL (if sset is empty)
 head = newNode;//set the new node as the first node
 if (tail)//if tail != NULL (if set isn't empty)
 tail->next = newNode;//set new node as the next node of current tail, so it'll be the tail
 tail = newNode;
 temp = temp->next;//does the same thing for all the nodes of the second list
 }
 }
 ~set()//destructor method
 {
 Snode *temp = head;
 while (temp)//traverse the list and delete each node
 {
 Snode *next = temp->next;
 delete temp;
 temp = next;
 }
 }
 set& operator=( set &rhs)
 {
 if (&rhs != this)
 {
 set temp(rhs);
 Snode *ptr = head;
 head = temp.head;
 temp.head = ptr;
 }
 return *this;
 }
 bool isAvailable(char value)//checks if any node with the same data exists or not
 {
 return (find(value) != NULL);//if find function can't find any, there's no same node
 }
 Snode* find(char value, Snode **previous = NULL)
 {
 if (previous)
 *previous = NULL;
 Snode *temp = head;
 Snode *prev = NULL;
 while (temp)
 {
 if (temp->data == value)
 {
 if (previous)
 *previous = prev;
 return temp;
 }
 temp = temp->next;
 }
 return NULL;
 }
 bool isFirst(char value)
 {
 return ((head) && (head->data == value));//if head's data is equal to value returns true
 }
 bool isLast(char value)
 {
 return ((tail) && (tail->data == value));//if tail's data is equal to value returns true
 }
 void display()
 {
 Snode *temp = head;
 while (temp)
 {
 cout << temp->data << " " << temp->count+1 << "\n";
 temp = temp->next;
 }
 }
 void insert(char value)//to insert a new value
 {
 Snode *temp = find(value);//if a node with the same data alreay exists
 if (temp)
 temp->count += 1;//increase the count by one
 else
 {
 temp = new Snode(value,NULL);//if if a node with the same data doesn't exist
 if (!head)//if list is empty
 head = temp;
 if (tail)//if list is not empty
 tail->next = temp;
 tail = temp;
 }
 }
 int count(char value)//count the nodes by the counter temp
 {
 Snode *temp = find(value);//travers the set
 return (temp) ? temp->count : 0;//if the list is empty return 0, else return the counter
 }
 void deleteFirst()//deletes the first node
 {
 if (head)//if list isn't empty
 {
 Snode *temp = head;
 head = head->next;//move the head forward
 if (tail == temp)//if loop faced the tail
 tail = NULL;
 delete temp;//delete the data
 }
 }
 void deleteLast()//delete the last node
 {
 if (head)
 {
 Snode *last = head;
 Snode *previous = NULL;
 while (last->next)//move forward untill the node before the last one
 {
 previous = last;
 last = last->next;
 }
 if (previous)//at the end of the list
 previous->next = NULL;
 tail = previous;
 if (head == last)//if there's only one node
 head = NULL;
 delete last;
 }
 }
 void remove(char value)//remove the node with the same data as the entry
 {
 Snode *previous;
 Snode *temp = find(value, &previous);
 if (temp)
 {
 if (temp->count > 1)
 temp->count -= 1;
 else
 {
 if (previous)
 previous->next = temp->next;
 if (head == temp)
 head = temp->next;
 if (tail == temp)
 tail = previous;
 delete temp;
 }
 }
 } };

• Stefan: Hi, I don't think your question is clear enough to get an appropiate answer. Can you try to pint point your question a bit more?
• Some programmer dude: What has merging two lists to do with the find and operator= functions? Please update your title to be a proper short summary of your problem. And please update your question to elaborate more on the problem you have, what you're wondering about, and why you're wondering. Also please try to create a Minimal, Complete, and Verifiable Example to show us.
• Stefan: If you skip the prev and previous, the find function must be pretty clear to you. The previous suggests some sort of being part of a recursive call, but it isn't. Contact the author and ask what that's all about. As for now these 2 variables have no meaning, besides that the inputted previous pointer is set to NULL
• Scheff's Cat: The previous parameter of set::find() returns the pointer to previous node of the found node (if a non-nullptr address of a pointer to Snode is passed). This is used in set::remove(). It's pointer to pointer to make its use optional. (as it is usually done in C. In C++, I would've solved this slightly different: providing two find() methods - one with the Snode *&previous, and the other as wrapper without, which calls the former.)
• Scheff's Cat: The set::operator=() uses the copy constructor which makes a deep copy of rhs. The swapping between this and temp is responsible to let temp delete the old contents of this when it goes out of scope. However, as already suspected by Stefan I believe as well it is broken. Neither tail of temp nor tail of this is considered.

Answer 1

As you have guessed, find tries to locate a Snode containing the required character. If only that is required, you can ignore the previous parameter (it will be NULL), and previous/prev processing will just be useless.

But find is used in remove... In order to remove a node in a singly linked list, you must have the previous one point to the next one. So you must browse the list keeping a track of the previous node. That is exactly the way it is used in remove with:

 if (previous)
 previous->next = temp->next;

The assignment operator uses a close variant of the copy and swap idiom. But as the destructor only uses the head member, only that member is swapped: that will be enough to have the destructor of temp to destroy all nodes of the original list.

Simply tail should be set in this even if it is useless to set it in tmp. A correct implementation could be:

set& operator=( set &rhs)
{
 if (&rhs != this)
 {
 set temp(rhs);
 Snode *ptr = head;
 head = temp.head;
 temp.head = ptr;
 tail = temp.tail; // no need for a full swap here
 }
 return *this;
}

• nitwit: @sergeballeeta that's it! They're used in remove. Thanks
• Scheff's Cat: But as the destructor only uses the head member, only that member is swapped: that will be enough to have the destructor of temp to destroy all nodes of the original list. For all that, it will leave the tail of this in wrong state after assignment (i.e. point to a node which is destroyed or leaving it nullptr when it shouldn't), won't it?
• Serge Ballesta: @Scheff: Of course you are right! I had not noticed that tail for completely off... Post edited