Выбор структуры данных
Один из основных недостатков двухсвязного списка считается скорость поиска элемента в нем, его сложность будет равна O (n), тогда как в бинарном дереве сложность поиска элемента равна O (log n), но на самом деле этот недостаток легко решается при помощи бинарного поиска. Так как блоки в списке расположены последовательно, то их адреса отсортированы по возрастанию, что дает возможность применить… Читать ещё >
Выбор структуры данных (реферат, курсовая, диплом, контрольная)
Систему двойников можно реализовать на нескольких структурах данных, основными являются: бинарное дерево и двухсвязный список.
Основным преимуществом двухсвязного списка является простая реализации, особенно, если разработка ведется с использованием языка программирования C#, так как в нем есть стандартный класс, реализующий двунаправленный связанный список.
В отличие от бинарного дерева список использует меньше памяти, так как при разбиении блока, он будет удаляться, в отличие от бинарного дерева, где старый блок сохраняется. Но за это преимущество двухсвязный список платит таким недостатком как скорость выполнение, так как будет потрачено время на удаление при разделении и создания блоков при соединении двойников.
Один из основных недостатков двухсвязного списка считается скорость поиска элемента в нем, его сложность будет равна O (n), тогда как в бинарном дереве сложность поиска элемента равна O (log n), но на самом деле этот недостаток легко решается при помощи бинарного поиска. Так как блоки в списке расположены последовательно, то их адреса отсортированы по возрастанию, что дает возможность применить бинарный поиск и получить сложность поиска элемента O (log n), как и у бинарного дерева.
Взвесив все за и против, я решил использовать двухсвязный список из-за простоты его реализации.