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

Question

[leventov]

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

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

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

Знаю, правда, одно применение связного списка как модели — для реализации lock-free списков и очередей, но не как самостоятельной структуры.

Comments

[Eddy_Em]

Зачем именно итератор? Связный список может быть просто структурой {sometype *data; list* next}, сам таким пользуюсь. Особо полезным такой список является при построении «динамического» массива. Ну, а когда уже количество элементов известно, можно перенести содержимое этого монстра в нормальный массив, чтобы ускорить работу.

[leventov]

Eddy_Em давайте поспорим, что если вы замените этот список на обычный vector<sometype&> (или как там надо в c++ писать), то станет быстрее.

[Eddy_Em]

Я не использую C++: у меня нет ни одной задачи, где плюсы нужны были бы. У меня только чистый С.
Понятное дело, в плюсах уже есть эти списки и городить свои костыли не нужно. А в сях это либо велосипеды (правда, размер маленький — поэтому есть смысл велосипедить), либо уродливая glib.

[wander]

Не будет быстрее на тех задачах, где нужно удалять из середины или с начала. Или если требуется постоянная вставка в середину или в начало. Вектор в С++ требует непрерывной памяти для всех элементов (как в обычном С-массиве) поэтому при вышеперечисленных операциях постоянно будет вызываться копирование и(или) переаллокация всех элементов.

[leventov]

wander если нужно часто удалять с хвостов, deque быстрее связного списка. До середины связного надо еще дойти, поэтому кроме описанного в вопросе случая, которому я не придумал, впрочем, реального применения, основанные на массивах структуры быстрее.

[wander]

Не стоит увиливать :) Вы правы насчет deque, но первоначально речь шла про vector:

давайте поспорим, что если вы замените этот список на обычный vector<sometype&> (или как там надо в c++ писать), то станет быстрее.

Answer 1

[Artem Zinnatullin]

Я в общем-то спорить не хочу, вы скорее всего 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

Вот. Просто такое ощущение, что вы задали вопрос чтобы убедится в правоте своего мнения и других слушать не хотите :)

Comments

[Artem Zinnatullin]

Извиняюсь за отдельный ответ, видимо не в то поле начал писать

[leventov]

import org.openjdk.jmh.annotations.*;

import java.util.*;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class Lists {

    @State
    public static class AL extends ArrayList<Object> {
        @Setup(Level.Invocation)
        public void fill() {
            Object x = new Object();
            for (int i = 0; i < 1000; i++) {
                add(x);
            }
        }
    }
    @State
    public static class LL extends LinkedList<Object> {
        @Setup(Level.Invocation)
        public void fill() {
            Object x = new Object();
            for (int i = 0; i < 1000; i++) {
                add(x);
            }
        }
    }

    @GenerateMicroBenchmark
    public int arrayList_add() {
        List<Object> list = new ArrayList<>(1000);
        Object x = new Object();
        for (int i = 0; i < 1000; i++) {
            list.add(x);
        }
        return list.size();
    }

    @GenerateMicroBenchmark
    public int linkedList_add() {
        List<Object> list = new LinkedList<>();
        Object x = new Object();
        for (int i = 0; i < 1000; i++) {
            list.add(x);
        }
        return list.size();
    }

    @GenerateMicroBenchmark
    public int arrayList_remove(AL list) {
        for (int i = 999; i >= 0; i--) {
            list.remove(i / 2);
        }
        return list.size();
    }

    @GenerateMicroBenchmark
    public int linkedList_remove(LL list) {
        for (int i = 999; i >= 0; i--) {
            list.remove(i / 2);
        }
        return list.size();
    }
}

t.Lists.arrayList_add         avgt   1     20    0        5,234        0,019  usec/op
t.Lists.arrayList_remove      avgt   1     20    0       82,344        0,201  usec/op
t.Lists.linkedList_add        avgt   1     20    0        6,417        0,032  usec/op
t.Lists.linkedList_remove     avgt   1     20    0      219,556        0,545  usec/op

[Artem Zinnatullin]

Какой читерский бенчмарк в пользу ArrayList. ArrayList создан сразу под количество элементов (соответственно вставка быстрая), удаление по индексу из LinkedList, ну тут и говорить не о чем. Тогда уж надо расходы по памяти смотреть, если после каждого remove вы не делаете trim.

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

Естественно в 99% нужно использовать ArrayList в качестве реализации списка, это да. То, что есть куча кода в тысячах проектов где по незнанию всунули LinkedList не означает, что он не нужен в принципе. Просто необходимо огородить его такого опасного использования, это да.

[leventov]

А откуда еще удалять? Если из начала, то ArrayDeque лучше.

С остальным согласен.

[Artem Zinnatullin]

Удалять в примере со слушателями надо не по индексу а по ссылке на объект, будет последовательный перебор пока не найдется equals элемент. Соответсвенно, сам перебор по скорости ~одинаков для ArrayList и LinkedList, а удаление с оптимальным использованием памяти и по времени, очевидно, быстрее в LinkedList.

Были бы структуры данных, применение найдется, никакого лобби нет :)

[leventov]

Реальные слушатели вряд ли будут сравниваться обходом кучи полей, скорее сведется к проверке на равенство ссылок. В этом случае ArrayList будет в разы быстрее

[Artem Zinnatullin]

Мм, а ведь про сравнение ссылок — вы правы, хотя скорее всего операция удаления скомпенсирует этот провал с лихвой :)

