#include <iostream>
using namespace std;
#pragma once

namespace task6 {

	struct Node
	{
	public:
		int key;
		Node* next;
	};

	Node* newNode(int key); 
	Node* rand_list(int size);
	void print_list(Node* head);

	bool is_list_empty(Node* head); 
	void push_back(Node* head, int key);
	void push_forward(Node*& head, int key);
  void squeeze_in(Node* head, int pos, int key);

	int list_size(Node* head);
	void behead(Node*& head);

	int init()
	{
		setlocale(LC_ALL, "Russian");
		int n; cout << "Введите длину: "; cin >> n;
		Node* lst = rand_list(n);
		
		if (is_list_empty(lst))
		{
			cout << "Список пуст." << endl;
			return 0;
		}
		cout << "Список: " << endl;
		print_list(lst);

		cout << "Добавим в начало 11111:" << endl;
		push_forward(lst, 11111);
		print_list(lst);

		cout << "Добавим в конец 22222:" << endl;
		push_back(lst, 22222);
		print_list(lst);

		cout << "Добавим в середину 33333:" << endl;
		squeeze_in(lst, n/2+1, 33333);
		print_list(lst);

		cout << "Длина списка: " << list_size(lst) << endl;

		cout << "Список без первого элемента:" << endl;
		behead(lst);
		print_list(lst);

		return 0;
	}

	Node* newNode(int key)
	{
		Node* node = new Node;
		node->key = key;
		node->next = nullptr;
		return node;
	}

	Node* rand_list(int size)
	{
		Node* head = newNode(rand());
		Node* last = newNode(rand());
		head->next = last;

		for (int i = 0; i < size-2; i++)
		{
			Node* node = newNode(rand());

			last->next = node;
			last = node;
		}

		return head;
	}

	void print_list(Node* head)
	{
		Node* ptr = head;
		while (ptr)
		{
			cout << ptr->key << " -> ";
			ptr = ptr->next;
		}
		cout << "nullptr" << endl;
	}

	bool is_list_empty(Node* head)
	{
		bool empty = true;

		while (head)
		{
			empty = false;
			break;
		}

		return empty;
	}

	void push_back(Node* head, int key)
	{
		Node* last = nullptr;
		Node* ptr = head;
		while (ptr)
		{
			last = ptr;
			ptr = ptr->next;
		}
		ptr = newNode(key);
		last->next = ptr;
	}

	void push_forward(Node*& head, int key)
	{
		Node* node = newNode(key);
		node->next = head;
		head = node;
	}

	void squeeze_in(Node* head, int pos, int key)
	{
		Node* node_left=head;
		Node* node_right;
		Node* node = newNode(key);
		
		for (int i = 0; i < pos-1; i++)
		{
			node_left = node_left->next;
		}
		node_right = node_left->next->next;
		node_left->next = node;
		node->next = node_right;
	}

	int list_size(Node* head)
	{
		int num=0;
		Node* ptr = head;
		while (ptr)
		{
			ptr = ptr->next;
			num++;
		}
		return num;
	}

	void behead(Node*& head)
	{
		head = head->next;
	}
}