Пример использования связного списка?

Расскажите, пожалуйста, про случай из практики программирования на Си-подобном языке, когда реально понадобился связный список. У меня такого случая не было никогда и придумать сходу ситуацию, в которой бы он понадобился, не получилось.

Это должен быть случай, когда надо постоянно удалять и вставлять элементы с помощью итератора, который постоянно живет где-то внутри списка.

Меня удивляет лоббирование связного списка. На Гитхабе стандартный явовский связный список LinkedList встречается чаще, чем TreeSet, TreeMap и ArrayDeque вместе взятые: github.com/search?l=java&q=LinkedList&ref=searchresults&type=Code. Каждый день только из-за присутствия связного списка в стандартных библиотеках Си-подобных языков на серверах сжигается лишнее электричество на десятки тысяч долларов.

Знаю, правда, одно применение связного списка как модели — для реализации lock-free списков и очередей, но не как самостоятельной структуры.
  • Вопрос задан
  • 13460 просмотров
Пригласить эксперта
Ответы на вопрос 9
Artem_zin
@Artem_zin
Я в общем-то спорить не хочу, вы скорее всего LinkedList просто «алгоритмически» не взлюбили и троллите его :)

Да, применений у него мало, конкретно так мало. В основном кто-нибудь всунет куда не надо по незнанию и потом сиди разгребай в чем проблема.

Но все же, для списка слушателей я использую именно LinkedList т.к. все что я перечислил выше + он ожидаемо ведет себя во всех ситуациях при данном использовании и не создаст мне неожиданных проседаний производительности (маааленьких, но все же), как тот же ArrayList если я просто хочу добавить/удалить слушателя не парясь заранее об их количестве.

Вам понравится подход к отделению LinkedList в C# от просто списков, там он не реализует IList и случайно применить его не выйдет, только если как коллекцию и то вряд ли, там ArrayList называется List и большинство даже не в курсе про LinkedList.

В статье снизу список с результатами среднего времени по операциям:
(наносекунды, меньше лучше)

ArrayList add:    13265642
LinkedList add:    9550057

ArrayList get:       1543352
LinkedList get:     85085551

ArrayList remove:    199961301
LinkedList remove:    85768810


Вот. Просто такое ощущение, что вы задали вопрос чтобы убедится в правоте своего мнения и других слушать не хотите :)
Ответ написан
apangin
@apangin
Аллокатор памяти, например, классический malloc.
Ответ написан
alexeygrigorev
@alexeygrigorev
Переворачиватель пингвинов
В хеш таблицах используются связные списки, а не списки на массивах
Ответ написан
Комментировать
@vScherba
Не скажу за все языки, но в C++ std::list редко бывает эффективнее других контейнеров. Но бывают случаи, когда он предпочтительнее, например, в графовых структурах данных типа Boost Graph Library.
Ответ написан
Artem_zin
@Artem_zin
Отвечу как разработчик на Java и C#, связные списки применяю очень редко и осторожно, но есть один кейс, в котором лучше него структуры нет — список слушателей какой-нибудь фигни. Почему? Потому что памяти ест мало а используется только для последовательного чтения, удаления с любого места в списке, а связный список самая оптимальная структура данных для этого.

Пример на Java:

public class ObservableValue {

        public interface Observer {
            void onValueChanged(Object newValue);
        }

        private Object value;
        private final List<Observer> observers = new LinkedList<Observer>();

        public Object getValue() {
            return value;
        }

        public void setValue(Object newValue) {
            this.value = newValue;
            notifyOnValueChanged(newValue); // уведомляем слушателей
        }

        // дешевая вставка объекта
        public void addObserver(Observer observer) {
            observers.add(observer);
        }

        // дешевое удаление с любого места в списке
        public boolean removeObserver(Observer observer) {
            return observers.remove(observer);
        }

        // дешевое чтение т.к. не по индексу, а последовательно
        private void notifyOnValueChanged(Object newValue) {
            for (Observer observer : observers) {
                if (observer != null) observer.onValueChanged(newValue);
            }
        }

    }


Если найдете структуру данных, которая подойдет лучше — скажите мне пожалуйста :)
Ответ написан
batment
@batment
Таблица файловой системы FAT. Насчет остальных систем не знаю.
Ответ написан
asm0dey
@asm0dey
LinkedList нужен там, где с одной стороны нужны листы. А с другой — быстрые вставки в середину. Примеров не много, но вот два:
1) Нам периодически приходят обновления о том, что объект из списка пропал. И происходит это часто, а объектов много. Например нам сообщают, что машина продана.
2) Удобно составлять цепи событий, куда можно вставлять промежуточные события.
Ответ написан
Комментировать
@hasu0
Как уже сказали выше — хеш таблица. Если заглянуть в реализацию std::unordered_map, то там все элементы выстроены в список, а в таблице хранятся итераторы на элементы этого списка. Такая структура позволяет и проитерироваться по всем элементам таблицы, и удалить элемент за константное время.
Ответ написан
Комментировать
В java LinkedList -- это идеальная реализация очереди для большинства случаев.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы