Простой список:
Сохраняет каждый элемент последовательно, поэтому случайный поиск чрезвычайно быстр (т.е. я могу сразу сказать: «Я хочу 657415671567-й элемент и сразу перейти к нему, потому что мы знаем, что его адрес памяти будет ровно на 657415671567 больше, чем первый элемент). Это приводит к небольшим или нулевым перерасходам памяти при хранении, однако у него нет способа автоматического изменения размера - вы должны создать новый массив, скопировать все значения, а затем удалить старый. Простые списки полезны, когда вам нужен поиск данные из любого места в списке, и вы знаете, что ваш список не будет длиннее определенного размера.
Связанный список:
Каждый элемент имеет ссылку на следующий элемент. Это означает, что есть некоторые накладные расходы (для сохранения ссылки на следующий элемент). Кроме того, поскольку они не сохраняются последовательно, вы не можете сразу перейти к 657415671567-му элементу - вы должны начать с заголовка (1-й элемент), а затем получить его ссылку, чтобы перейти ко 2-му, а затем получить его ссылку, чтобы добраться до третьего, ... и затем получить его ссылку, чтобы добраться до 657415671566-го, а затем получить его ссылку, чтобы добраться до 657415671567-го. Таким образом, это очень неэффективно для случайного поиска. Тем не менее, это позволяет изменить длину списка. Если ваша задача состоит в том, чтобы последовательно проходить каждый элемент, то это примерно то же значение, что и обычный список. Если вам нужно изменить длину списка, это может быть лучше, чем простой список. Если вы знаете 566-й элемент и ищете 567-й, то все, что вам нужно сделать, это перейти по ссылке на следующий. Однако, если вы знаете 567-й и ищете 566-й, единственный способ найти его - это начать поиск с 1-го элемента снова. Здесь пригодятся двойные списки ...
Двусвязный список:
Двойные связанные списки хранят ссылку на предыдущий элемент. Это означает, что вы можете просматривать список назад , а также вперед. Это может быть очень полезно в некоторых ситуациях (например, пример, приведенный в разделе «Связанный список»). Помимо этого, они имеют большинство тех же преимуществ и недостатков, что и связанный список.
Ответ из раздела комментариев:
Для использования в качестве очереди:
Вы должны принять во внимание все эти преимущества и недостатки: можете ли вы с уверенностью сказать, что ваша очередь будет иметь максимальный размер? Если ваша очередь может иметь длину от 1 до 10000000000 элементов, то простой список будет просто тратить память (а затем может даже не быть достаточно большим). В этом случае я бы пошел со связанным списком. Однако вместо того, чтобы хранить index на передней и задней панелях, вы должны хранить узел.
Резюме: связанный список состоит из «узлов», и каждый узел хранит элемент, а также ссылку на следующий узел
Таким образом, вы должны хранить ссылку на первый узел и последний узел. Таким образом, когда вы ставите в очередь, вы прикрепляете новый узел сзади (связывая старый задний с новым задним) и запоминаете этот новый задний узел. И, когда вы удаляете из очереди, вы удаляете передний узел и вспоминаете второй как новый "передний узел". Таким образом, вам не нужно беспокоиться о каких-либо промежуточных элементах. Таким образом, вы можете игнорировать длину очереди (хотя вы также можете сохранить ее, если действительно хотите)