#include <stdio.h>
#include <stdlib.h>
// #include <time.h>
#define N 100

typedef int item;
item m,v;

typedef struct // структура элемента
{ 
  item body;  //значение
  int next;  //индекс следующего элемента
} litem;

typedef struct
{ 
  int first, last, size; // индекс первого, последнего, размер
  litem M[N]; //массив элементов
} list;

void init(list* l)  // инициализация
{ 
  l->first=0;          // первый равен 0
l->last=1;             
   l->size=0;       
   for(int i=0;i<N-1;i++) 
   {
l->M[i].next=i+1; 
l->M[i].body=0;
}
   l->M[N-1].next=0;  // терминатор
}

void print(list l) {  
int i=1;
    printf("first=%d\n",l.first);
    printf("last=%d\n",l.last);
    printf("size=%d",l.size);
    //  do 
      //  printf("%d-(%d,%d)\n",i,l.M[i].body,l.M[i].next);
    //  while(l.M[i++].body);
 if(!l.size) {
printf("\nList is empty!\n");
return;
}
   i=l.first;   
printf("\nList: ( ");
    do {
printf("%d ",l.M[i].body); 
i=l.M[i].next;
} // iterator
    while(i);  
printf(")\n");
}

void insertfirst(list* l, item v)  
{  
  int k=l->M[0].next;      // элемент m[0] пустой, а m[0].next содержит индекс пустого элемента за последним
  l->M[0].next=l->M[k].next;  
   printf(">%d<\n",  l->M[0].body);
   printf(">%d<<", l->M[k].next);
l->M[k].body=v; 
l->M[k].next=l->first;
l->first=k; 
l->size++;
}

void insertlast(list* l, item v)
{ 
int k=l->M[0].next; 
l->M[0].next=l->M[k].next;
   l->M[l->last].next=k;
   l->M[k].body=v; 
l->M[k].next=0; 
l->last=k;
   l->size++; 
if(!l->first)
l->first=k;
}


void insertafter(list* l,int after, item v)
{ 
int i=l->first;
   do { 
if(i==after)
break; 
i=l->M[i].next;
}
     while(i);
    if(!i||!l->size)
    {
printf("There is no index=%d in list!\n",after); return;
}
   int k=l->M[0].next; 
l->M[0].next=l->M[k].next;
   l->M[k].body=v; 
l->M[k].next=l->M[after].next;
   l->M[after].next=k;
   if(l->last==after) 
l->last=k;
   l->size++;
}

int find(list* l, item v)
{ 
int i=l->first;
   do { 
if(l->M[i].body==v)
break; 
i=l->M[i].next;
}
     while(i);
    if(!i||!l->size)
    {
printf("There is no value=%d in list!\n",v); 
return 0;
}
    return i;
}

void deleting(list* l, int index)
{
   if(!index)
    {
printf("There is no index=%d in list!\n",index); 
return;
}
   if(!l->size){
printf("List is empty!"); 
return;
}
     if(index==l->first)
    { 
l->first=l->M[index].next;
      l->M[index].next=l->M[0].next; 
l->M[0].next=index;
      if(!l->M[l->first].next) 
l->last=l->first;
      l->size--; 
return;                        
     }
   int after=l->first;
   do { 
if(l->M[after].next==index)
break; 
after=l->M[after].next;
}
     while(after);
    if(!after)
    {
printf("There is no index=%d in list!\n",index); 
return;
}
    l->M[after].next=l->M[index].next;
      l->M[index].next=l->M[0].next; 
l->M[0].next=index;
      if(!l->M[after].next) 
l->last=after;
      l->size--; return;
}

// across each line of code with drawing each step.
/*void deleteAfterMiddle(list* l, int num_to_del) 
{
  if (l->size < num_to_del) {
    return;
  } else {
    if(l->size < 2)
    {
        printf("there is nothing to delete!\n");
        return;
    }
    // точка середины
    int middle_point = l->size / 2;
    int current_ind = l->first;//индекс элемента где мы находимся
    while(num_to_del > 0)
    {
      //сколько элементов мы прошли дойдя до середины
        int num_of_elem_to_travel = middle_point;
        current_ind = l->first;
	//
        while(num_of_elem_to_travel > 1)
        {
            num_of_elem_to_travel--; //все ближе и ближе
            current_ind = l->M[current_ind].next; // двигаемся в next elements in list
        }
	//нет элементов после середины
	//больше ничего не будем удалять
        if(l->M[current_ind].next == 0)
            break; 
        current_ind = l->M[current_ind].next;
	//удалить первый элемент после середины
	// список обновится после операции, поэтомы следующий элемент, который должен быть удален, становится первым после середины
        deleting(l, current_ind);
        num_to_del--;

    }
}
}*/

