21. Как устроен LinkedList, сложность основных операций.

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

Вся работа с LinkedList сводится к изменению ссылок.

Однако, у LinkedList есть отдельные методы для работы с началом и концом списка, которых нет в ArrayList: addFirst(), addLast(): методы для добавления элемента в начало/конец списка Вставка и удаление в середину LinkedList устроены гораздо проще, чем в ArrayList. Мы просто

переопределяем ссылки соседних элементов, а ненужный элемент “выпадает” из цепочки ссылок.

Особенности:

• Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1) [константное время - поскольку выполняется единственная команда для его обнаружения];
• На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n) [линейное время - Например, процедура, суммирующая все элементы списка, требует время, пропорциональное длине списка]. Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1);
• Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки;
• Не синхронизирован.

LinkedList содержит все те методы, которые определены в интерфейсах List, Queue, Deque.

Некоторые из них:

• addFirst() / offerFirst(): добавляет элемент в начало списка
• addLast() / offerLast(): добавляет элемент в конец списка
• removeFirst() / pollFirst(): удаляет первый элемент из начала списка
• removeLast() / pollLast(): удаляет последний элемент из конца списка
• getFirst() / peekFirst(): получает первый элемент
• getLast() / peekLast(): получает последний элемент

Предыдущий вопрос: 20. Как устроен ArrayList, сложность основных операций.

Следующий вопрос: 22. Почему LinkedList реализует и List, и Deque?

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку:напишите мне