Java. Обращение односвязного списка.

[@katorabian]

Спасибо. Для меня было познавательно. На методе разворота листа - голову сломал со всеми теми ссылками. Отдельная благодарность за напоминание о множественном выделении, при помощи ALT

[@МихаилБезуглов-ь4ы]

Сергей, спасибо за видео! Сразу стало все понятно)

[@Дмитрий-х2й5р]

Огромное спасибо вам за такие видеоуроки. Крайне познавательно.

[@ЕвгенийВовк-ы7ь]

Сергей, огромное спасибо за понятный язык изложения материала! Прям спасение.

[@larisavishnyakova5832]

Спасибо за урок!

[@erikjoomla9872]

Было бы интересно так же послушать про "расстояние Левенштейна". Надеюсь когда-нибудь снимешь ролик про этот алгоритм.

[@ВладиславПавленко-л5х]

Большое спасибо

[@Andrzej3935]

Спасибо, друг!

[@GenesizANT]

Большое спасибо автору за труд! Вопрос по домашнему заданию))) - правильно ли я понял, что для реализации метода «удаление» нужно будет добавить в класс ListItem новое поле ListItem previous? Я так и не понял как можно сделать удаление, если есть только ссылка на следующий элемент…

[@user-cx5ry5tt6s]

Спасибо 👍🏻👍🏻

[@sergeyshcherbakov3653]

Классно объяснено. А вопрос почему-то действительно часто задают.

[@svalyavasvalyava9867]

Спасибо!!!

[@samirbagamaev93]

спасибо бро

[@MrTheMaks]

Спасибо за видео! А плей лист с сортировками будет ещё пополняться? Можно к примеру сделать видео про shell сортировку. Прикольная и не сложная)

[@ViktorVdovichenko]

жаль на видео нет нумерации строк кода. Есть вопрос по коду. В методе addToEnd() есть проверка if (isEmpty) {tail = newItem;} и в else {tail = newItem;} получается, что при любом исходе переменная tail получит значение newItem; Я так понимаю, это присваивание можно вытащить за пределы проверки условия. Да?

[@YouMeNow88]

Понять за 5 минут говоришь?)) 3 дня уже подряд с утра до ночи сижу над этим)

[@user-cx5ry5tt6s]

Это как я понял «Linked List»? То есть каждая у каждой ноды есть ссылка на next и на prev .. P.S ещё не досмотрел видос но сразу в голову пришёл линкед лист. Когда учился java проходили это, прям как под капотом устроено. Я правильно понял?

[@MrTheMaks]

Вы описали двух связный список (ссылка на Некст и на предыдущий) а односвязный это только одна ссылка на некст, как было показано в видео.

[@user-cx5ry5tt6s]

Макс спасибо , понял )

[@programer8]

ну вот, ответили бы так на собес, и вас бы отсеивали

[@MrTheMaks]

@@programer8 почему ?

[@user-cx5ry5tt6s]

@@programer8 не в тему чет.

[@raznye_sovety]

сама суть начинается здесь: 15:33

[@maksigors]

отличное видео, но я тоже не могу понять процесс реверса списка

[@alexanderkolosov1371]

А разве метод hasNext() не должен return current.next != null?

[@duapps4090]

нет, так как мы обновляем данную ссылку в методе next.Кроме того, мы проверяем текущую позицию на null чтобы избавится от доп if-блоков

[@sfiirwuejnn]

А когда будут следующие уроки?

[@arhitutorials]

Привет. Хотелось бы делать выпуски чаще, но пока что работа и дела отнимают почти все свободное время. По этому видео редко выходят. Но бросать не собираюсь, и тем для новых видео хватит на несколько лет вперед. Новое видео будет где-то в течение недели. Снято уже, но надо нормально смонтировать.

[@NummeSpnet]

почему последовательный доступ и произвольный разный? ведь и там и там придется перебирать все элементы, чтобы добраться до нужного элемента.

[@arhitutorials]

