Другое

Односвязный и двусвязный список С: основные операции и методы

Lorem ipsum dolor

Односвязный или двусвязный список в С — это простейшая структура сохранения информации в программе. Информация в такой структуре сохраняется в цепочке элементов, которые называются узлами. Каждый отдельный узел списка состоит из 2 компонентов:

  •  сохраняемой информации,

  •  ссылки на последующий узел.

В качестве сохраняемой информации в узлах может располагаться что угодно:

  •  число,

  •  переменная,

  •  строки,

  •  объекты класса,

  •  структуры,

  •  и др.

Информация в списках может располагаться произвольным образом. Что касается ссылок, они же указатели, то их предназначение указывать на следующий узел или на следующий и предыдущий узел. Роль ссылок — показывать взаимосвязь между информацией, сохраняемой в узлах списка.

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

Списки в С классифицируются по нескольким критериям. Первая и главная классификация — по количеству ссылок (указателей) в узлах списка. Согласно этому критерию, можно выделить 2 вида списков:

  1. Односвязный или однонаправленный список С. В таком списке в отдельном узле хранится какая-то информация и указатель только на следующий узел. Исследовать элементы такого списка можно лишь в одном направлении — по мере движения указателей. В обратном направлении исследовать такой список затруднительно.

  2. Двусвязный или двунаправленный список С. В каждом отдельном узле такого списка содержатся две ссылки (указателя): одна на следующий узел списка, а другая на предыдущий узел списка. Исследовать элементы такого списка можно в двух направлениях.

Мы выяснили, что односвязный и двусвязный списки — это взаимосвязанные между собой узлы. По типу связи списки бывают:

  1. Линейные. У таких списков последний узел указывает на значение «NULL». Это касается односвязного и двусвязного списков.

  2. Циклические. В таких списках последний узел связан с первым, а не с «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;

 

Заключение

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

Схожие статьи

Cosmos: операционная система, ее требования и пошаговая установка
Другое

Cosmos: операционная система, ее требования и пошаговая установка

Воспроизведение звука в Unity и добавление музыки в приложение
Другое

Воспроизведение звука в Unity и добавление музыки в приложение

Палиндром: определение и применение в разных языках программирования
Другое

Палиндром: определение и применение в разных языках программирования

База данных: как ее создавать, с чего начать и основные этапы
Другое

База данных: как ее создавать, с чего начать и основные этапы