3

I am going through some tutorials, this one in particular is for linked lists and I am facing a roadblock here, I got:

#include<iostream>
#include<stdlib.h>
using namespace std; 


    struct Node{
        int data;
        Node *next;
    };
    
    Node *tail, *head;  
    
    class singly{
    
        public:
        
            singly(){
                
                head = NULL;
                tail = NULL;
            }
            
            
            void deletenode(struct Node **head_ref, int key){
                
                struct Node *temp = *head_ref, *prev;
                
                if(temp != NULL and temp -> data == key){
                    
                    *head_ref = temp -> next; 
                    free(temp);
                    return;
                }
                
                while (temp != NULL && temp -> data != key){
                    
                    prev = temp;
                    temp = temp -> next;
                }
                
                if(temp == NULL) return;
                
                prev -> next = temp -> next;
                free(temp);
            }
    };

int main{}

my issue in understanding this piece of code is the deletenode function, in particular with the way struct is used, first, what is the meaning of defining struct Node **head_ref?, second, what in itself is happening with?:

struct Node *temp = *head_ref, *prev;

as such I am not sure what is the relationship between *head_ref, *prev, *temp, and further down the code

*head_ref = temp -> next;

and

prev = temp;

make little sense to me because of this. What I am missing?

Salamander
  • 31
  • 2
  • The `**head_ref` is a (slightly confusing) way to ensure that when the `head` is deleted, that one would be able to change the pointer to the next element, by value. It is equivalent to declaring a `struct list { node *head; }`, but much more confusing. – Neil Oct 03 '22 at 00:03
  • 2
    `deletenode(&head, 1234);` if &head is passed then head can be updated, that would happen if the first node had data==1234. To update a pointer you need a pointer to the pointer hence `Node **head_ref` – QuentinUK Oct 03 '22 at 00:18
  • 1
    Fwiw, the unusual handling in that function is overkill. You can just as easily walk the list with `head_ref` if you do it right. Unrelated, this looks like you sniped a C implementation of a head+tail single linked list and have 1/3rd ported it to C++. That isn't helping matters much. Neither `head` nor `tail` should be globals; they should me members of `singly`. And you almost-certainly shouldn't be using `free` (which suggests somewhere else you're almost-certainly using `malloc`). – WhozCraig Oct 03 '22 at 00:29
  • 3
    Whichever tutorial taught you to use `free` in C++ code -- delete the bookmark and don't use this so-called "tutorial" again. Forget everything you learned from this "tutorial". It is not teaching you proper C++. Start over with a different tutorial, or a good C++ textbook. Although it appears to be safe to use here, using `malloc` and `free` in C++ code will eventually end in tears. – Sam Varshavchik Oct 03 '22 at 00:55
  • @WhozCraig just fallowing the tutorial, but yeah, having implemented single linked lists before in c++ this did felt super weird, also not using malloc anywhere else in the rest of the code... I am not continuing that tutorial, but it does bother me I don't quite understand how this is working anyways. – Salamander Oct 03 '22 at 01:14
  • @SamVarshavchik yup I can see that, any good text book you can recommend? was hoping for some slighly more advanced c++ than what I knew before, but I suppose this tutorial is all bullsh**. – Salamander Oct 03 '22 at 01:17
  • 1
    See [Stackoverflow list of curated textbooks](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Oct 03 '22 at 01:24
  • If you can't get your hands on a book just yet, have a look at "learncpp.com" its pretty decent. Also note that in C++ you probably would be using std::list from instead of writing your own code like that. That code is more indicative of "learning datastructures using C++" (with datastructures requiring a lower level kind of coding then higher level C++ which is used more nowadays) – Pepijn Kramer Oct 03 '22 at 04:49
  • It is not bad to learn data structures. Every programmer should know the implementation of the basic ones. But it can be confusing to learn the programming language at the same time, even more so with code, which is neither real C nor real C++. Apart from that this is mostly C code. – Sebastian Oct 03 '22 at 07:11
  • For accessing the linked list you would store a pointer to the head and go from node to node. To enable the delete_node function to also delete the head node it expects a pointer to this pointer to the head to be able to exchange it with the second node in case. temp and prev are declared in one line. They are independent. temp is initialized, prev not. The code goes through the linked list and keeps the current node as temp and the previous node as prev. So most of the time `temp==prev->next`. – Sebastian Oct 03 '22 at 07:21
  • The first if block handles the case the key is in the head node and returns at the end. The while block goes over all nodes, which are not the key. The second if block handles the case, if the key was not found. The final code removes the node from within the linked list. Only the first occurrence of a node with the key is deleted. – Sebastian Oct 03 '22 at 07:21
  • For multiple variable declaration in one statement see also https://stackoverflow.com/questions/6838408/how-can-i-declare-and-define-multiple-variables-in-one-line-using-c https://stackoverflow.com/questions/67801305/value-assignment-in-c-while-declaring-multiple-variable-in-1-line https://stackoverflow.com/questions/35877190/how-to-initialize-multiple-variables-in-c-to-the-same-value – Sebastian Oct 03 '22 at 07:28

0 Answers0