Создание связного списка

Элемент (узел) - это область памяти, в которой хранится ячейка связного списка. Узел односвязного списка состоит из 2-х полей: в первом хранятся данные (это поле также называется ключом), а во втором - указатель на следующий узел. Существует специальный указатель head, указывающий на первый узел списка. Указатель head – это отдельная переменная, не принадлежащая списку. Последний узел в списке указывает на NULL, и для него тоже создается специальная переменная - указатель tail. Если первый элемент указывает на NULL, то это будет пустой список. В листинге 2 приведена структура для определения элемента списка:

Листинг 2. Структура для элемента списка

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

Указатель next имеет тот же тип, что и сам элемент, и указывает на следующий элемент списка. В листинге 3 приведен пример создания списка из трех элементов.

Листинг 3. Создание списка из трех элементов

// объявить три указателя на элементы списка // указатель head ведет на первый элемент списка struct node* head = NULL; struct node* second = NULL; struct node* third = NULL;   // выделить память под элементы // метод sizeof вычисляет размер элемента // метод malloc выделяет требуемое количество памяти // установить указатели на выделенные фрагменты памяти head = malloc(sizeof(struct node)); second = malloc(sizeof(struct node)); third = malloc(sizeof(struct node));   // инициализировать элементы списка и связать их между собой head->data = 1; head->next = second; second->data = 2; second->next = third; third->data = 3; third->next = NULL;

 

Определение длины списка

Чтобы определить размер связного списка, необходимо пройти по списку и посчитать количество узлов. В листинге 4 приведена функция для подсчета числа узлов.

Листинг 4. Функция для определения длины списка

int Length(struct node* head) { struct node* current = head; int count = 0; while (current!= NULL) { count++; current = current->next; } return count; }

В этой функции создается дополнительный указатель current, с помощью которого выполняется ИТЕРАЦИЯ связного списка:

current = current->next;

При этой операции со списком ничего не происходит, но указателю НАЗНАЧАЕТСЯ новое значение. Если вызвать эту функцию для пустого списка, у которого вершина равна NULL, то функция вернет ноль.

 

Добавление элемента в начало списка

В листинге 5 приведена функция Push для добавления элементов в начало списка в обратном порядке.

Листинг 5. Функция для добавления элементов в начало списка

void Push(struct node** headRef, int data) { struct node* newNode = malloc(sizeof(struct node)); newNode->data = data; newNode->next = *headRef; *headRef = newNode; } // пример использования этой функции struct node* head = NULL; // создание первого элемента Push(&head, 1); Push(&head, 2); Push(&head, 3);

Символ & - это указание компилятору, что параметр передается по ссылке, т.е. все изменения, которые будут сделаны с этим параметром внутри функции, останутся актуальными для переданного объекта и после выхода из функции.

При передаче параметров по ссылке нужно следовать трем правилам:

1. в определении функции для указателей нужно использовать двойной указатель **;
2. при вызове функции перед ссылочным параметром нужно поставить &;;
3. в самой функции к ссылочному параметру обращаться через указатель *.

Добавление элементов в конец списка

 

В листинге 6 представлен пример добавления элементов в конец списка.

Листинг 6.

struct node* AppendNode(struct node** headRef, int num) { struct node* current = *headRef; struct node* newNode; newNode = malloc(sizeof(struct node)); newNode->data = num; newNode->next = NULL; // если список пуст if (current == NULL) { *headRef = newNode; } else { // иначе while (current->next!= NULL) { current = current->next; } current->next = newNode; } }

В представленном коде выполняется итерация по списку для поиска последнего элемента, а затем его указатель next устанавливается на добавляемый элемент.