Приложения связанных списков

Каковы хорошие примеры применения связанного списка? Я знаю, что это хорошая идея - реализовывать очереди и стеки в виде связанных списков, но есть ли практический и прямой пример связанного списка, решающего проблему, которая конкретно использует преимущества быстрого времени вставки? Не только другие структуры данных, основанные на связанных списках.

Надеемся получить ответы, похожие на этот вопрос о приоритетных очередях: Приложения с приоритетной очередью

Я нашел один: кеш LRU (использовался реже всего), реализованный с помощью хеш-таблицы и связанного списка.

Есть также пример класса Exception, имеющего InnerExeption

Что еще там есть?

4 голоса | спросил Matthew Sainsbury 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 14 Sep 2013 15:57:02 +0400 2013, 15:57:02

3 ответа


0

Я работаю разработчиком на "большом фондовом рынке" в США. Часть того, что заставляет нас работать с очень высокой скоростью, заключается в том, что мы не делаем никакого распределения /перераспределения кучи после инициализации (до начала дня на рынке). Этот метод не уникален для бирж, он также распространен в большинстве систем реального времени.

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

  • Одним из приложений является предварительное распределение всех объектов в пулы (которые являются связанными списками) во время инициализации; поэтому всякий раз, когда нам нужен новый объект, мы можем просто удалить заголовок списка.
  • Другое приложение находится в обработке заказа; каждый объект Order реализует интерфейс записи связанного списка (имеет предыдущую и следующую ссылку), поэтому, когда мы получаем заказ от клиента, мы можем удалить объект Order из пула и поместить его в список «для обработки». Поскольку каждый объект Order реализует запись в связанном списке, добавление в любой точке списка так же просто, как заполнение предыдущей и следующей ссылок.

Пример с макушки головы:

Interface IMultiListEntry {

    public IMultiListEntry getPrev(MultiList list);
    public void setPrev(MultiList list, IMultiListEntry entry);

    public IMultiListEntry getNext(MultiList list);
    public void setNext(MultiList list, IMultiListEntry entry);

}

Class MultiListEntry implements IMultiListEntry {

    private MultiListEntry[] prev = new MultiListEntry[MultiList.MAX_LISTS];
    private MultiListEntry[] next = new MultiListEntry[MultiList.MAX_LISTS];

    public MultiListEntry getPrev(MultiList list) {
        return prev[list.number];
    }
    public void setPrev(MultiList list, IMultiListEntry entry) {
        prev[list.number] = entry;
    }

    public IMultiListEntry getNext(MultiList list) {
        return next[list.number];
    }
    public void setNext(MultiList list, IMultiListEntry entry) {
        next[list.number] = entry;
    }

}

Class MultiList {

    private static int MAX_LISTS = 3;
    private static int LISTS = 0;

    public final int number = LISTS++;

    private IMultiListEntry head = null;
    private IMultiListEntry tail = null;

    public IMultiListEntry getHead() {
        return head;
    }

    public void add(IMultiListEntry entry) {
        if (head==null) {
            head = entry;
        } else {
            entry.setPrevious(this, tail);
            tail.setNext(this, entry);
        }
        tail = entry;
    }

    public IMultiListEntry getPrev(IMultiListEntry entry) {
        return entry.getPrev(this);
    }
    public IMultiListEntry getNext(IMultiListEntry entry) {
        return entry.getNext(this);
    }
}

Теперь все, что вам нужно сделать, это либо расширить MultiListEntry, либо реализовать IMultiListEntry и делегировать методы интерфейса внутренней ссылке на объект MultiListEntry.

ответил Justin 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 14 Sep 2013 18:08:48 +0400 2013, 18:08:48
0

Ответа может быть бесконечно много, и «хороший пример» - это субъективный термин, поэтому ответ на ваш вопрос весьма спорен. Конечно, есть примеры. Вам просто нужно подумать о возможных потребностях быстрой вставки.

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

Чтобы дать вам другой пример: у вас есть набор имен, упорядоченных в алфавитном порядке. Давайте предположим, что каким-то образом вы можете быстро определить объект, следующий пункт которого указывает на объект, в котором хранится определенное имя. Если вы хотите быстро удалить имя, вы просто переходите к предыдущему элементу объекта, который нужно удалить. Удаление также происходит быстрее, чем в случае стеков или очередей.

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

ответил Lajos Arpad 14 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 14 Sep 2013 17:30:40 +0400 2013, 17:30:40
0

hashmaps в java использует представление списка ссылок. Когда более одного ключа хэшируется в одном месте, это приводит к коллизии, и в это время ключи объединяются в цепочки, как список ссылок.

ответил Sonia Chawla 21 PM00000010000001831 2017, 13:44:18

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132