Преимущества и недостатки связанного списка или реализации массива списка

Question

Каковы преимущества реализации списка Listed List в List над реализацией массива и наоборот?

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

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

Любые идеи по поводу чего-либо еще для преимущества-недостатка?

Answer 1

Для массива вы можете получить доступ к любому элементу, если у вас есть индекс (постоянная временная сложность O (1)). Но для списка вам нужно перебирать один за другим, чтобы получить доступ, хотя у вас есть индекс (временная сложность O (n))

Для получения списка вставка и удаление элемента занимает постоянное время (O (1)). Но для массива вставка и удаление занимают время O (n).

Для сортировки реализация списка лучше, чем реализация массива.