I sort of understand the use of &(*front)->next which would mean the address of the actual front pointer's next node, I'm not sure. Also, the function works to remove a node at front or somewhere else, BUT when I'm trying to find a non-existent node, the program crashes.
struct sll_node//singly linked list node
{
string date;
sll_node *next;
};
sll_node* r_remove(string node_data, sll_node** front, sll_node* prev_)//returns updated list (so front ptr) or NULL (reached end of list and not found)
{
sll_node* prev = prev_;
sll_node* cur = *front;//pts to what front ptr points to initially
if ( prev == NULL && cur == NULL ) return NULL;//Base case:if empty list
elseif ( cur->data == node_data && prev == NULL )//base case: else if node to remove is first node, update front to point to next node in line
{
*front = (*front)->next;
delete cur; cur = NULL;
return *front;
}
// if we find node to remove somewhere else, return updated list (=>return ptr front (front pts to list)
//node could either be first node or somewhere else in list (need to update relink w/ prev and delete cur)
elseif ( cur->data == node_data && prev != NULL )
{
prev->next = cur->next;
delete cur; cur = NULL;
return *front;
}
//if EOL (reached end of list), => node not on list since we always compare w/ cur ptr and once cur pts to NULL, of course no more items to compare with!
elseif ( cur == NULL && prev != NULL ) return NULL;
elsereturn r_remove(node_data, &(*front)->next, *front);//keep traversing
}
int main()
{
sll_node *front = NULL;
sll_node *end = NULL;
insert_at_end("j", &front, &end);//I have this working
insert_at_end("d", &front, &end);
insert_at_front("h", &front);//I have this function working
insert_at_front("g", &front);
if ( !r_remove("jad", &front, NULL) )
cout << "No node found to be removed" << endl;
else
cout << "Removed" << endl;
return 0;
}
Why are you complicating things with pointer to pointer to a node? This line *front = (*front)->next; for example would be front = front->next; if front was just a pointer to a node.
It looks like you are actually making two lists, one named front and one named end, they do not appear to be connected in any way. Also in the remove function prev doesn't point to the previous node which is necessary to remove a node in a singly linked list. I would also suggest doing the remove iteratively if possible, it is usually faster and definitely easier to follow.
I thought we need to use a pointer to a pointer whenever we need to modify the original pointer and since I want the actual front pointer (i.e. from the singly linked list declared in main), I need to repoint that front pointer.
Here is the my insert_at_end (I've tested it and works):
=======================================
void insert_at_end(string node_data, sll_node **front, sll_node **end)tr
{
sll_node *newNode = new sll_node;
newNode->data = node_data;
newNode->next = NULL;
//If list is empty, then head and tail pts to the newNode
if ( *front == NULL && *end == NULL )
{
*front = newNode;
*end = newNode;
}
//Else the list is not empty, so just update tail ptr and leave head ptr alone!
else
{
(*end)->next = newNode;
*end = newNode;
}
}
Here is my insert_at_front (I've tested it and it works btw):
==========================================
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
void insert_at_front(string node_data, sll_node **front)
{
sll_node *newNode = new sll_node;
newNode->data = node_data;
//If our list is empty, then make front ptr just point to node newNode
if ( *front == NULL )
{
newNode->next = NULL;
*front = newNode;
return;//BAD PRACTICE as it could be easily missed but I jus want to use it for small code (SO use if-else instead)
}
newNode->next = *front;
*front = newNode;
}
I don't understand is b/c I have pointer cur always pointing to the node to remove, and prev is used to relink w/ cur's next node, so once pointer cur points to end of list which is NULL, it should return NULL.