Являются ли LinkedLists не интуитивным решением, поскольку в большинстве случаев мне не нужно знать физическое местоположение элемента в коллекции?

Question

Недавно коллега показал мне код, который он написал с помощью LinkedList, и я не мог разобраться с этим.

a -> b -> c -> d -> e -> f

Если я хочу получить d из LinkedList, разве мне не нужно просматривать список, начиная с a и повторяя до d или начиная с f и возвращаясь к d?

Зачем мне дело, ГДЕ физически хранится в Коллекции?

Answer 1

Не каждый связанный список связан в обоих направлениях, но, как правило, да. Этот тип коллекции имеет последовательный доступ в прямом или обратном и обратном направлениях.

Преимущества:

• наименьший объем памяти, кроме плоского массива
• очень быстрая вставка и удаление
• память может быть выделена и освобождена по одному элементу за раз
• легко реализовать (не так важно для современных языков, но важно в C89 и C99)
• Возможен заказ LIFO или FIFO

Answer 2

Я думаю, что правильный вопрос не ГДЕ, а КАК в нем хранилась ваша коллекция. В соответствии с этим ваше время добавления, поиска, удаления и сохранения соответствия вашей коллекции отличается. Поэтому, когда вы выбираете коллекцию типов, вы должны помнить, какая операция будет наиболее частой, и выбирать лучшее решение для вашего случая.

Answer 3

Вам не нужно явно просматривать связанный список, поскольку LinkedList предлагает indexOf(Object) и get(int). Они по-прежнему будут проходить по списку, но сделают это неявно.

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

Answer 4

Списки не относятся к «физическим местоположениям» (что бы вы ни имели в виду), списки представляют собой определенную структуру данных, которая может увеличиваться и уменьшаться и обеспечивать приличную сложность для различных операций.

Answer 5

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

Answer 6

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

И да, если вы работаете с отсортированными данными, вам обычно все равно, в каких элементах порядка хранятся.