Немного лирики
Примерно полгода назад мне было дано задание реализовать двусвязный список на языке С++. В тот момент мои познания в языке были сугубо скромные. Разумеется, я начал искать решение своей проблемы в интернете, но все найденные варианты меня не устроили либо из-за своей простоты, либо излишней запутанности объяснений. Поэтому я решил, что как только сделаю что-то более достойное, то тут же попытаюсь написать об этом статью. И вот этот момент настал.
Немного теории
Список — это структура данных, которая состоит из узлов, каждый из них содержит какую-то полезную информацию и указатели на предыдущий и последующий узлы списка. Сам же список должен содержать указатели на начало и конец списка. Это необходимо, потому что узлы располагаются в случайных участках памяти и для их нахождения необходимо знать где именно они находятся. Указатели на первый и последний элементы позволяют привязать список к цепочке узлов, а тот факт, что каждый узел связан с другими двумя, позволяет перемещаться по списку в поисках нужного узла.
Класс LinkedList
Класс LinkedList будет реализовывать наш двусвязный список. Пожалуй, удобно сделать его шаблонным, чтобы в нем можно было хранить любой тип данных. Ниже представлено объявление класса.
template<typename Item>
class LinkedList
{
private:
// Структура, которая реализует узел списка
struct Node
{
Item item; // Содержимое узла
Node* prev; // Указатель на предыдущий узел
Node* next; // Указатель на следующий узел
};
Node* first; // Указатель на первый узел списка
Node* last; // Указатель на последний узел списка
int size; // Размер списка
// Перечисление, используемое в приватном методе ниже
enum {
up = 0,
down = 1,
};
// Метод, исключающий дублирование кода при поиске элементов внутри класса
Node& findElement(int pos, int count = up) const;
public:
// Конструктор по умолчанию
LinkedList();
// Конструктор с созданием одного узла
LinkedList(Item);
// Конструктор копирования (глубокое копирование)
LinkedList(const LinkedList&);
// Деструктор
~LinkedList();
// Добавление узла в конец списка
LinkedList& Add(const Item&);
// Добавление узла на указанную позицию
LinkedList& Add(const Item&, int pos);
// Размещение указанного количества элементов массива в конец списка
LinkedList& Add(const Item[], int number);
// То же, что и выше, только с указанием позиции размещения
LinkedList& Add(const Item[], int number, int pos);
// Добавление узлов из другого списка
LinkedList& Add(const LinkedList<Item>&);
// То же, только с добавлением на указанную позицию
LinkedList& Add(const LinkedList<Item>&, int pos);
// Удаление узлов, начиная с узла, который указан в pos
// (по умолчанию удаляется один узел)
LinkedList& Delete(int pos, int range = 1);
// Удаление узла в конце списка
LinkedList& Delete();
// Перегрузка операции [], используется при использование
Item operator[](int i) const;
// То же, только используется в изменяемом списке
Item& operator[](int i);
// Перегрузка оператора сложения
LinkedList operator+(const LinkedList<Item>&) const;
// Перегрузка операции равно (глубокое копирование)
const LinkedList& operator=(const LinkedList<Item>&);
// Метод, возвращающий размер списка
int Size();
};Приватная часть класса
Начнем с того, что объявим внутри класса структуру, представляющую собой узел списка. Ее объявление в приватной части класса позволит обеспечить инкапсуляцию. Затем надо объявить поля, являющиеся указателями на первый и последний узел. Размер списка понадобится нам в реализации интерфейса класса(публичные методы). Перечисление и приватный метод рассмотрим вместе.
Метод findElement
При реализации интерфейса нашего класса нам понадобится средство, которое позволит перемещаться к указанному узлу.
// Приватный метод, позволяющий найти нужный узел в списке
// Без использования typename, возникают проблемы распознавания
// включенной структуры Node, как типа, поэтому необходимо это явно указать
template<typename Item>
typename LinkedList<Item>::Node& LinkedList<Item>::findElement(int pos, int count) const
{
LinkedList<Item>::Node* current; // Указатель на узел
// Теперь в зависимости от значения count будет осуществляться поиск
// либо сверху вниз, либо снизу вверх
// (при удалении элементов может быть невозможен поиск снизу вверх)
// При удалении элементов, например из центра списка,
// при прохождении его от первого элемента, наткнемся на пустую область памяти
// В этом случае придется идти от последнего элемента к нужному нам
if (count == up)
{
current = first;
for (int k = 1; k <= pos; k++)
current = current->next;
}
else
{
current = last;
for (int k = size - 2; k >= pos; k--)
current = current->prev;
}
return *current;
}Начнем с сигнатуры метода. Возвращаемым значением будет ссылка на искомый узел, что позволяет редактировать непосредственно сам узел и экономит ресурсы, так как тогда не создается временный объект. Параметр функции pos определяет позицию искомого узла, а параметр count определяет направление поиска: сверху вниз(down), снизу вверх(up — по умолчанию). Квалификатор const говорит о том, что метод не изменяет объект, вызвавший его.
Публичная часть(интерфейс)
Методы Add
Я начал реализацию интерфейса с метода Add, добавляющего один узел на указанную позицию, а потом старался использовать его во всех остальных перегрузках метода. Может такой подход не самый оптимизированный с точки зрения выполнения программы, но зато предотвращает дублирование кода и уменьшает количество потенциальных ошибок.
// Основной метод, добавляющий узел (newNode)
// Будет использоваться в остальных перегрузках метода Add
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Add(const Item& item, int pos)
{
// Создаем новый узел и инициализируем им указатель
LinkedList<Item>::Node* temp = new LinkedList<Item>::Node;
// Устанавливаем содержимое нового узла
temp->item = item;
// Если позиция указывает на позицию за последним элементом, то
if (pos >= size)
{
// новый узел становится последним и
// указатель на следующий элемент узла устанавливается в "0"
last = temp;
temp->next = nullptr;
}
else // В ином случае
{
// указатель на следующий элемент устанавливается на узел,
// который ранее стоял на этой позиции (oldNode),
temp->next = &findElement(pos);
// а указатель на предыдущий узел узла oldNode устанавливается на newNode
(temp->next)->prev = temp;
}
// В итого новый узел и узел перед ним(если он есть) связаны,
// осталось связать наш узел с предыдущим
// Т.к. либо перед, либо после, либо же по обе стороны от нашего узла
// могут отсутствовать другие узлы,
// то логично было разделить связывание newNode c последующим и предыдущим узлами
// Это избавляет нас от сильной вложенности и путаницы
// Если позиция = 0, то узел становится первым
if (pos == 0)
{
temp->prev = nullptr;
first = temp;
}
else
// В ином случае, если размер не равен нулю
// (вдруг пользователь указал ненулевую позицию, а список пуст),
// то связываем newNode с предыдущим узлом
if (size != 0)
{
temp->prev = &findElement(pos - 1);
temp->prev->next = temp;
}
size++; // Увеличиваем значение размера списка
// Возвращаем, используя ссылку, объект, который вызвал метод,
// чтобы можно было воспользоваться конструкцией вида: list.Add().Add()
return *this;
}Далее просто покажу код остальных перегрузок метода Add с подробными комментариями.
// Добавление узла в конец списка
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Add(const Item& item)
{
// Вызываем метод добавления узла, передавая ему содержимое item и указывая,
// что надо добавить узел в конец при помощи поля size
//(гарантирует, что попали на позицию за последним элементом)
return Add(item, size);
}// Добавление массива элементов item[] в список,
// где number - количество элементов массива,
// которые необходимо добавить, а pos указывает на позицию
// с которой начинается добавление узлов
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Add(const Item item[], int number, int pos)
{
// Цикл, вызывающий метод Add, который добавляет по одному элементу в список
for (int i = 0; i < number; i++, pos++)
{
Add(item[i], pos);
}
return *this;
}// Добавление массива в конец списка
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Add(const Item item[], int number)
{
// Вызывает предыдущую перегрузку метода,
// передавая указание, что надо добавить массив в конец списка
return Add(item, number, size);
}// Добавление в список другого списка
// Узлы добавляются, начиная с указанной позиции
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Add(const LinkedList<Item>& list, int pos)
{
// Используется тот же подход, что и с добавлением элементов массива
// в список
for (int i = 0; i < list.size; i++, pos++)
{
// Используется перегрузка операции []
Add(list[i], pos);
}
return *this;
}О перегрузке оператора [] будет написано ниже.
// Добавление в конец списка другого списка
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Add(const LinkedList<Item>& list)
{
// Используется тот же принцип, что и при добавлении
// элементов массива в конец списка
return Add(list, size);
}Конструкторы класса
Так как у нас определенно несколько различных конструкторов, то компилятор не создает конструктор по умолчанию, поэтому это задача ложится на плечи разработчика.
template<typename Item>
LinkedList<Item>::LinkedList()
{
// Установка всех полей в "0"
size = 0;
first = nullptr;
last = nullptr;
}Прочие конструкторы тоже не заключают в своей реализации особых сложностей.
template<typename Item>
LinkedList<Item>::LinkedList(Item item) // Создание одного узла
{
size = 1; // Установка размера списка в 1
// Создание узла и установка на него указателей
first = last = new LinkedList<Item>::Node;
// Через указатель first устанавливаем поля созданного узла
first->prev = nullptr;
first->next = nullptr;
first->item = item;
}
// Конструктор, инициализирующий созданный объект списком
template<typename Item>
LinkedList<Item>::LinkedList(const LinkedList<Item>& ll)
{
// Для начала установим указатели в "0"
// на случай, если будет совершена попытка инициализировать
// созданный объект пустым списком
first = last = nullptr;
size = 0;
// Просто вызываем метод добавления элемента,
// который внутри себя выставит все нужные поля объекта
for (int i = 0; i < ll.size; i++)
{
Add(ll[i], i);
}
}Перегрузка оператора []
Были реализованы две перегрузки оператора, одна для работы с константным объектом, другая — с неконстантным.
template<typename Item>
Item& LinkedList<Item>::operator[](int i)
{
// Небольшой костыль
// В дальнейшем можно добавить создание исключений
if (i < 0 || i >= size)
std::cout << "Выход за границы массива";
// С помощью приватного метода ищется нужный элемент
// и возвращается его полезное содержимое
return findElement(i).item;
}// То же самое, но для работы с константными объектами
template<typename Item>
Item LinkedList<Item>::operator[](int i) const
{
if (i < 0 || i >= size)
std::cout << "Выход за границы массива";
return findElement(i).item;
}Метод Delete
Удаление узлов в списке я поделил на два этапа:
- Удаление узлов
- «Сшивание» оставшихся узлов между собой
На первом этапе просто осуществляем последовательное удаление указанного количества узлов, начиная с указанной позиции. На втором этапе нужно восстановить целостность списка.
// По умолчанию удаляется один элемент, на который указывает pos
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Delete(int pos, int range)
{
// Очередной костыль)
if (pos < 0 || pos >= size)
std::cout << "Выход за границы массива";
// Так как в методе findElement используется поле size,
// то до полного "сшивания" списка размер не должен изменяться,
// в ином случае поиск будет осуществляться неверно.
// Поэтому в самом методе используется tempSize
int tempSize = size;
// Первый этап
// Последовательно удаляем нужное количество элементов,
// начиная с указанной позиции
for (int i = pos; i < pos + range && i < size; i++, tempSize--)
delete &findElement(i, down);
// Второй этап
// Если были удалены все элементы,
// то просто устанавливаем все указатели в "0"
if (tempSize == 0)
first = last = nullptr;
else
{
// В ином случае возможны три варианта:
// 1) Удалено определенное количество элементов, начиная с первого
// 2) Удалены узлы(не с первого) вплоть до последнего включительно
// 3) Удалены узлы(не с первого), но не доходя до последнего узла
if (pos == 0) // 1)
{
// Обновляем первый элемент списка
first = &findElement(pos + range, down);
first->prev = nullptr;
}
else
if (pos + range >= size) // 2)
{
// Обновляем последний элемент списка
last = &findElement(pos - 1);
last->next = nullptr;
}
else // 3)
{
// Сшиваем конец одного куска списка с началом другого
// down указывает нам о том, что поиск элемента идет сверху вниз
// Логично, что в одних случаях надо идти сверху вниз,
// а в других - наоборот
// Это вызвано появлением "пустого" участка в центре списка, ибо два куска его
// еще не сшиты между собой. Но у нас имеются указатели last и first,
// каждый из которых указывает на отдельный кусок и можно таким образом
//проводить поиск в каждом из них
findElement(pos - 1).next = &findElement(pos + range, down);
findElement(pos + range, down).prev = &findElement(pos - 1);
}
}
// Обновляем значение размера списка
size = tempSize;
return *this;
}// Удаление элемента в конце списка
template<typename Item>
LinkedList<Item>& LinkedList<Item>::Delete()
{
// Просто вызовем иную перегрузку, передав координаты конца
return Delete(size - 1);
}Деструктор класса
При выделении памяти операцией new необходимо реализовать деструктор, а не полагаться на создаваемый компилятором, ибо он производит так называемое «поверхностное» удаление. Нам же необходимо удалить все узлы, перед удалением самого объекта.
template<typename Item>
LinkedList<Item>::~LinkedList()
{
// Чтобы не дублировать код удаления всех элементов,
// можно просто вызвать функцию Delete, передав ей параметры для
// удаления всех узлов в списке
Delete(0, size);
}
Перегрузка оператора +
Оператор + не изменяет вызывающий его объект и список, участвующий в сложений, поэтому внутри метода нужно создать новый временный объект, который будет содержать в себе узлы из обоих списков, из-за этого не выйдет вернуть ссылку, так как объекты, созданные внутри метода, уничтожаются при выходе из него, и ссылка будет указывать на несуществующий элемент, говоря по-простому.
Стоит напомнить, что метод вызывается объектом, расположенным слева от знака +, а параметром является объект справа.
template<typename Item>
LinkedList<Item> LinkedList<Item>::operator+(const LinkedList<Item>& list) const
{
// Создаем временный объект, инициализируя
// вызвавшим его объектом
LinkedList<Item> temp(*this);
// Добавляем второй список
temp.Add(list);
return temp;
}Перегрузка оператора =
Главное, надо помнить о том, что перед тем, как записать значение операнда справа операнду слева, надо очистить левый операнд. Для этого в моем коде вызывается деструктор, хотя логичнее было бы вызвать просто метод удаления узлов списка. Но я применил этот метод, чтобы просто продемонстрировать явный вызов деструктора в методах класса.
Метод возвращает константную ссылку на объект, чтобы можно было использовать цепочку из операторов =. Это объясняется тем, что данный метод будет вызываться справа налево, и возвращаемое значение одного будет служить входным параметром для другого.
template<typename Item>
const LinkedList<Item>& LinkedList<Item>::operator=(const LinkedList<Item>& list)
{
// Очистка списка
if (size != 0)
this->~LinkedList();
// Запись в список новых узлов
Add(list);
// можно использовать так: list1 = list2 = list3;
return list;
// Если бы возвращаемое значение было void, то метод бы работал, но
// нельзя было бы использовать цепочку из приравниваний
}
Метод size
Пожалуй, тут комментарий излишни.
template<typename Item>
int LinkedList<Item>::Size()
{
return size;
}
Заключение
Можно было бы еще добавить сортировку и много других полезных функций, но для начала, думаю, такого функционала вполне достаточно. Буду рад ответить на любые вопросы или критику. И конечно же вот файл с кодом для скачивания. Обычно объявление класса и реализацию его методов записывают в разных файлах, но в случае шаблонных классов, необходимо все поместить в заголовочном. Спасибо за внимание.
Комментарии (27)
oleg-m1973
19.08.2019 16:29Плохая идея — работать со списком, как с массивом, по индексу элемента. Сложность получится O(N). Надо добавлять/удалять и т.д. по указателю на ноду.
amarao
19.08.2019 16:59+1Давайте я задам три сложных вопроса:
1) Зачем для реализации связного списка использовать Си (Си++)?
2) Знаете ли вы, что использование связного списка ломает кучу оптимизаций работы с кеш-памятью, т.е. очень медленное?
3) Чем связный список лучше, чем vector?GarryC
19.08.2019 17:46Не знаю, как ответит автор, но я бы ответил так:
1. Не вижу оснований, чтобы не использовать плюсы, ничуть не хуже любого другого
2. Сильное утверждение, требует доказательств, при последовательном выделении памяти список может быть совсем не медленным.
3. Он контролируемый, я понимаю, что велосипеды — это не выход, но часто встроенные типы для данной конкретной задачи оказываются не вполне эффективными, хотя истина, как и всегда, конкретна.
Но все вышеперечисленное ни в коей мере не оправдывает автора исходного поста в части интерфейса и доступ с индексом, скорее всего, будет намного быстрее на векторе, который под такой метод заточен изначально.amarao
19.08.2019 18:11Насколько я видел практику, связные списки практически всегда проигрывают другим структурам с большей гранулярностью аллокации.
Объясняю, какая у вас проблема при "последовательном выделении памяти".
- Каждый элемент — это sizeof(data) + size_t. Каждый элемент — это переход по ссылке, который оптимизируется хуже, чем последовательные операции над элементами в массиве. Например, если вы хотите что-то найти или просуммировать по списку — для вектора у вас будут интринзики, а для спска -нет.
- Каждая аллокация памяти — это обращение к аллокатору, который должен хранить информацию об этой аллокации, чтобы потом сделать free. Сколько бы там не было умнейших трюков, но а) free всё равно придётся позвать много раз, и malloc придётся позвать много раз, а это МЕЕЕДЛЕННО. Потому что куча много раз.
- Даже если вам повезло и данные идут подряд, то у вас будет пачка операций на каждый элемент, вместо ++.
berez
19.08.2019 19:32+4Попросили человека на собеседовании накидать двусвязный список, а он ни в зуб ногой. Стало ему интересно, он и изобразил как смог. Как по мне — подход к вопросу правильный. Да и по коду видно, что человек старался и все написал сам, без ансамбля — один поиск по индексу чего стоит. :)
А вы — про интринсики с аллокаторами… Прямо на взлете. :)
oleg-m1973
19.08.2019 18:01+1Список не хуже и не лучше, чем vector. Просто он нужен для других задач, которые при помощи массива решаются, как минимум, плохо.
mOlind
20.08.2019 11:07Именно. Чтобы понять какой контейнер подойдет лучше — нужно набросать тест с нагрузкой из реальной жизни и сравнить как будут вести себя два контейнера.
Я не уверен, был ли уже перевод на хабре, но гугл подсказывает хорошее сравнение: baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html Но и оно не гарантирует что в вашем приложении все будет так же. Надо делать тесты на своих типах, и на своей архитектуре, чтобы получить более-менее точный ответ.oleg-m1973
20.08.2019 21:22Подозреваю, для того, чтобы решить где использовать список, а где массив, тесты не нужны, достаточно просто подумать головой.
berez
20.08.2019 21:46Думанье головой — это всегда хорошо, но тесты я бы вот так сходу не отменял. Случаи бывают разные. Иногда на практике оказывается, что совершенно, казалось бы, неподходящий к задаче контейнер работает быстрее, чем теоретически абсолютно «правильный».
Например, бывали случаи, что вектор оказывался быстрее списка, хотя данные активно вставлялись в середину. Просто отведение памяти подтормаживало, а вот копирование объектов туда-сюда — нет.
dmxvlx
19.08.2019 23:48Мне приходилось писать кастомный аллокатор, там и использовал двусвязные списки, только у меня в нодах хранились блоки выделенной памяти, с постраничным выравниванием, а никак у автора — одно значение на ноду (для подобных задач есть деревья и иже с ними)
eandr_67
19.08.2019 17:04+2Набор реализованных операций не характерен для нормальных списков. Смысл списка в том, что в нём нет доступа по индексу, а есть перемещение текущей позиции (курсора) по элементам списка и работа только с тем элементом, на который указывает курсор. Для двусвязного списка набор основных операций:
- Перейти к первому элементу списка
- Перейти к последнему элементу списка
- Перейти к следующему элементу списка
- Перейти к предыдущему элементу списка
- Получить значение текущего элемента
- Заменить значение текущего элемента
- Добавить элемент перед текущим
- Добавить элемент после текущего
- Удалить текущий элемент
Дополнительно:
- Длина списка
- Предикат «текущий элемент является началом списка»
- Предикат «текущий элемент является концом списка»
- Поиск следующего/предыдущего элемента, имеющего заданное значение
- и т.д.
rrust
19.08.2019 18:06ну а для скорости произвольного доступа добавить HashTable, который годится и для односвязного списка. Просто бывают случаи когда произвольный доступ нужен в нескольких местах, а исходные данные в виде списка.
Hottych
19.08.2019 18:44Думаю стоит подождать еще какое-то время, пока не получится нечто еще более достойное. Выше уже все сказали. Delete выглядит ужасно. Поиск, кстати, тоже.
Почитайте stl, чтоли.
justhabrauser
19.08.2019 19:26+4Сейчас не модно RTFM. Сейчас модно в таком порядке:
1. написать что-нибудь
2. почитать доку по нестандартным либам
3. почитать доку по стандартным либам
4. почитать Страустроупа
5. почитать доку по языку
6. почитать Кнута
Именно в таком порядке.
Не наоборот.
PS. хотя насчет «почитать» я переборщил. Читать некогда — писать надо.
И в хабр обязательно.MooNDeaR
20.08.2019 14:47Да и слава богу :D Начинал я читать Кнута и Страуструпа в самом начале своего программисткого пути. Просто ужасные книги :)
Отличные справочники, но как учебные материалы, а уж темболее для новичков, просто полный отстой :) Это как предлагать учить математику с универского курса по матану. Нет, сам по себе матан в универе на непрофильных специальностях не особо сложный, но не для ученика 5го класса
justhabrauser
20.08.2019 21:29Здесь Вы совершенно правы.
Идеальный вариант — начинать с ассемблера.MooNDeaR
20.08.2019 21:37Пишу на С++ уже много лет. Даже приходилось писать драйвера как-то и немного прошивок под bare metal. Ни строчки в жизни на ассемблере не написал, да и вообще ассемблер не знаю толком. Никак не мешает работе и понимаю устройства процессора/памяти/стека/да чего угодно. Когда уж надо что-то такое посмотреть при отладке, что случается почти никогда, просто уходит чуть больше времени, потому что приходится гуглить команды ассемблера :)
Так что всем новичкам крайне советую — не учите ассемблер, только время потеряете. Даже если собираетесь писать на Си/С++. Вероятность того, что он вам понадобится, а особенно в тех задачах, которые вы будете решать в самом начале карьеры — околонулевая.
igormich88
19.08.2019 20:41+1
Я правильно понял что в случае выхода pos за границы, вы просто печатаете сообщенеи в консоль и продолжаете работу?LinkedList<Item>& LinkedList<Item>::Delete(int pos, int range) { if (pos < 0 || pos >= size) std::cout << "Выход за границы массива"; int tempSize = size; for (int i = pos; i < pos + range && i < size; i++, tempSize--) delete &findElement(i, down); ...Deosis
20.08.2019 07:58+1А вас не удивило, что автор для удаления одного элемента из списка проходит по нему пять раз?
alan008
19.08.2019 23:30+2Ой, на статью из песочницы сразу уж и минусов наставили. То есть не предположили вариант, что автор не имеет ещё совсем бэкграунда разработки и не очень понимает, зачем такая структура как двусвязный список может потребоваться в реальных задачах (структура довольно специфическая, если уж на то пошло). Автор поигрался с языком, что-то реализовал и оно даже как-то работает. Что же в этом плохого? Никаких особых ужасов в приведённых фрагментах кода нет, да там есть ненужные или неоптимальные вещи, но это ведь просто учебная задача, отвязанная от конкретики, так что я считаю что минусы — проявление классической злобы Хабра из серии "мы тут все умнее, не надо нам капитанства от юниоров", но призываю все-таки быть подружественнее к новичкам, а то так любой сеньор может отбить у юниора желание вообще что-либо делать, набивать шишек и учиться на своих ошибках, хотя этот сеньор 5-10 лет назад сам был точно таким же.
GarryC
20.08.2019 09:28Дело в том, что нам действительно не нужно «капитанство от юниора». Я, конечно, минусов не ставил, это вообще не в моих правилах, но, если бы в посте была вводная часть, как Вы верно заметили, о месте подобной структуры и объяснение необходимости, довольно таки загадочных, операций на списке с индексами, то было бы намного лучше, если не совсем хорошо.
Кстати, о необходимости двусвязного списка. Давным давно (лет 20 назад), в одной далекой Галактике (программе для АТС на микроконтроллере х51) для хранения списка активных абонентов, требующих частого внимания, я применял именно такой список, поскольку любые аллокаторы на таком МК… ну Вы понимаете.
Да и в современных разработках такие решения вполне имеют место, посмотрите FreeRTOS, к примеру.
Hottych
20.08.2019 16:27Меня смущает, что кто-то найдет эту статью и попытается использовать данную реализацию листа. А новичек, который научился на коде другого новичка — это страшно.
Часть функций реализована действительно ужасно. И тут вопрос не в том, что «не достоин», а в том, что это нельзя показывать кому-либо.
Минусов не ставил.alan008
20.08.2019 16:34Сейчас на просторах Инета столько всякой всячины валяется, из которой сложно что-либо рекомендовать к использованию, однако это не мешает процветанию говнокода практически во всех проектах, т.к. все равно все гуглят "как сделать, чтобы работало". Такова жизнь)
maximw
20.08.2019 19:03Нет ничего плохого в таких упражнениях. Это очень даже хорошо. Но зачем про это писать статью на Хабре?
Это не злоба, это самоочищение сообщества от ненужного, а иногда и вредного, контента.
maksqwe
Та, это уже не интересно делать, сколько такого добра на просторах интернета валяется. Вот если бы сделали формальное доказательство на языке Idris, тогда что-то интересное и могло бы получиться… Вот как тут:
habr.com/ru/post/463957
п.с.: шутка