> Ну если для тебя использовать стандартную либу западло, а написать реализацию связного
> списка самому является слишком сложной задачей, то наверное в Go тебе
> еще рано. Поищи себе ЯП в котором связные списки есть на
> уровне языка. Интересно, есть ли такой вообще.Это есть в LISP. Но ни в лиспе, ни где-либо ещё я не буду создавать список из 10k элементов. Если так уж всё упирается во вставки и удаления, то напрашиваются оптимизации массива, а не список из 10k элементов.
Во-первых, можно пересмотреть алгоритм, которому нужно вставлять и удалять, и что-нибудь в нём поменять, с тем чтобы либо не надо было бы вставлять/удалять, либо чтобы при вставках/удалениях можно было бы игнорировать порядок элементов. Во-вторых, операции вставки и удаления можно выполнять батчами по нескольку штук. В-третьих, на крайняк, можно создать что-то a la gap-buffer'а, имеющего N gap'ов, что, в среднем, поделит время вставки/удаления на N (если N на два-три порядка меньше 10000), ценой увеличения времени рандом-акцесса с O(1) до O(log(N)).
Первые две альтернативы, кстати, вполне себе объединяются в одну: если совсем отказаться от упорядоченности нельзя, то элементы можно вставлять в конец массива, удалять их можно тоже с конца массива, предварительно переместив их туда операцией swap. А перед операциями требующими упорядоченности выполнять сортировку массива каким-нибудь алгоритмом, заточенным на сортировку "почти отсортированных" массивов, который будут давать "почти линейное" время сортировки. Или их можно не объединять, но придумать свой lazy-"процессор" вставок/удалений, который получая запросы на вставки/удаления будет лишь записывать, что надо сделать, но ничего не делать, а когда придёт время, он возьмёт список вставок/удалений, оптимизирует его, переупорядочив их так как ему удобнее и выполнит одним проходом по массиву. Это будет гораздо сложнее, чем push+swap_remove+sort (что минус с точки зрения возможности дальнейшей поддержки кода), и не факт, что даст выигрыш по скорости, но если заняться нечем и хочется реализовать свой контейнер, то отличная практика для скиллов составления алгоритмов.
Если вставка/удаление в случайные места массива тормозит, и требуется оптимизация, то замена массива на список -- это не оптимизация, а жест отчаяния. Если же массив не тормозит, то тем более не стоит заменять его на список. В lisp'е можно создать список вместо массива, но только если этот список достаточно мелкий, и если это происходит в коде, производительность которого нас не колышет, и это в lisp'е, просто потому что в нём очень удобно работать со списками, гораздо удобнее чем с массивами.
