Ответ
Двусвязный список. Каждый элемент (узел) хранит:
E item— данные.Node<E> next— ссылку на следующий узел.Node<E> prev— ссылку на предыдущий узел.
Внутренний класс узла:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}| Сложность основных операций: | Операция | Сложность | Примечание |
|---|---|---|---|
| Вставка/удаление в начале/конце | O(1) | Известны ссылки на head и tail. | |
| Вставка/удаление по индексу | O(n) | Требуется линейный обход до позиции. | |
| Получение элемента по индексу | O(n) | Линейный поиск. | |
| Поиск по значению | O(n) | Линейный поиск. |
Память: Занимает больше, чем ArrayList, из-за хранения двух дополнительных ссылок на каждый элемент.
Ответ 18+ 🔞
Давай разберём эту штуку, как будто я тебе на кухне объясняю, водку при этом не предлагаю, но атмосфера та ещё.
Представь себе цепочку из людей в очереди за колбасой, только каждый — не просто мудак, а мудак с двумя телефонами. В одном у него номер того, кто перед ним, в другом — кто сзади. Это и есть двусвязный список, ёпта. Каждый узел — это такой вот хитрожопый чувак.
Вот смотри, как он внутри устроен, этот узел-мудак:
private static class Node<E> {
E item; // Сама колбаса, которую он держит. Данные, короче.
Node<E> next; // Телефон, по которому звонит тому, кто сзади него. Ссылка на следующий узел.
Node<E> prev; // Телефон, по которому звонит тому, кто перед ним. Ссылка на предыдущий узел.
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}Он, сука, такой: «Я стою между Васей и Петей. Вася — это prev, Петя — next. А в руках у меня — item, моя драгоценная палка колбасы».
А теперь про скорость, тут весело. Сложность операций, блядь:
- Впихнуть или выкинуть кого-то в начало/конец очереди (вставка/удаление в начале/конце): O(1). Вообще быстро, потому что мы знаем, кто там первый и последний (
headиtail). Подошёл, взял за шкирку, переставил — готово. Никого по всей очереди бегать не надо. - Впихнуть или выкинуть кого-то по номеру в очереди (по индексу): O(n). Вот тут пиздец начинается. Ты говоришь: «Мне нужен 102-й человек». И пошёл ты, блядь, с начала считать: раз, два, три... девяносто девять, сто, сто один, сто два — вот он, нашёлся! Линейный обход, хуле.
- Посмотреть, что за колбаса у 102-го (получение по индексу): O(n). Та же хуйня. Беги и считай снова.
- Найти человека по виду колбасы (поиск по значению): O(n). Вообще ахтунг. Ты идёшь и каждому в руки смотришь: «У тебя «Докторская»? Нет? А у тебя?» Пока не найдёшь или всю очередь не пройдёшь.
Память: А жрёт эта конструкция, ядрёна вошь, больше, чем обычный динамический массив (ArrayList). Потому что каждый наш мудак-узел тащит на себе не только колбасу (item), но и два целых телефона (next и prev) — две дополнительные ссылки. За удобство двустороннего движения (вперёд-назад) платим местом.
Короче, если тебе надо часто тыкать в начало и конец — это твой выбор, огонь. Если же ты планируешь постоянно прыгать по индексам и смотреть, что там внутри — готовься к долгой пробежке, это не твой инструмент, дружок. Выбирай с умом, а то будешь как Герасим с Муму — вроде сила есть, а нихуя не можешь объяснить.