При последовательном доступе все элементы обходятся по порядку. Например при линейном поиске нужно идти по списку, пока не найдется искомый элемент. В этом случае односвязный список не влияет на производительность. А если у нас бинарный поиск, то нужно посмотреть к примеру 128-й элемент, потом 196-й, потом 160-й, потом 176-й, потом 168-й и т.д. И следующий переход заранее неизвестен, решение принимается по ходу работы алгоритма. Получается что для того, чтобы вернутся с 196 элемента на 160, надо снова делать проход от головы списка, и так каждый раз. Это куча лишней работы. Я говорю об этом и говорю. Если нужен последовательный доступ - все хорошо, если произвольный - будут накладные расходы.

[@NummeSpnet]

​@@arhitutorials при линейном поиске это уже O(n) а при бинарном поиске? у тебя массив должен быть отсортирован в первую очередь. дальше там всегда участвует "Минимальный" элемент, "Максимальный" и "Средний". если ты будешь искать число, то ты средний уже уже знаешь, и оно либо больше, либо меньше, либо равно искомому. дальше ты меняешь Максимальный, Минимальный и Средний. да, по факту это такой же перебор будет. НО. с каждым перебором будет данных в два раза меньше. потому, что Средний элемент, это априори средний элемент. Минимальный и Максимальный это у тебя будет голова и хвост. и получается, ты работаешь с одними и теми же данными. а коэффиценты при расчете сложности опускаются, потому не играет роли O(n), O(2n), O(3n) это всё будет считаться как O(n)

[@arhitutorials]

@@NummeSpnet Пусть нам, например, нужно посчитать сумму чисел в листе. Для этого нужно обойти все элементы. Будем обходить связный список в прямом порядке. Складываем первый элемент, потом за O(1) переходим на второй элемент, потом снова за O(1) переходим на 3-й элемент, и так далее... Доступ к каждому последующему элементу происходит за O(1) - просто переход по ссылке на следующий элемент листа за константное время. Это есть последовательный доступ. Произвольный доступ в связном листе производится за O(n). Перебор всех элементов в обратном порядке в односвязном списке - это вообще O(n^2)

[@NummeSpnet]

Sergey Arkhipov чтобы суммировать все элементы в списке это O(n) потому что тебе придётся обратиться к каждому элементу из списка. O(1) это когда по ключу запись в HashMap искать. когда по конкретному ключу он либо есть либо нету O(1) это запрос элемента в массиве. у тебя N элементов. поэтому, чтобы найти значение 9го элемента из 10, в самом сложном случае, тебе придётся перебирать все. это O(n). O(1) когда ты можешь получить значение по ключу/индексу . это Arraylist/HashMap/массив и ещё некоторые. у тебя в линейном списке в 100 элементов нет индекса конкретного элемента. значит значение этого элемента в худшем случае за одну операцию ты получить не можешь. значит никаким O(1) там и не пахнет. в худшем случае, для поиска нужного элемента (даже с помощью счетчика) тебе придётся переходить каждый элемент! и чтобы суммировать все элементы между собой ты обязан перебирать все ссылки между элементами! а это O(n) потому для для поиска 98 элемента из 100, тебе всегда придётся перебрать 97 элементов. и никак иначе! в плане суммы всех элементов, это равноценно поиску максимума в обычном массиве. а это всегда O(n)

[@arhitutorials]

​@@NummeSpnet Суммирование всех элементов это O(n) да, а доступ к каждому *конкретному отдельному элементу* списка при проходе от головы к хвосту - это O(1). Как бы мы могли пройти по списку за O(n), если доступ к каждому элементу был бы O(n)? Тогда бы полный проход был бы за O(n^2), а не за O(n), логично? А вот если к элементам обращаться в произвольном порядке, то это будет O(n) для *каждого* элемента. Вы же не будете отрицать, что полный проход по односвязному списку в прямом направлении это O(n), а в обратном O(n^2)? Вот по той же самой причине последовательный и произвольный доступ имеют разную сложность.

[@МерейАйтуреева-х3г]

А название программы как?

[@МеняЗовут-р1з]

ага а если без tail?)

[@LYT101]

Ааа, сложно! Не, логика понятно, но я сам написать код не могу.