Связные списки

В этом руководстве вы познакомитесь с различными типами связанных списков и узнаете, как реализовать его на Си. 

Существует три основных типа связанных списков.

  1. Односвязный список.
  2. Двусвязный список.
  3. Кольцевой связный список.

Односвязный список

Это самый распространенный тип связных списков. В каждом узле есть указатель на следующий узел.

 

Узел в этом случае выглядит вот так:

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

Создадим односвязный список из 3 членов на Си:

/* Объявляем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Присваиваем значения */
one->data = 1;
two->data = 2;
three->data = 3;

/* Связываем узлы */
one->next = two;
two->next = three;
three->next = NULL;

/* Сохраняем «адрес» первого узла в корне */
head = one;

Двусвязный список

Если добавить указатель на предыдущий узел, получится двусвязный список. В нём можно «двигаться» в обоих направлениях: и вперед, и назад.

Поэтому двусвязный список еще называют двунаправленным.

Узел в этом случае выглядит вот так:

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

Создадим двусвязный список из 3 членов на Си:

/* Объявляем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Присваиваем значения */
one->data = 1;
two->data = 2;
three->data = 3;

/* Связываем узлы */
one->next = two;
one->prev = NULL;
two->next = three;
two->prev = one;
three->next = NULL;
three->prev = two;

/* Сохраняем «адрес» первого узла в корне */
head = one;

Кольцевой связный список

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

Кольцевой связный список может быть как односвязным, так и двусвязным.

  • В односвязном указатель на следующий элемент последнего узла указывает на первый узел. 

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

Создадим кольцевой односвязный список на Си:

/* Объявляем узлы */
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

/* Выделяем память */
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

/* Присваиваем значения */
one->data = 1;
two->data = 2;
three->data = 3;

/* Связываем узлы */
one->next = two;
two->next = three;
three->next = one;

/* Сохраняем «адрес» первого узла в корне */
head = one;
codechick

СodeСhick.io - простой и эффективный способ изучения программирования.

2024 ©