Шпаргалка по структурам данных в Java

[panzerfaust]

Дерево, TreeMap, TreeSet

Неа. Типичное заблуждение. Поведение объекта характеризуется его интерфейсом. TreeMap и TreeSet - это прежде всего Map и Set. Они не реализуют какие-то специфичные древесные интерфейсы. Соответственно, вы не можете работать с ними как с деревьями и выполнять например поиски в глубину и ширину. В плане ООП мы не можем сказать TreeSet is a Tree. Зато можем сказать TreeSet has a Tree - но это совсем другая история.

[dcct0r]

Спасибо за фидбэк, учту)

[aleksandy]

При желании можно написать универсальную реализацию ArrayList, сделать его массивом Object

Интересно, зачем так делать, если всё уже сделано.

Если не указать в конструктор начальную емкость, то будет создан пустой список с емкостью в 10 элементов

Если говорить про ArrayList, то это не так, как минимум с 1.8+. Если не указать размерность, то никаких дополнительных массивов не будет создаваться до первого добавления элемента в список.

Стек

Цитата прям из документации.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Связный список

Самого главного про этот список и нет.

Does anyone actually use LinkedList? I wrote it, and I never use it.
Joshua Bloch

Про TreeXXX уже всё сказали.

[dcct0r]

А что бы вы еще добавили про связный список?

[aleksandy]

Что нет никакого практического смысла его использовать.

Не саму структуру, но её конкретную реализацию java.util.LinkedList.

[Andrey_Solomatin]

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

Я неплохо прокачался в структурах данных реализуя их или используя для получения лучшего (алгоритмического или по памяти) результата решая задачки на litcode.

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

[dcct0r]

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

[sshikov]

Java есть следующие структуры данных
Я не очень понимаю смысл таких собеседований и таких вопросов.

Во-первых, это далеко не все. А как же ConcurentMap и иже с ним?

А во-вторых, много-много лет существует такая штука, как Google Guava (также Google Collections), где есть еще с десяток наверное структур данных. Ну просто чтоб далеко не ходить — MultiMap, где по одному ключу лежит N значений. Или реверсивный мап, который можно повернуть в сторону value->key. И еще — куча других библиотек, реализующих еще десятки других структур.

Не говоря уже о том, что каждый, кто немного владеет языком, может создать свою структуру данных достаточно несложно.

[dcct0r]

Cогласен, это далеко не все структуры данных и Google Guava может упростить жизнь, но ведь как правило же об этом не спрашивают на собеседованиях на позицию джуна или интерна

[sshikov]

как правило же об это не спрашивают на собеседованиях

Ну вот это и смешно :) Знаете, я вот лет пять пишу под Hadoop, так там конфликт версий Guava — это прям настолько типичные грабли, что чуть ли не каждый наступал. Т.е. гугль имел такое свойство, объявлять методы deprecated, и потом их выпиливать. И вот вы такой модный и молодежный, взяли свежую версию гуавы, собрали приложение под хадуп, и выяснили, что в самом хадупе тоже лежит Guava, более старой версии. И при замене ее на вашу более новую, что-то в самом хадупе перестает работать.

Я это к чему — что почти все разработчики приложений под хадуп так или иначе гуавой попользовались в свое время.

[Andrey_Solomatin]

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

Если есть понимание про базовые коллекций, то работа с гуавой не потребует догого изучения. Помотрел какие коллекции там есть, какие удобные методы у них есть и вперёд.

[sshikov]

Да я вообще про другое — что набор коллекций, который доступен для использования, не ограничен ни разу тем, что есть в составе JRE. Что есть куча других библиотек, в том числе очень широко используемых, которые могут быть полезны, и которые не нужно писать самому. Ну скажем, case insensitive Map-ы со строковыми ключами — насколько я помню, в JRE таких до сих пор нет, между тем это частый случай применения. Поэтому формулировка проблемы вообще должна быть примерно такой: какие бывают структуры данных, и для чего именно они полезны. Так намного ближе к практике, как по мне.

[Andrey_Solomatin]

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

Я никода не использовал case insensitive Map. И в отрытом вопросе врядли бы упомянул её. С мультимапами сталкивался (HTTP get params), но как отдельный класс их тоже бы не выделил, это же мапа со значеним типа лист.

Array, HashMap, Tree стоят в основе большиства стракур данных, всё остальное специфика, отсутствие опыта в которой не сделает кандидата хуже.