// across each line of code with drawing each step.
void deleteAfterMiddle(list* l, int num_to_del) 
{
  if (l->size < num_to_del) {
    return;
  } else {
    //  if (l->size < 2)
    /* {
        printf("there is nothing to delete!\n");
        return;
	}*/
    if (l->size == 1 && num_to_del == 1) {
        deleting(l, l->first);
	return;
    }
    if (l->size < 2) {
      return;
    } else {
    int middle_point = l->size/2;
    if (num_to_del >= middle_point) {
    // точка середины
      //   int middle_point = l->size / 2;
    int current_ind = l->first;//индекс элемента где мы находимся
    while(num_to_del > 0)  {
        int num_of_elem_to_travel = l->size - num_to_del;
        current_ind = l->first;
        while(num_of_elem_to_travel > 0) {
            num_of_elem_to_travel--; //все ближе и ближе
            current_ind = l->M[current_ind].next; // двигаемся в next elements in list
        }
	//нет элементов после середины
	//больше ничего не будем удалять
        if(l->M[current_ind].next == 0)
            break; 
        current_ind = l->M[current_ind].next;
	//удалить первый элемент после середины
	// список обновится после операции, поэтомы следующий элемент, который должен быть удален, становится первым после середины
        deleting(l, current_ind);
        num_to_del--;

    }
    }
    if ((num_to_del <= middle_point) && (num_to_del <= l->size)) {
      while (num_to_del != 0) {
      int idti;
      idti = l->size - num_to_del;
int  current_ind = l->first;
   while(idti != 0) {
           idti--; //все ближе и ближе
            current_ind = l->M[current_ind].next; // двигаемся в next elements in list
        }
    deleting(l, current_ind);
        num_to_del--;
}
    }
  }
}
}

int main() {
  int i;
  int v;
  int num, el, after;
      list k;
  while(1) {
    printf("1. Generate a list.\n");
    printf("2. Add the first element.\n");
    printf("3. Add the last element.\n");
    printf("4. Add the element after.\n");
    printf("5. Delete element.\n");
    printf("6. Delete k elements.\n");
    printf("7. Print.\n");
    printf("0. Exit.\n");
    printf("---");
      scanf("%d", &v);
    //  v = getchar();
      if (v == 0) {
	break;
      }
      if (v == 1) {
      printf("Enter the number of elements(1 - 14).\n");
      scanf("%d", &num);
      if (num > 0 && num <= 14) {
	init(&k);
	for (i = 0; i < num; i++) {
	  printf("Enter the element:\n");
	  scanf("%d", &el);
	  insertlast(&k, el);
	}
      } else {
	printf("Wrong!\n");
      }
      }
      if (v == 2) {     
    printf("Enter the element.\n");
    scanf("%d", &el);
    insertfirst(&k, el);
      }
      if (v == 3) {     
    printf("Enter the element.\n");
    scanf("%d", &el);
    insertlast(&k, el);
      }
      if (v == 4) {
    printf("Enter the element.\n");
    scanf("%d", &el);
    printf("After.");
    scanf("%d", &after);
    insertafter(&k, find(&k, after), el);
      }
      if (v == 5) {
    printf("Enter the element to delete.");
    scanf("%d", &el);
    deleting(&k, find(&k, el));
      }
      if (v == 6) {
    printf("Delete n last elements:\n");
    scanf("%d", &el);
    deleteAfterMiddle(&k, el);
      }
      if (v == 7) {
      print(k);
      }
  }
    }

#include <stdio.h>
#include <stdlib.h>

#define N 100

typedef int item;	//тип данных элемента списка
item		m,v;

typedef struct		//структура элемента
{ 
	item body;		//значение
	int next;		//индекс следующего элемента
} litem;

