Спасибо. Для меня было познавательно. На методе разворота листа - голову сломал со всеми теми ссылками. Отдельная благодарность за напоминание о множественном выделении, при помощи ALT
Большое спасибо автору за труд! Вопрос по домашнему заданию))) - правильно ли я понял, что для реализации метода «удаление» нужно будет добавить в класс ListItem новое поле ListItem previous? Я так и не понял как можно сделать удаление, если есть только ссылка на следующий элемент…
жаль на видео нет нумерации строк кода. Есть вопрос по коду. В методе addToEnd() есть проверка if (isEmpty) {tail = newItem;} и в else {tail = newItem;} получается, что при любом исходе переменная tail получит значение newItem; Я так понимаю, это присваивание можно вытащить за пределы проверки условия. Да?
Это как я понял «Linked List»? То есть каждая у каждой ноды есть ссылка на next и на prev .. P.S ещё не досмотрел видос но сразу в голову пришёл линкед лист. Когда учился java проходили это, прям как под капотом устроено. Я правильно понял?
Привет. Хотелось бы делать выпуски чаще, но пока что работа и дела отнимают почти все свободное время. По этому видео редко выходят. Но бросать не собираюсь, и тем для новых видео хватит на несколько лет вперед. Новое видео будет где-то в течение недели. Снято уже, но надо нормально смонтировать.
При последовательном доступе все элементы обходятся по порядку. Например при линейном поиске нужно идти по списку, пока не найдется искомый элемент. В этом случае односвязный список не влияет на производительность. А если у нас бинарный поиск, то нужно посмотреть к примеру 128-й элемент, потом 196-й, потом 160-й, потом 176-й, потом 168-й и т.д. И следующий переход заранее неизвестен, решение принимается по ходу работы алгоритма. Получается что для того, чтобы вернутся с 196 элемента на 160, надо снова делать проход от головы списка, и так каждый раз. Это куча лишней работы. Я говорю об этом и говорю. Если нужен последовательный доступ - все хорошо, если произвольный - будут накладные расходы.
@@arhitutorials при линейном поиске это уже O(n) а при бинарном поиске? у тебя массив должен быть отсортирован в первую очередь. дальше там всегда участвует "Минимальный" элемент, "Максимальный" и "Средний". если ты будешь искать число, то ты средний уже уже знаешь, и оно либо больше, либо меньше, либо равно искомому. дальше ты меняешь Максимальный, Минимальный и Средний. да, по факту это такой же перебор будет. НО. с каждым перебором будет данных в два раза меньше. потому, что Средний элемент, это априори средний элемент. Минимальный и Максимальный это у тебя будет голова и хвост. и получается, ты работаешь с одними и теми же данными. а коэффиценты при расчете сложности опускаются, потому не играет роли O(n), O(2n), O(3n) это всё будет считаться как O(n)
@@NummeSpnet Пусть нам, например, нужно посчитать сумму чисел в листе. Для этого нужно обойти все элементы. Будем обходить связный список в прямом порядке. Складываем первый элемент, потом за O(1) переходим на второй элемент, потом снова за O(1) переходим на 3-й элемент, и так далее... Доступ к каждому последующему элементу происходит за O(1) - просто переход по ссылке на следующий элемент листа за константное время. Это есть последовательный доступ. Произвольный доступ в связном листе производится за O(n). Перебор всех элементов в обратном порядке в односвязном списке - это вообще O(n^2)
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)
@@NummeSpnet Суммирование всех элементов это O(n) да, а доступ к каждому *конкретному отдельному элементу* списка при проходе от головы к хвосту - это O(1). Как бы мы могли пройти по списку за O(n), если доступ к каждому элементу был бы O(n)? Тогда бы полный проход был бы за O(n^2), а не за O(n), логично? А вот если к элементам обращаться в произвольном порядке, то это будет O(n) для *каждого* элемента. Вы же не будете отрицать, что полный проход по односвязному списку в прямом направлении это O(n), а в обратном O(n^2)? Вот по той же самой причине последовательный и произвольный доступ имеют разную сложность.
Спасибо. Для меня было познавательно.
На методе разворота листа - голову сломал со всеми теми ссылками.
Отдельная благодарность за напоминание о множественном выделении, при помощи ALT
Сергей, спасибо за видео! Сразу стало все понятно)
Сергей, огромное спасибо за понятный язык изложения материала! Прям спасение.
спасибо бро
Большое спасибо
Было бы интересно так же послушать про "расстояние Левенштейна". Надеюсь когда-нибудь снимешь ролик про этот алгоритм.
Классно объяснено. А вопрос почему-то действительно часто задают.
Огромное спасибо вам за такие видеоуроки. Крайне познавательно.
Спасибо за урок!
Большое спасибо автору за труд! Вопрос по домашнему заданию))) - правильно ли я понял, что для реализации метода «удаление» нужно будет добавить в класс ListItem новое поле ListItem previous? Я так и не понял как можно сделать удаление, если есть только ссылка на следующий элемент…
Спасибо, друг!
Спасибо 👍🏻👍🏻
Спасибо!!!
Спасибо за видео! А плей лист с сортировками будет ещё пополняться? Можно к примеру сделать видео про shell сортировку. Прикольная и не сложная)
Понять за 5 минут говоришь?)) 3 дня уже подряд с утра до ночи сижу над этим)
жаль на видео нет нумерации строк кода. Есть вопрос по коду. В методе addToEnd() есть проверка if (isEmpty) {tail = newItem;} и в else {tail = newItem;} получается, что при любом исходе переменная tail получит значение newItem; Я так понимаю, это присваивание можно вытащить за пределы проверки условия. Да?
отличное видео, но я тоже не могу понять процесс реверса списка
Это как я понял «Linked List»? То есть каждая у каждой ноды есть ссылка на next и на prev .. P.S ещё не досмотрел видос но сразу в голову пришёл линкед лист. Когда учился java проходили это, прям как под капотом устроено. Я правильно понял?
Вы описали двух связный список (ссылка на Некст и на предыдущий) а односвязный это только одна ссылка на некст, как было показано в видео.
Макс спасибо , понял )
ну вот, ответили бы так на собес, и вас бы отсеивали
@@programer8 почему ?
@@programer8 не в тему чет.
сама суть начинается здесь: 15:33
А когда будут следующие уроки?
Привет. Хотелось бы делать выпуски чаще, но пока что работа и дела отнимают почти все свободное время. По этому видео редко выходят. Но бросать не собираюсь, и тем для новых видео хватит на несколько лет вперед. Новое видео будет где-то в течение недели. Снято уже, но надо нормально смонтировать.
А разве метод hasNext() не должен return current.next != null?
нет, так как мы обновляем данную ссылку в методе next.Кроме того, мы проверяем текущую позицию на null чтобы избавится от доп if-блоков
А название программы как?
Ааа, сложно! Не, логика понятно, но я сам написать код не могу.
почему последовательный доступ и произвольный разный? ведь и там и там придется перебирать все элементы, чтобы добраться до нужного элемента.
При последовательном доступе все элементы обходятся по порядку. Например при линейном поиске нужно идти по списку, пока не найдется искомый элемент. В этом случае односвязный список не влияет на производительность.
А если у нас бинарный поиск, то нужно посмотреть к примеру 128-й элемент, потом 196-й, потом 160-й, потом 176-й, потом 168-й и т.д. И следующий переход заранее неизвестен, решение принимается по ходу работы алгоритма. Получается что для того, чтобы вернутся с 196 элемента на 160, надо снова делать проход от головы списка, и так каждый раз. Это куча лишней работы. Я говорю об этом и говорю. Если нужен последовательный доступ - все хорошо, если произвольный - будут накладные расходы.
@@arhitutorials при линейном поиске это уже O(n)
а при бинарном поиске? у тебя массив должен быть отсортирован в первую очередь. дальше там всегда участвует "Минимальный" элемент, "Максимальный" и "Средний".
если ты будешь искать число, то ты средний уже уже знаешь, и оно либо больше, либо меньше, либо равно искомому. дальше ты меняешь Максимальный, Минимальный и Средний. да, по факту это такой же перебор будет. НО. с каждым перебором будет данных в два раза меньше. потому, что Средний элемент, это априори средний элемент. Минимальный и Максимальный это у тебя будет голова и хвост.
и получается, ты работаешь с одними и теми же данными. а коэффиценты при расчете сложности опускаются, потому не играет роли O(n), O(2n), O(3n) это всё будет считаться как O(n)
@@NummeSpnet Пусть нам, например, нужно посчитать сумму чисел в листе. Для этого нужно обойти все элементы. Будем обходить связный список в прямом порядке. Складываем первый элемент, потом за O(1) переходим на второй элемент, потом снова за O(1) переходим на 3-й элемент, и так далее... Доступ к каждому последующему элементу происходит за O(1) - просто переход по ссылке на следующий элемент листа за константное время. Это есть последовательный доступ.
Произвольный доступ в связном листе производится за O(n). Перебор всех элементов в обратном порядке в односвязном списке - это вообще O(n^2)
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)
@@NummeSpnet Суммирование всех элементов это O(n) да, а доступ к каждому *конкретному отдельному элементу* списка при проходе от головы к хвосту - это O(1).
Как бы мы могли пройти по списку за O(n), если доступ к каждому элементу был бы O(n)? Тогда бы полный проход был бы за O(n^2), а не за O(n), логично?
А вот если к элементам обращаться в произвольном порядке, то это будет O(n) для *каждого* элемента.
Вы же не будете отрицать, что полный проход по односвязному списку в прямом направлении это O(n), а в обратном O(n^2)? Вот по той же самой причине последовательный и произвольный доступ имеют разную сложность.
ага
а если без tail?)