Home > front end >  How to use head while iterating through a linked list?
How to use head while iterating through a linked list?

Time:08-24

We are iterating through the linked list with the help of head, that is, we are updating our head as we move forward towards i th position. Please have a look at the fuction insertIthnode. I am inserting my Node at i th position are returning head - and it's still able to print the linked list. I don't know how? head is no longer pointing towards the first node then how is it still able to return a full linked list?

here's the code:

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *next;

  Node(int data) {
    this->data = data;
    next = NULL;
  }
};

int length(Node *head) {
  int x = 0;
  Node *temp = head;
  while (temp != NULL) {
    x  = 1;
    temp = temp->next;
  }

  return x;
}

void printIthnode(Node *head, int i) {
  int n = length(head);
  if (i < 0 || i > n - 1) {
    cout << -1 << endl;
    return;
  }
  int count = 1;
  while (count <= i) {
    head = head->next;

    count  ;
  }
  if (head) {
    cout << head->data << endl;

  } else {
    cout << "-1" << endl;
  }
}

Node *takeinput() {
  int data;
  cin >> data;
  Node *head = NULL;
  Node *tail = NULL;

  while (data != -1) {
    Node *n = new Node(data);
    if (head == NULL) {
      head = n;
      tail = n;
    } else {
      tail->next = n;
      tail = n;
    }
    cin >> data;
  }
  return head;
}

void PrintLL(Node *head) {
  Node *temp = head;
  while (temp != NULL) {
    cout << temp->data << " ";
    temp = temp->next;
  }
}

Node *insertIthnode(Node *head, int i, int data) {
  if (i < 0) {
    return head;
  } else if (i == 0) {
    Node *n = new Node(data);
    n->next = head;
    head = n;
    return head;
  }

  int count = 1;
  while (count <= i - 1 && head != NULL) {
    head = head->next;
    count  ;
    if (count == i - 1) {
      Node *n = new Node(data);
      n->next = head->next;
      head->next = n;
      return head;
    }
    return head;
  }
}
int main() {
  /*Node n1(1);
  Node *head=&n1;
  Node n2(2);
  Node n3(3);
  Node n4(4);
  Node n5(5);
  Node n6(6);

  n1.next=&n2;
  n2.next=&n3;
  n3.next=&n4;
  n4.next=&n5;
  n5.next=&n6;
  */
  Node *head = takeinput();

  insertIthnode(head, 3, 7);
  PrintLL(head);
}

CodePudding user response:

The problem is that you consider the Node as the linked list. While this is valid, the whole point of the linked list is that you don't lose track of the head. You could use two approaches:

  1. Don't iterate over the head. Instead, use a temporary reference to the head.
  2. Implement a Linked List wrapper. You can keep a constant reference to the head while performing operations over the node.

CodePudding user response:

In the main() function you are creating a head when you are taking input from the user with the help of the "takeInput()" function.

After that, you are calling the function "insertIthnode(head,3,7)" which is returning the head (since the return type is Node) but you are not receiving it in any variable so the head returned from the "insetIthnode" is lost.

Your original head remains the same as per of "takeInput()" function.

If you try to insert ith Node at Index 0 it won't print according to the inserted node.

CodePudding user response:

You pass head by value. Any changes you do to the variable receiving the value of head inside the functions are made to the local variable inside the function only and will not be visible from the call site.

Take your PrintLL function as an example:

void PrintLL(Node *head) { // head is here a local variable 
  Node *temp = head;
  while (temp != NULL) {
    cout << temp->data << " ";
    temp = temp->next;
  }
}

This could be rewritten without the extra variable temp. The name head doesn't make it the same head you used to call the function with:

void PrintLL(Node* head) {
  while (head != nullptr) {
    cout << head->data << ' ';
    head = head->next;
  }
}

and it would not affect the head you passed in as a parameter.

Similarly:

void foo(int x) {
      x;
    //
}

int main() {
    int x = 10;
    foo(x);
    std::cout << x << '\n'; // prints 10
}
  • Related