Можно ли спасти LinkedList? Пишем быстрый List на связном списке

[pda0]

Упрощённая реализация SkipList. :)

[qideil]

SkipList – вероятностная структура данных. Здесь же просто использование дополнительной памяти для достижения преимущества в случае неправильного выбора структуры данных.

[SFH]

спасибо за ссылку, очень любопытно!

[lazy_val]

Существует мнение, что LinkedList - неудачная коллекция и всегда и везде лучше использовать ArrayList. А LinkedList - это для стеков и очередей, да и то не факт

Во встроенной БД Prometheus связные списки вовсю используются для управления изоляцией транзакций, Это к примеру. Далеко не единственному, кстати.

Правда, это Go. Ваше утверждение только к Java относится? Или разработчик Prometheus пошли по неправильному пути?

[SFH]

Речь, конечно, о Java. С Go я не знаком и как там реализованы коллекции не знаю.

[qideil]

Зачем пытаться использовать структуру данных не по назначению? LinkedList не используют там, где нужен ArrayList, и наоборот. Или для вас HashSet и TreeSet тоже взаимозаменяемы?

[Falakure1234]

А в чем вообще отличие arraylist и linkedlist? Где-то array list используется?

[SFH]

ну, во-первых, потому что ArrayList тоже не идеален, во-вторых, применимость LinkedList сильно ограничена теми проблемами что я описал, а именно, O(N) в рандомных операциях.

Почему бы не ускорить коллекцию, не теряя функциональности? Ведь внутри - все тот же двусвязный список со всеми возможностями. только быстрее

[qideil]

Вы тратите дополнительную память улучшая то, что не нуждается в улучшении. Выбирайте правильные структуры для конкретной задачи, а не пытайтесь исправить то, что замечательно работает. Нужны «рандомные» операции — используйте ArrayList, а LinkedList оставьте для других задач. У них даже контракты разные, если уж на то пошло. И как уже сказали выше, можете использовать любую из существующих имплементаций SkipList.

[XViivi]

Я так понимаю, эта структура данных позволяет проделывать чтение, запись, вставку и удаление за O(√n), верно?

Но нельзя ли тогда уж использовать дерево, чтобы каждая операция была за O(log n)?

Или же какие свойства св. списка имеются ввиду?

[Yami-no-Ryuu]

Это структура для накопления и последовательной итерации, в одну сторону.

[SFH]

1. дерево требует компаратора, что ограничивает область применения.

2. есть интерфейс List, он очень популярен, но одна из стандартных реализаций неудачная. идея была в том, чтобы проверить, можно ли ее улучшить, сохранив базовые свойства. Оказалось, можно. Это было, для меня, интересное иследование.

[npoKA3Hbuk]

По поводу 1. поправьте, если ошибаюсь, но в нашем случае всегда будет компаратор интов (причем можно просто примитивы сравнивать), как как ключом в дереве будут индексы List.

[zzzzzzzzzzzz]

То, что LinkedList не подходит для доступа по индексу, очевидно из его устройства. То, что ArrayList не подходит для вставки в начало, также очевидно из его устройства. Единственные интересные тут числа - это что вставка в конец LinkedList медленнее, чем в ArrayList. Видимо, операции с выделением памяти такие дорогие.

Предложенную структуру тоже не очень понимаю, зачем надо было изобретать. Если довести такое кэширование до крайнего состояния, то получится дерево. И не вижу причин, чтобы как раз его и не использовать. Было бы интересно, если бы, например, TreeMap тоже присутствовал в испытаниях.

[cupraer]

Если надо добавлять элементы в конец связного списка, то люди обычно его инвертируют, добавляют все, что нужно, в начало, а потом инвертируют обратно. В эрланге, например, массивов вообще 40 лет не было, и это никому не мешало.

[SFH]

1. идея была - улучшить LinkedList, сделать его пригодным для реального использования.

2. простестирую и treemap, интересно, что получится

[Kealon]

2. LinkedHashMap по идее

3. Весосбалансиррванное дерево позволяет по индексу доступ получить.

4. Ну и третий фокус, о котором забывают - хранение сервисных указателей в самих объектах

Ps: странно номера показывает( при редактировании с 1)

[just_vladimir]

1. Чем вы меряете производительность? Неужели для микробенчмарков в 2025 кто-то использует не JMH?

2. Проблема связного списка не в алгоритмической сложности, а в том как устроено современное железо.

[SFH]

простым System.currentTimeMillis()

[AlekseyShibayev]

Интересно, спасибо за статью.

1. Добавь, пожалуйста, сравнение по памяти.

2. Всё-таки самое частое использование List - добавление в конец с последующей итерацией. И в таком кейсе использования ваша структура и LinkedList делают доп нагрузку на хип. К тому же ArrayList можно сразу задать нужного размера.

p.s. а ещё есть стримы)

[SFH]

спасибо за идею, сделаю тесты по памяти, но быстро не обещаю

[cupraer]

самое частое использование List - добавление в конец с последующей итерацией

В этом случае надо взять LinkedList, добавлять в начало, а потом его развернуть.

[AnonimYYYs]

Странно, почему для add рассмотрели и first/last, и random, а для всех остальных операций - только random?

В целом, что получится, я конечно понимаю. Но все таки в рамках "исследования" такие нюансы выглядят как попытка чего-то там

[SFH]

Обычно при реальном использование добавление происходит именно в конец, поэтому его стоит рассматривать отдельно. А вот удаление, обновление, и получение - это рандомные операции, которые происходят с каким-либо уже существующим объектом.
Впрочем, я мог и ошибиться с методологией. Безусловно, результаты смешанного теста зависят от процентовки операций. Если вы предложите другое распределение, я могу прогнать и его.

[WDeath]

Есть мысль, что это съест не мало памяти. Может по этому не заменили ещë arrayList?

[Gabenskiy]

Прикольная статья. Мне пришла мысль, что это чем-то похоже на задачку с собеса: вот тебе проблема и решай. Остался только один вопрос: в промышленном коде кто-то такое применял?

[MaxSidorov]

Мне кажется есть отличный класс ArrayDeque который умеет все что умеет LinkedList но при этом уделывает его по скорости в разы и по памяти тоже.

Все таки массивы работают намного эффективней, чем созлание инстансов и хранение по 3 указателя на элемен