//0-й элемент пустой, [0].next содержит индекс пустого элемента за последним
typedef struct		//структура списка
{ 
	int		first, last, size;	//индекс первого, последнего, размер
	litem	M[N];				//массив элементов
} list;

void init(list* l)	//инициализация списка
{ 
	l->first = 0;	//первый равен 0
	l->last = 1;	//последний = 1
	l->size = 0;	//размер = 0
	
	//пропишем всем значение = 0 и последовательные ссылки друг на друга
	for(int i=0;i<N-1;i++) 
	{
		l->M[i].next=i+1; 
		l->M[i].body=0;
	}
	l->M[N-1].next=0;//терминатор, конец последнего
}

void print(list l)	//вывод на экран списка
{  
	int		i;
	
	printf("first=%d\n",l.first);	//первый
	printf("last=%d\n",l.last);		//последний
	printf("size=%d",l.size);		//размер

	if(!l.size)						//список пустой?
	{
		printf("\nList is empty!\n");
		return;
	}
	i = l.first;					//начинаем с первого
	printf("\nList: ( ");
    do 
	{
		printf("%d ", l.M[i].body);	//значение
		i=l.M[i].next;				//на следующий
	} // iterator
    while(i);						//пока не 0
	printf(")\n");
}

void insertfirst(list* l, item v)	//вставка в список первым
{  
	int		k = l->M[0].next;		//элемент m[0] пустой, а m[0].next содержит индекс пустого элемента за последним
									//k - индекс пустого элемента за последним
	l->M[0].next = l->M[k].next;	//сохраняем индекс следующего пустого элемента
//	printf(">%d<\n",  l->M[0].body);//незачем выводить, там всегда 0
	printf(">%d<<\n", l->M[k].next);//выведем для отладки индекс следующего пустого элемента
	l->M[k].body=v;					//копируем значение элемента
	l->M[k].next=l->first;			//старый первый будет идти за новым
	l->first=k;						//новый делаем первым
	l->size++;						//считаем
}

void insertlast(list* l, item v)	//вставка в конец списка
{ 
	int		k = l->M[0].next;		//элемент m[0] пустой, а m[0].next содержит индекс пустого элемента за последним
	
	l->M[0].next=l->M[k].next;		//индекс нового пустого
	l->M[l->last].next=k;			//новый будет идти за старым последним
	l->M[k].body=v;					//копируем значение элемента
	l->M[k].next=0;					//помечаем, что последний
	l->last=k;						//запоминаем индекс последнего
	l->size++;						//считаем
	if(!l->first)					//если ничего не было
		l->first=k;					// то считаем нового первым
}


void insertafter(list* l,int after, item v)	//вставка элемента после after
{ 
	int i=l->first;					//первый в списке
	do								//найдем элемент, равный заданному
	{ 
		if (i==after)				//индекс равен?
			break;					//да, идем дальше
		i=l->M[i].next;				//на следующий элемент списка
	}while(i);						//пока не просмотрим весь список
    
	if(!i||!l->size)				//не нашли или список пуст
    {
		printf("There is no index=%d in list!\n",after); 
		return;
	}
   
	int k=l->M[0].next;				//индекс пустого места
	l->M[0].next=l->M[k].next;		//новое пустое место
	l->M[k].body=v;					//пишем значение элемента
									//правим ссылки
	l->M[k].next=l->M[after].next;	//после нового будет идти следующий за after
	l->M[after].next=k;				//а новый будет идти за after
   
	if(l->last==after)				//вставляем после последнего?
		l->last=k;					//запоминаем новый последний индекс
	l->size++;						//считаем
}

int find(list* l, item v)			//поиск элемента в списке
{ 
	int i=l->first;					//начинаем с первого
	do 
	{ 
		if(l->M[i].body==v)			//сравнимаем значение элемента
			break;					//равно - нашли!
		i=l->M[i].next;				//на следующий
	}while(i);						//пока не пройдем весь список
    
	if(!i||!l->size)				//не нашли или пустой список?
	{
		printf("There is no value=%d in list!\n",v); 
		return 0;					//признак того, что не нашли
	}
    return i;						//индекс найденного элемента
}

