Работа с связными списками

linked_list.c

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

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

struct node* AddNode(struct node* root, int new_val)
{
	int u;
	if (root == NULL)
	{
		root = (struct node*)malloc(sizeof(struct node));
		root->val = new_val;
		root->next = NULL;
		u = root->val;
	}
	else
	{
		struct node *cur;
		cur = root;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = (struct node*)malloc(sizeof(node));
		cur = cur->next;
		cur->val = new_val;
		cur->next = NULL;
	}

	return root;
}

void PrintList(node *root)
{
	if (root == NULL)
	{
		printf("List is empty!");
		return;
	}
	node* cur;
	cur = root;
	do
	{
		printf("%d ", cur->val);
		cur = cur->next;
	} while (cur != NULL);
}
///*


// функция удаляет элемент на какой-то позиции
struct node* DeleteNodeAtPos(struct node* root, int pos)
{
	if (root == NULL) return root; // возвращаем список, если он пустой
	if (root->next == NULL)
	{
		free(root); return NULL;
	}
	struct node* prev;
	struct node* cur;
	
	int i = 0;
	
	prev = NULL;
	cur = root;

	while (cur->next != NULL && i != pos)
	{
		//-
		i++;
		prev = cur;
		cur = cur->next;
	}
	//--
	prev->next = cur->next;
	free(cur);
	return root;
}

int main()
{
	struct node* root = NULL;

	int N = 12;
	for (int i = 0; i < N; i++)
		root = AddNode(root, i);

	PrintList(root);
	printf("\n");

	for (int i = N - 1; i >= 0; i--)
	{
		root = DeleteNodeAtPos(root, i);
		PrintList(root);
		printf("\n");
	}
}

Введение

Язык Си предоставляет ряд инструментов для хранения данных. В первую очередь, в голову приходят обычные массивы:
int Arr[10];
Указатели просты в обращении, но имеют критический дефект: их размер нельзя изменить в ходе работы программы. Если программисту потребуется памяти больше, чем доступно в массиве - придется объявлять дополнительный массив либо всячески ухищряться. Проще всего заранее выделить Достаточно Большой Массив, однако данный подход чреват неэффективным использованием памяти. Существует и другой, не столь очевидный момент. Если объявить массив из большого числа элементов, то для его размещения в памяти потребуется достаточно большой и протяженный блок свободной оперативной памяти, так как все элементы массива хранятся в памяти последовательно. В таком случае массив может не влезть в память, даже если формально будет хватать свободного места в памяти.

Указатели и динамически выделяемая память даёт больше свободы - мы можем выделить память в процессе исполнения программы, освободить её и изменить размер блока. Но всё ещё - выделяемая для одного указателя память выделяется как один протяженный блок. Конечно, можно объявить указатель на динамический массива указателей. Указателям из этого массива память будет выделяться случайным образом в виде блоков памяти.

Подобный подход эффективно решает проблему оптимального использования памяти, однако требует глубоких познаний и высокой культуры программирования. В противном случае, все прекрасные свойства языка Си становятся ужасным проклятием и программисты довольно резво начинают отстреливать свои конечности.
Существует альтернативный подход предоставляющий значительно более простой вариант работы с объектами в памяти и при этом достаточно эффективный.

Структуры, ещё раз структуры и все-все-все

В языке Си существует такое понятие как структуры. Необходимый ликбез разобран в этом электронном учебнике. Я не буду разбирать структуры, лучше прочитайте обо всё по ссылке: достаточно прочитать главы 6.1, 6.2 и 6.3.

Массивы и указатели хранят данные, а обращение к нужным ячейкам, как и вся логика, осуществляется по разумению программиста. Хранить информацию о самой информации отдельно от информации для доступа к информации не всегда хорошая идея. Например, как представить граф?

Или дерево?

Имеет смысл использовать такую структуру данных, в которой каждый элемент (узел) будет хранить как информацию, так и ссылку на следующий элемент(-ы). Структуры языка Си прекрасно подходят для данной задачи.
Объявим структуру, описывающую элемент связного списка - простейшего варианта структуры данных. Пусть она содержит только одно поле - число и указатель на следующий элемент.

struct Node
{
   int val;
   struct Node *next;
}

Вы наверняка обратили внимание на тип указателя. В главе 6.2 учебника указывалось, что структура А может быть элементом структуры Б. В главе 6.3 объяснены указатели на структуры. Неожиданный вывод: структура может хранить указатель на другую структуру такого же типа. Здесь нет никаких противоречий: указатель является переменной, хранящей адрес другого объекта. Тип указателя нужен для правильного расчета смещений в памяти. Поэтому данный указатель можно воспринимать как ещё одно число в котором хранится адрес следующего элемента.
Цепочку элементов в связном списке можно изобразить как:

На рисунке показана цепочка элементов. Каждый элемент хранит одно число, указатель next указывает на следующий узел. Обратите внимание на последний элемент - его указатель next равен NULL. Это - обязательное требование. Так же обратите внимание на root - это отдельный указатель типа struct *Node, который ссылается на первый элемент списка. Если в списке не содержится никаких элементов, то он равен NULL. Указатель root не изменяется в ходе любых манипуляций с списком (кроме удаления всех элементов из него либо удаления первого элемента). В противном случае будет потерян доступ к списку - так как заранее неизвестно по каким адресам лежат узлы списка, то единственный способ добраться к ним - это перебор всех элементов начиная с значения root. Для этого обычно вводится дополнительный указатель node* cur и все операции осуществляются с его помощь.

В общем и целом, два главных правила для работы с связным список крайне просты:

1. Указатель next последнего элемент всегда равен NULL.

Основными операц