#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

// insert elements from the front
void push(Node** head_ref,int new_data)
{
	Node* new_node = new Node();
	new_node->data = new_data;

	new_node->next = (*head_ref);

	(*head_ref) = new_node;
}

//insert elements after a specific node
void insert_after(Node* prev_node,int new_data)
{
	if(prev_node==NULL)
	{
		cout<<"the previous node cannot be null";
		return;
	}

	Node* new_node = new Node();
	new_node->data = new_data;

	new_node->next = prev_node->next;
	prev_node->next = new_node;
}

//insert elements at last
void insert_last(Node* head,int new_data)
{
	Node* new_node = new Node();
	new_node->data = new_data;
	new_node->next = NULL;

	if(head == NULL)
	{
		head = new_node;
		return;
	}
	Node *cur = NULL;
	cur = head;

	while(cur->next!=NULL)
	{
		cur = cur->next;
	}
	cur->next = new_node;
}

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

int main()
{
	Node* head = NULL;

	insert_last(head,6);
	push(&head,7);
	push(&head,1);
	insert_last(head,4);
	insert_after(head->next,8);

	print_list(head);
	
	return 0;
}