Односвязный или двусвязный список в С — это простейшая структура сохранения информации в программе. Информация в такой структуре сохраняется в цепочке элементов, которые называются узлами. Каждый отдельный узел списка состоит из 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;
Заключение
Сегодня мы рассказали и показали вам, что такое односвязный и двусвязный список в С. Как вы, наверное, заметили, реализация списков в С не связана с какими-то трудностями. Самое главное — это выбрать, что больше подходит для вашей программы: массив или список. В следующих статьях мы покажем, какие операции можно проводить с элементами списка.
Другое
