Линейный односвязный список. Общие сведения. Базовые операции над списком
Содержание
- 1. Понятие об односвязном списке. Особенности кодировки. Базовые операции над списком
- 2. Общий вид списка. Структура, описывающая один элемент списка
- 3. Формирование списка
- 4. Вставка элемента в заданную позицию списка
- 5. Удаление элемента из списка в заданной позиции
- Связанные темы
Поиск на других ресурсах:
1. Понятие об односвязном списке. Особенности кодировки. Базовые операции над списком
Односвязный список является динамической структурой данных, реализующей формирование и обработку набора элементов. Элементы односвязного списка могут быть отсортированы или не отсортированы.
Односвязный список может сохраняться:
- в оперативной памяти;
- в файле.
В односвязном списке выделяют отдельный элемент (Element), который называется узел (Node).
Каждый элемент (узел) односвязного списка состоит из двух частей:
- данные. Это может быть переменная любого примитивного типа (int, double, char, …), объект класса или сложная структура. Данные могут состоять из нескольких полей (переменных);
- адрес или позиция следующего элемента. Если односвязный список хранится в оперативной памяти, то это указатель (адрес) на такой же элемент (узел). Если односвязный список хранится в файле, то это позиция следующего элемента в файле.
Реализовать узел можно с помощью класса или структуры. Также можно создавать односвязный список на основе шаблонного класса, оперирующего некоторым обобщенным типом T.
Совокупность элементов (узлов), в которых указатель предыдущего элемента указывает следующий элемент, образует односвязный список.
Для списка можно выделить следующие основные операции:
- формирование списка;
- добавление элемента в конец списка;
- вставка элемента в заданную позицию списка;
- удаление элемента из списка из заданной позиции;
- очистка списка;
- замена элемента в списке;
- поиск элемента в списке по индексу или некоторому критерию.
При желании перечень операций можно расширить, добавив собственные идеи (например, вставка группы элементов в список, сортировка элементов в списке, создание отсортированного списка и т.п.).
⇑
2. Общий вид списка. Структура, описывающая один элемент списка
Общий вид линейного односвязного списка изображен на рисунке 1.
Рисунок 1. Общий вид списка
На рисунке 2 изображена структура Element, используемая как базовый элемент линейного односвязного списка. В каждом элементе хранятся данные некоторого типа T.
Рисунок 2. Структура Element, описывающая один элемент списка с программным кодом на языке C++
⇑
3. Формирование списка
3.1. Создать пустой список
Создание списка включает следующие этапы.
1. Объявление указателей на начало и конец списка.
2. Установка нулевых значений указателям.
3. Установка количества элементов в значение 0.
Рисунок 3. Формирование списка: 1) — объявление указателей; 2) — установка нулевых значений
⇑
3.2. Добавление элемента в конец списка
При добавлении элемента в конец списка рассматривают 2 возможные ситуации:
- добавление элемента в пустой список;
- добавление элемента в непустой список (список, в котором есть элементы).
⇑
3.2.1. Добавление нового элемента в конец пустого списка
При добавлении элемента в конец пустого списка выделяют следующие операции (рисунок 4):
1. Создать новый элемент. Здесь нужно выделить память для нового элемента и заполнить ее некоторыми данными (_data). Для этого объявляется указатель (например, elem):
Element<T>* elem = new Element<T>; elem->data = _data;
2. Установить указатель next в нулевое значение
elem->next = nullptr;
3. Установить указатели begin и end равными значению указателя elem.
begin = end = elem;
4. Увеличить количество элементов в списке на 1
count++;
Рисунок 4. Добавление элемента в конец пустого списка: 1 – создание элемента; 2 – установка указателя next; 3 – установка указателей begin и end
⇑
3.2.2. Добавление элемента в конец существующего списка
Если список уже существует, то последовательность шагов добавляющих элемент в список следующая (рисунок 5):
1. Создать новый элемент и заполнить его данными (рисунок 5). Заполняются поля data и next. Создание элемента осуществляется таким же образом как в случае с пустым списком:
Element<T>* elem = new Element<T>; elem->data = _data; elem->next = nullptr;
2. Установить указатель next элемента, на который указывает указатель end, в значение адреса элемента elem (рисунок 6)
end->next = elem;
3. Установить указатель end равным значению указателя elem
end = elem;
4. Увеличить количество элементов в списке на 1
count++;
Вышеприведенные шаги более красноречиво отображаются на рисунках 5, 6, 7.
Рисунок 5. Создание элемента и заполнение его данными
Рисунок 6. Изменение указателя next элемента end
Рисунок 7. Установка указателя end на последний элемент списка
⇑
4. Вставка элемента в заданную позицию списка
При вставке элемента в заданную позицию списка рассматриваются 2 варианта:
- список пуст (нет элементов);
- список имеет хотя бы один элемент.
Если список пуст, то вставка заменяется добавлением первого элемента, как описано в пункте 3.2.1.
Если в списке есть элементы, то здесь рассматриваются 3 варианта:
- вставка элемента в первую позицию списка;
- вставка элемента внутри списка;
- вставка элемента за последним элементом списка. Если происходит вставка за последним элементом списка, то это есть добавление элемента в конец списка как описано в пункте 3.2.2.
⇑
4.1. Список не пуст. Вставка элемента в первую позицию списка
Если происходит вставка элемента в первую позицию списка, то последовательность операций следующая:
1. Создайть новый элемент (рисунок 8). Выделить память под новый элемент. Заполнить элемент данными.
// Выделение памяти под новую ячейку Element<T>* elem = new Element<T>; elem->data = _data;
2. Установить указатель next элемента на начало списка (рисунок 9).
elem->next = begin;
3. Установить начало списка на новую ячейку (рисунок 10).
begin = elem;
Все вышеперечисленные шаги графически изображены на рисунках 8, 9, 10.
Рисунок 8. Создание нового элемента. Заполнение полей элемента значениями
Рисунок 9. Вставка элемента в начало списка. Установка поля next равного адресу первого элемента списка
Рисунок 10. Присваивание указателю начала списка адреса новосозданного элемента
⇑
4.2. Список не пуст. Вставка элемента в середину списка
Если элемент вставляется перед второй, третьей и т.д. а также последней позицией списка, то выполняются нижеследующие шаги.
1. Создать элемент. Заполнить поле данных элемента
Element<T>* elem = new Element<T>; elem->data = _data;
2. Определить позицию элемента, который следует перед позицией вставки элемента. Получить указатель на эту позицию.
Element<T>* elemPrev = Move(index - 1);
здесь Move() – метод, возвращающий позицию элемента, находящегося перед позицией вставки index.
3. Установить указатель next элемента elem, который вставляется
elem->next = elemPrev->next;
4. Установить указатель next предыдущего элемента elemPrev так, чтобы он указывал на вставляемый элемент elem
elemPrev->next = elem;
Предыдущие 4 шага изображены на рисунках 11, 12, 13, 14.
Рисунок 11. Создание элемента. Заполнение элемента данными
Рисунок 12. Вставка элемента в список. Поиск элемента, который следует перед позицией вставки
Рисунок 13. Вставка элемента в список. Установка указателя next вставляемого элемента
Рисунок 14. Вставка элемента в список. Установка указателя next элемента, следующего перед позицией вставки
⇑
5. Удаление элемента из списка в заданной позиции
Чтобы удалить элемент из списка, сначала производится проверка, пуст ли список. Если список не пуст (список содержит хотя бы один элемент), то производится удаление элемента.
При удалении элемента из списка рассматриваются 2 возможные ситуации:
- удаляется первый элемент из списка;
- удаляется не первый элемент из списка (второй, третий и т.д.).
⇑
5.1. Список не пуст. Удаление первого элемента из списка
Если удаляется первый элемент в списке, то последовательность шагов удаления следующая.
1. Получить адрес первого элемента (рисунок 15)
Element<T>* delElem = begin;
2. Переместить указатель на начало списка begin на следующий элемент
begin = begin->next;
3. Освободить память, выделенную для элемента delElem
delete delElem;
На рисунках 15, 16, 17 изображен весь процесс удаления первого элемента из списка.
Рисунок 15. Удаление первого элемента из списка. Шаг 1. Создать указатель на первый элемент
Рисунок 16. Удаление элемента. Шаг 2. Перемещение указателя начала списка на следующий элемент
Рисунок 17. Удаление элемента. Шаг 3. Освободить память, выделенную под элемент
⇑
5.2. Список не пуст. Удаление не первого элемента из списка
Если в непустом списке удаляется не первый элемент (второй, третий и т.д., последний), то последовательность шагов следующая.
1. Переместить указатель на позицию, следующую перед удаляемым элементом. Получить элемент, предшествующий удаляемому элементу
Element<T>* elemPrev = Move(index - 1);
здесь Move() – метод, возвращающий элемент по указанной позиции.
2. Запомнить удаляемый элемент
Element<T>* elemDel = elemPrev->next;
3. Сместить указатель next предыдущего элемента elemPrev в обход удаляемого элемента elemDel
elemPrev->next = elemDel->next;
4. Удалить элемент elemDel (освободить память, выделенную для элемента).
delete elemDel;
На рисунках 18, 19, 20, 21 схематически рассмотрены вышеприведенные шаги.
Рисунок 18. Удаление элемента всередине списка. Переход на элемент, следующий перед предыдущим
Рисунок 19. Удаление элемента. Получить удаляемый элемент
Рисунок 20. Удаление элемента из списка. Смещение указателя next предыдущего элемента в обход удаляемого элемента
Рисунок 21. Удаление элемента из списка. Особождение памяти, занимаемой элементом
⇑
Связанные темы
- Пример реализации линейного односвязного списка для обобщенного типа T
- Линейный двухсвязный список. Общие сведения. Базовые операции со списком
- Линейный двухсвязный список. Пример шаблонного класса
- Разработка шаблонного класса, реализующего стек в виде односвязного списка
⇑