Бюро по регистрации патентов и торговых марок США не перестаёт нас удивлять: в апреле 2006 года оно выдало компании LSI Logic Corporation патент на связный список. Связные списки используются практически в любой программе, а значит любая компания-разработчик в США теоретически оказывается под угрозой судебного иска. Впрочем, вряд ли компания сможет отстоять своё «изобретение» в суде, так как связные списки появились ещё в середине 50-х годов прошлого века.
На всякий случай напомню, что такое связный список. Связный список — структура данных, представляющая из себя набор элементов, каждый из которых состоит из двух частей: собственно данных и ссылки-указателя на следующий элемент. Это одна из простейших структур данных, она используется повсеместно, например, для реализации стека, очереди, хеша, списков с пропусками и т. п.
В патенте описана одна из разновидностей списка, а именно двусвязный список. Элементы двусвязного списка содержат два указателя: на следующий и предыдущий элементы. Благодаря этому список можно просматривать как вперёд, так и назад. Сравните с кратким описанием патента: «Компьютерный список снабжается вспомогательными указателями для обхода списка в разных направлениях. Один или несколько вспомогательных указателей обеспечивают быстрый, последовательный обход списка с минимальными затратами вычислительного времени. Такие списки могут использовать в любых приложениях, в которых требуется различные сортировки списка для различных задач». Компании потребовалось целых четыре года, чтобы запатентовать свой алгоритм. Возможно, они просто искали в Бюро кого-то, кто не знает о связных списках?
На всякий случай напомню, что такое связный список. Связный список — структура данных, представляющая из себя набор элементов, каждый из которых состоит из двух частей: собственно данных и ссылки-указателя на следующий элемент. Это одна из простейших структур данных, она используется повсеместно, например, для реализации стека, очереди, хеша, списков с пропусками и т. п.
В патенте описана одна из разновидностей списка, а именно двусвязный список. Элементы двусвязного списка содержат два указателя: на следующий и предыдущий элементы. Благодаря этому список можно просматривать как вперёд, так и назад. Сравните с кратким описанием патента: «Компьютерный список снабжается вспомогательными указателями для обхода списка в разных направлениях. Один или несколько вспомогательных указателей обеспечивают быстрый, последовательный обход списка с минимальными затратами вычислительного времени. Такие списки могут использовать в любых приложениях, в которых требуется различные сортировки списка для различных задач». Компании потребовалось целых четыре года, чтобы запатентовать свой алгоритм. Возможно, они просто искали в Бюро кого-то, кто не знает о связных списках?