В общем, мы неплохо поговорили, предлагаю закрыть дискуссию

Answer 2

[apangin]

Аллокатор памяти, например, классический malloc.

Comments

[leventov]

Ссылочные структуры безусловно бывают полезны, особенно когда есть ссылки на внутренние узлы. В вашем примере ссылки организованы так, что вообще не занимают лишнего места. Мое недовольство вызывает лоббирование конкретно std::list и java.util.LinkedList.

[leventov]

Кстати, спасибо за ссылку. Отличное чтение.

Answer 3

[Ололёша Ололоев]

В хеш таблицах используются связные списки, а не списки на массивах

Answer 4

[vScherba]

Не скажу за все языки, но в C++ std::list редко бывает эффективнее других контейнеров. Но бывают случаи, когда он предпочтительнее, например, в графовых структурах данных типа Boost Graph Library.

Comments

[leventov]

Кто-нибудь реально сравнивал? Больше походит на очередной пример связного лобби

Answer 5

[Artem Zinnatullin]

Отвечу как разработчик на 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);
            }
        }

    }

Если найдете структуру данных, которая подойдет лучше — скажите мне пожалуйста :)

Comments

[leventov]

Далеко ходить не надо — ArrayList подойдет лучше. LinkedList ест больше памяти при любом количестве элементов. В т. ч. при 1, 2 или 3 элементах. (Если использовать не конструктор по умолчанию, а new ArrayList(2), например.)

[Artem Zinnatullin]

А если подписчики постоянно добавляются/убавляются, причем неравномерно :) это, конечно, шутка.

А теперь серьезно. Вы ведь сравнили только по памяти, а как же сложность операций? Добавление элемента может вызвать увеличение ArrayList, а это время (малое конечно т.к. System.arrayCopy() быстрый по максимуму, но все же это время) или наоборот удаление элемента точно приведет к копированию массива.

Я сейчас хочу график где-нибудь найти сравнения по памяти LinkedList и ArrayList, если найдете, поделитесь пожалуйста.

[leventov]

Если серьезно — то тут не о чем говорить, конечно ArrayList быстрее по операциям над подписчиками.

LinkedList = заголовок + поле с размером (4 байта) + 2 ссылки + Нода * кол-во элементов
Нода = заголовок + 3 ссылки
ArrayList = заголовок + поле с размером (4 байта) + ссылка на массив + заголовок массива + ссылка * кол-во элементов

Начиная с 1 элемента LinkedList занимает больше

[Кайгородов Алексей]

«Начиная с 1 элемента LinkedList занимает больше» — но при удалении элементов память LinkedList'a стремится к нулю, а у ArrayList'a остается максимальной.

[Artem Zinnatullin]

Ну ок, по памяти верю, но еще раз про время операций?

Нашел дурацкое, но все же какое-то сравнение перформанса ArrayList и LinkedList http://java.dzone.com/articles/arraylist-vs-linkedlist-vs

Вставка и удаление работают быстрее в LinkedList, это факт, к тому же после удаления предлагаете каждый раз вызывать trim() у ArrayList, если уж о памяти заботится?

При последовательном чтении (через итератор естественно) производительность будет одинакова, все равно объекты по памяти раскиданы и для массивов (т.к. в них только ссылки, если мы про Java)

[leventov]

Вставка и удаление работают быстрее в LinkedList

В статье я этого не нашел, а если бы нашел, это бы означало, что ее написал не очень компетентный человек.

Производительность не будет одинакова, потому что будет в 2 раза больше хождений по ссылкам.

Я вообще не собирался доказывать, что ArrayList быстрее LinkedList во всех случаях, кроме, может быть, описанного в вопросе, потому что на мой взгляд это было совершенно очевидно. Ваше мнение лишь доказывает силу лобби связного списка

Answer 6

[batment]

Таблица файловой системы FAT. Насчет остальных систем не знаю.

Comments

[leventov]

Судя по Википедии более современные ФС используют Bitmap (что бы это не значило в контексте ФС), да и я бы не назвал FAT примером выдающегося дизайна, но принимается

Answer 7

[asm0dey]

LinkedList нужен там, где с одной стороны нужны листы. А с другой — быстрые вставки в середину. Примеров не много, но вот два:
1) Нам периодически приходят обновления о том, что объект из списка пропал. И происходит это часто, а объектов много. Например нам сообщают, что машина продана.
2) Удобно составлять цепи событий, куда можно вставлять промежуточные события.

Answer 8

[hasu0]

Как уже сказали выше — хеш таблица. Если заглянуть в реализацию std::unordered_map, то там все элементы выстроены в список, а в таблице хранятся итераторы на элементы этого списка. Такая структура позволяет и проитерироваться по всем элементам таблицы, и удалить элемент за константное время.

Comments

[Stepan524]

почему в хеш таблице хранятся именно связные списки, а не деревья поиска? поиск был бы быстрее чем "проитерироваться" за линейное время

Answer 9

[Борис Ванин]

В java LinkedList -- это идеальная реализация очереди для большинства случаев.

Comments

[leventov]

Хуже ArrayDeque почти всегда.

[Борис Ванин]

leventov: Вы правы, спасибо за полезную информацию! Получается, что LinkedList произоводительнее только для операции удаления в позиции итератора.

[Борис Ванин]

И добавление элемента для ListIterator-а