Односвязный или двусвязный список в С — это простейшая структура сохранения информации в программе. Информация в такой структуре сохраняется в цепочке элементов, которые называются узлами. Каждый отдельный узел списка состоит из 2 компонентов:
-
сохраняемой информации,
-
ссылки на последующий узел.
В качестве сохраняемой информации в узлах может располагаться что угодно:
-
число,
-
переменная,
-
строки,
-
объекты класса,
-
структуры,
-
и др.
Информация в списках может располагаться произвольным образом. Что касается ссылок, они же указатели, то их предназначение — указывать на следующий узел или на следующий и предыдущий узел. Роль ссылок — показывать взаимосвязь между информацией, сохраняемой в узлах списка.
Односвязный и двусвязный список С
Списки в С классифицируются по нескольким критериям. Первая и главная классификация — по количеству ссылок (указателей) в узлах списка. Согласно этому критерию, можно выделить 2 вида списков:
-
Односвязный или однонаправленный список С. В таком списке в отдельном узле хранится какая-то информация и указатель только на следующий узел. Исследовать элементы такого списка можно лишь в одном направлении — по мере движения указателей. В обратном направлении исследовать такой список затруднительно.
-
Двусвязный или двунаправленный список С. В каждом отдельном узле такого списка содержатся две ссылки (указателя): одна на следующий узел списка, а другая на предыдущий узел списка. Исследовать элементы такого списка можно в двух направлениях.
Мы выяснили, что односвязный и двусвязный списки — это взаимосвязанные между собой узлы. По типу связи списки бывают:
-
Линейные. У таких списков последний узел указывает на значение «NULL». Это касается односвязного и двусвязного списков.
-
Циклические. В таких списках последний узел связан с первым, а не с «NULL». Таким образом получается «цикл». Односвязный циклический список С — это когда последний узел содержит ссылку на первый узел списка. Двусвязный циклический список — это когда последний узел списка содержит ссылки на предыдущий и первый узлы, а первый узел содержит ссылки на следующий и последний узлы.
Односвязный и двусвязный список С: сравнение с массивами
Списки нужны для сохранения структурированной информации. Массивы выполняют такую же функцию, поэтому довольно часто С-программист стоит перед выбором: использовать списки или массивы? Чтобы ответить на данный вопрос, мы составили таблицу, где провели сравнение этих двух структур.
|
Свойства массива С |
Свойства списков |
|
Необходимо выделить память под весь массив сразу. Вначале выделяется память, а потом можно пользоваться массивом. |
Не нужно выделять память перед использованием списка. Память выделяется автоматически по мере наполнения списка. |
|
Если удалить какой-то компонент, тогда нужно копировать все последующие компоненты, чтобы их «сдвинуть». |
Если удалить какой-то узел, тогда ничего сдвигать и копировать не нужно. Нужно только сменить ссылки в узлах. |
|
Память нужна только для хранения самого компонента массива. |
Память нужна для хранения компонента списка и ссылок, которые с ним связаны. |
|
Можно обратиться к любому компоненту и в любом порядке. |
Доступ к компонентам можно делать только последовательно. |
Как видно из таблицы сравнения, каждая структура данных имеет собственные достоинства и недостатки, поэтому выбирать ту или иную структуру нужно исходя из конкретных требований к программе. К примеру, для списка не нужно изначально просчитывать и выделять память, но самой памяти потребуется больше и к отдельным элементам обратиться будет сложнее. Массивы нужно изначально просчитывать, однако при одинаковом количестве сохраняемой информации массивам нужно меньше памяти, плюс они предоставляют более свободное обращение к собственным компонентам.
Односвязный и двусвязный список С: примеры в коде
Неважно, какой вид списка вам нужно составить — для начала определяется структура узла. Соответственно, если определите однонаправленную структуру, тогда список будет однонаправленный. Если определите двунаправленную структуру, тогда список будет двунаправленный.
Односвязный список С
Определяем структуру узла:
struct node {
int data;
struct node *next; // определяем указатель только на последующий узел
}
Код односвязного списка из 3-х элементов:
/* Определяем компоненты односвязного списка */
struct node *head; //начальный компонент
struct node *first = NULL;
struct node *second = NULL;
struct node *third = NULL;
/* назначаем выделение памяти под нашу структуру списка */
first = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));
/* определяем сохраняемую информацию в узлах */
first->data = 10;
second->data = 20;
third->data = 30;
/* Указываем связь между узлами */
first->next = second;
second->next = third;
third->next = NULL;
/* указываем, что первичный узел у нас будет начальным или главным компонентом*/
head = first;
Двусвязный список
Определяем структуру узла:
struct node {
int data;
struct node *next;//определяем указатель на последующий компонент списка
struct node *prev;//определяем указатель на предыдущий компонент списка
}
Создаем двусвязный список С, состоящий из 3-х элементов:
/* Определяем компоненты двусвязного списка */
struct node *head;
struct node *first = NULL;
struct node *second = NULL;
struct node *thrid = NULL;
/* Назначаем выделение памяти под компоненты списка */
first = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
thrid = malloc(sizeof(struct node));
/* Определяем информацию, сохраняемую в узлах */
first->data = 10;
second->data = 20;
thrid->data = 30;
/* Определяем связь между компонентами списка */
first->next = second;
first->prev = NULL;
second->next = thrid;
second->prev = first;
thrid->next = NULL;
thrid->prev = second;
/* Указываем, что первый узел у нас будет начальным главным узлом списка */
head = first;
Заключение
Сегодня мы рассказали и показали вам, что такое односвязный и двусвязный список в С. Как вы, наверное, заметили, реализация списков в С не связана с какими-то трудностями. Самое главное — это выбрать, что больше подходит для вашей программы: массив или список. В следующих статьях мы покажем, какие операции можно проводить с элементами списка.