void deleting(list* l, int index)	//удаление элемента из списка по индексу
{
	if(index<1)						//индекс должен быть >= 1
    {
		printf("There is no index=%d in list!\n",index); 
		return;
	}
	if(!l->size)					//список пуст?
	{
		printf("List is empty!"); 
		return;
	}
	if(index==l->first)				//удаляем первого?
    { 
		l->first=l->M[index].next;	//запоминаем следующего за первым, как новый первый индекс
									//добавляем индекс удаленного элемента в цепочку свободных
		l->M[index].next=l->M[0].next;	//удаленный ссылается на первого свободного
		l->M[0].next=index;				//а индекс удаленного запоминаем, как нового первого свободного
		if(!l->M[l->first].next)	//если новый первый - единственный
			l->last=l->first;		//то он становится и новым последним
		l->size--;					//уменьшаем число
		return;
	}
	int after=l->first;				//ищем удаляемый элемент, начиная с первого
	do 
	{ 
		if(l->M[after].next==index)	//следующий - удаляемый?
			break;					//нашли!
		after=l->M[after].next;		//на следующий
	}while(after);					//до конца списка
    
	if(!after)						//не нашли?
	{
		printf("There is no index=%d in list!\n",index); 
		return;
	}
	//нашли, правим ссылки
	l->M[after].next=l->M[index].next;	//предыдущий будет ссылаться на следующего за удаляемым
									//добавляем индекс удаленного элемента в цепочку свободных
	l->M[index].next=l->M[0].next;	//удаленный ссылается на первого свободного
	l->M[0].next=index;				//а индекс удаленного запоминаем, как нового первого свободного
	
	if(!l->M[after].next)			//удалили последнего?
		l->last=after;				//сохраняем нового последнего
	l->size--;						//уменьшаем число
}

void deleteLastK(list* l, int num_to_del) //удаление num_to_del последних элементов
{
	int		i;

	if (l->size >= num_to_del)		//есть что удалять?
	{
		for (i=0; i<num_to_del; i++)//удаляем num_to_del раз
			deleting(l, l->last);	//последнего!
	}
}

int main() 
{
	int		i;
	int		v;
	int		num, el, after;
    list	k;						//список
	  
	init(&k);						//его надо обязательно инициировать!
  
	while(1) 
	{
		printf("1. Generate a list.\n");
		printf("2. Add the first element.\n");
		printf("3. Add the last element.\n");
		printf("4. Add the element after.\n");
		printf("5. Delete element.\n");
		printf("6. Delete k last elements.\n");
		printf("7. Print.\n");
		printf("0. Exit.\n");
		printf("---");
		scanf("%d", &v);

		if (v == 0)					//выход
			break;
		else if (v == 1)			//добавление группы новых элементов в конец списка
		{
			printf("Enter the number of elements(1 - 14).\n");
			scanf("%d", &num);
			if (num > 0 && num <= 14)	//разрешаем 1 - 14
			{
				for (i = 0; i < num; i++) 
				{
					printf("Enter the element:\n");
					scanf("%d", &el);
					insertlast(&k, el);	//в конец списка
				}
			} 
			else 
				printf("Wrong!\n");
		}
		else if (v == 2)				//добавляем в начало списка
		{
			printf("Enter the element.\n");
			scanf("%d", &el);
			insertfirst(&k, el);
		}
		else if (v == 3) 				//в конец списка
		{
			printf("Enter the element.\n");
			scanf("%d", &el);
			insertlast(&k, el);
		}
		else if (v == 4)				//после заданного
		{
			printf("Enter the element.\n");
			scanf("%d", &el);
			printf("After.");
			scanf("%d", &after);
			insertafter(&k, find(&k, after), el);
		}
		else if (v == 5)				//удаление элемента по значению
		{
			printf("Enter the element to delete.");
			scanf("%d", &el);
			deleting(&k, find(&k, el));	//сначала найдем элемент, если не найдем, 
										//то будет сообщение о невозможности удаления 0 элемента
		}
		else if (v == 6)				//удаление N последних элементов
		{
			printf("Delete n last elements:\n");
			scanf("%d", &el);
			deleteLastK(&k, el);
		}
		else if (v == 7) 
			print(k);					//вывод списка
	}
}