Problem with linked lists

[gaurav97]

#include <iostream>
#include <stdlib.h>

using namespace std;

struct node
{
  int data;
  struct node *next;
}

void push(struct node **ref, int n)
{
  struct node *ptr=(struct node*)malloc(sizeof(struct node));
  struct node *ptr2=(struct node*)malloc(sizeof(struct node));
  ptr=*ref;
  ptr2->data=n;
  ptr2->next=NULL;
  if(ptr==NULL)
    ptr=ptr2;
  else
  {
    while(ptr!=NULL)
      ptr=ptr->next;
    ptr=ptr2; 
  }
}

int main()
{
  struct node *head=NULL;
  int tc; cin>>tc;
  while(tc--)
  {
    int n; cin>>n;
    push(&head, n);
  }
  return 0;
}

What is the problem with this code for insertion of elements at the end of a linked list ?
It is giving me an execution timeout error.

[Thomas1965]

Do you have to write your own?
In case you haven't heard of std::list https://www.geeksforgeeks.org/list-cpp-stl/

[Manga]

line 10 needs a ; at the end.

[tpb]

You are writing mostly in C, not C++.

In C++:
* use 0 instead of NULL; use nullptr if C++11 or better.
* use new instead of malloc
* use references instead of passing an address
* don't say "struct Node" when making a Node; just say "Node"
* Use a "constructor" to create objects

The following is only a taste of what you could do.

#include <iostream>
using namespace std;

struct Node {
    int   data;
    Node *next;

    // constructor (with default 0 pointer for nx)
    Node(int dt, Node *nx=0) : data(dt), next(nx) {}
};

void push(Node *&head, int n) {  // head is a reference to a Node*
    Node *nd = new Node(n);   // call the constructor to create the node
    if (!head)
        head = nd;
    else {
        Node *p = head;
        while (p->next)
            p = p->next;
        p->next = nd;
    }
}

void print(Node *&nd) {
    while (nd) {
        cout << nd->data << ' ';
        nd = nd->next;
    }
    cout << '\n';
}

int main() {
    Node *head = 0;

    int tc;
    cin >> tc;

    while (tc--) {
        int n;
        cin >> n;
        push(head, n);
    }

    print(head);
}

[uplime]

why do you allocate a node for ptr, but then assign it the value of ref?

[Manga]

@tpb

I see new being used, but no delete... and no destructor either.
I don't feel comfortable with this.

[tpb]

@Manga, good point. I totally forgot about that.
A dtor would need to work recursively (and not using tail-recursion, either), which I don't like for a list (what if it had millions of elements?) so I suppose a delete_list function is best. It's still very C-like, though. A C++ list would have a List object to hold the nodes. I don't know how far the OP wants to go. He seems to really only know C (and not much of that).

#include <iostream>
using namespace std;

struct Node {
    int   data;
    Node *next;

    // constructor (with default 0 pointer for nx)
    Node(int dt, Node *nx=0) : data(dt), next(nx) {}
};

void push(Node *&head, int n) {  // head is a reference to a Node*
    Node *nd = new Node(n);   // call the construtor to create the node
    if (!head)
        head = nd;
    else {
        Node *p = head;
        while (p->next)
            p = p->next;
        p->next = nd;
    }
}

void print(Node *nd) {
    while (nd) {
        cout << nd->data << ' ';
        nd = nd->next;
    }
    cout << '\n';
}

void delete_list(Node *&nd) {
    while (nd) {
        Node *tmp = nd->next;
        delete nd;
        nd = tmp;
    }
}

int main() {
    Node *head = 0;

    int tc;
    cin >> tc;

    while (tc--) {
        int n;
        cin >> n;
        push(head, n);
    }

    print(head);

    delete_list(head);
}

[jonnin]

pushing onto the end of a list? /shudder

1
2,1 //push 2, new node, node -> next = head, head = new ... no loop to find end
3,2,1 ...
making pop just tmp = head, head = head-> next, delete tmp, no loop to find end
and so on.

You are making your code slower AND more complex to write.

[tpb]

I didn't think about the name "push" which doesn't make sense to add to the end. I just assumed that's what the OP wanted to do.

"Pushing" to the front instead:

#include <iostream>
using namespace std;

struct Node {
    int   data;
    Node *next;

    Node(int dt, Node *nx=0) : data(dt), next(nx) {}
};

void push(Node *&head, int n) {
    head = new Node(n, head);
}

int pop(Node *&head) {
    if (!head) return 0;  // or do whatever
    int data = head->data;
    Node *next = head->next;
    delete head;
    head = next;
    return data;
}

void print(Node *nd) {
    while (nd) {
        cout << nd->data << ' ';
        nd = nd->next;
    }
    cout << '\n';
}

void delete_list(Node *&nd) {
    while (nd) {
        Node *tmp = nd->next;
        delete nd;
        nd = tmp;
    }
}

int main() {
    Node *head = 0;

    int tc;
    cin >> tc;

    while (tc--) {
        int n;
        cin >> n;
        push(head, n);
    }

    print(head);

    while (head)
        cout << pop(head) << ' ';
    cout << '\n';

    // delete_list(head); // list is already empty
}