Linked List C++

[jshm415]

Hello. I am studying this sample code for linked list class node implementation.
I've studied this code for hours and I am not 100% sure what certain parts of the code do.

Here are my questions:

1. Why is ptr NULL in the default constructor?

2. What does Node* next const do? I know it returns a pointer, but could you please elaborate more?

3. What is int done and what does it do?

4. What does Node::Node()do? Is this the head node? What is the difference between Node::Node and Node::Node(int tkey, Node* tnode)?

Below is what I know so far. If you think they are wrong, please feel free to correct me.

Thank you in advance.

  class Node
{
public:
  Node();                                       // constructor of class node without arguments
  Node(int, Node*);                           //constructor with arguments of int type and a pointer node type
  Node* next() const;                  
  void setNext(Node*);                        //member fun, returning a pointer of node type
  void setKey(int);
  int  getKey() const;
  int done;
private:
  Node* ptr;
  int key;
};

Node::Node()                            // constructor intialisation
{
  ptr = NULL;
  key = -1;
  done = 1;
}
Node::Node(int tkey, Node* tnode)                   // intialisation to private members
{
  ptr = tnode;
  key = tkey;
  done = 1;
}
Node* Node::next() const                                  
{
  return ptr;
}
int Node::getKey() const                                // returning the key to be inserted
{
  return key;
}
void Node::setNext(Node* tnode)                     // setting the link to next node in ptr
{
  ptr = tnode;
}
void Node::setKey(int tkey)                      // setting the value to be inserted in key {
  key = tkey;
}
  
void insert(Node* head, int key)                  // function taking the starting pointer of list and key to be inserted {
  Node* temp  = new Node(key, NULL);      // creating a new node by calling function  Node(int, Node*)
  Node* index;
  if(key < head->getKey())          // comparing the key to be inserted and present starting key of the list
    {
      index = new Node(key, head);     // if true, make the key to be inserted as the starting key
      head = index;                                 
      return;
    }
  index = head;
  while(index->next()!=NULL && index->next()->getKey() < key)       //else traverse the list until key to be inserted is greater than the values in the list.  
    {                                                                                               


 index = index->next();  // when found the place to insert the key, store the pointer in index.

 }   


temp->setNext(index->next());                                         // point temp->link to index.
  index->setNext(temp);
  return;
}
void printList(Node * head)                                          // print the list, starting form head of the list
{
  Node* index = head;                                              // storing value head in pointer index
  cout << index->getKey() << ", ";                             
  while(index->next()!= NULL)                       //till the end of list or index->next is not equal to NULL
    {
      index = index->next();                             //traversing node by node
      cout << index->getKey() << ", ";
    }
  cout << "\n";

[fg109]

1. The default constructor assigns the address NULL to the pointer because you haven't assigned any values yet, and it just makes sense.

2. In the implementation of a linked list, there are multiple nodes, each of which points to the next node in the list. So the node class has a function that gives you a pointer to the node that should come after itself.

3. No idea from the code you have posted. Nothing here checks the assigned value.

4. Node::Node() is the default constructor. The first Node is saying that the function belongs to the class Node. So it's the Node() function of the class Node. Node::Node(int tkey, Node* tnode) is the parametized constructor.

[jshm415]

Thank you for helping me out. I have just few more questions.

For 4, Node::Node (the default constructor) is setting the values for the first(head node) while Node::Node(int tkey, Node* tnode) is called in line 45 to make new nodes.

Is this right?

[fg109]

Not exactly...

No Node object knows whether or not it's the head node. The default constructor is used when a Node object is created without giving any parameters. The first node can be created with either the default or parametized constructor. Just know that any class needs to have a default constructor, and the person who wrote this code probably intended to only use the parametized constructor.

The insert() function is indeed used to make new nodes. It's supposed to insert the new data into an ordered list. The pointer to the head node is stored somewhere not shown in this code, and is provided as a parameter when this function is called. Although there is a problem with line 50. Changing the value of head in the function is not going to change the actual pointer to the head node, which is stored elsewhere.

[jshm415]

How does it exactly keep track of the head node?

Again, thank you for helping.