Лучше чем эти уроки, я не видел! Но неплохо бы было пояснить, как перебрать элементы до того элемента, после которого планируется вставка еще одного... while node?
Смотрю это видео и двухсвязный список потому что прохожу ООП и оооочень тяжко доходит, путаница не много получается. Думаю что возьму курс по структурам данных, но хотелось бы чтобы в видео было применение в коде потому что не очень понятно (точнее совсем не понятно) как этим пользоваться, я понимаю что курс для с++ и питонистов поэтому кода нет и это очень печально что нет примеров в коде
Уточните, пожалуйста, а почему добавление в конец это не O(n)? Мы же должны вначале последовательно дойти до текущего конечного элемента, чтобы поменять у него ссылку. Точно так же как проходим до предпоследнего когда удаляем с конца
мы когда добавляем, то на последний элемент есть указатель tail, поэтому новый элемент ptr просто цепляется к нему, то есть: tail.next = ptr ptr.prev = tail tail = ptr и все
@@selfedu_rus спасибо, вопрос возник в связи с тем, что в языке скала list это односвязный список, но при этом в документации написано что добавление в конец занимает O(n). Скорее всего, потому что tail там ссылается не на последний элемент, а на список всех кроме первого. docs.scala-lang.org/overviews/collections/performance-characteristics.html
Немного не понятно, как реализовать этот список с начального состояния. То есть сначала у нас нет объектов, и head, tail node равный None. Потом мы создаем первый объект, на который указывает все 3 переменные. Дальше мы создаем второй объект, на который теперь указывает tail и node, потом третий также, четвертый и т.д. Я правильно понял?
Почему говориться что в конец односвязного списка вставка О(1) ? Просто как я понял , чтобы присвоить предпоследний элемент в тейл, нам нужно будет этот предпоследний элемент найти, итерируя список с головы. так как привиос метки у нас нет.
@@selfedu_rus ну, допустим. У нас есть сингл лл. У него есть тейл. У тейла есть поле некст привиос нету как в длл. Чтобы удалить тейл нам сначала же надо найти превиос. Тоесть элемент который стоит перед тейлом который и будет после удаления новым тейлом. Чтобы его найти нам надо по некстам нодов про итерировать с головы. Я об этом. Как бы удаление будет (1) но под капотом удаления ещё и итерация, а это уже О(N)
Почему BigO вставки нового элемента в конец связного списка равна O(1)? Нам ведь нужно пробежаться по всем элементам уже входящим в этот список перепрыгивая с одного элемента на другой по ссылке и остановится, когда у последнего элемента не окажется ссылки, и только после этого, мы связываем наш новый элемент с последним т.е. производим операцию добавления в конец. Следовательно, если мы всё равно пробегаем по всем элементам перед вставкой нельзя считать что это O(1), это O(n). А в интернетах ваших тоже пишут O(1), объясните, почему я не прав?
Если бы мы всегда знали последний элемент списка (tail) то добавление к нему нового элемента было бы за время O(1), тут вопросов нет, всё понятно, но ведь что бы узнать этот последний элемент мы поэлементно обходим список до конца и нигде не храним адрес последнего элемента (tail) храним только начало списка (head)
Это уже двусвязный список будет. На самом деле не всегда нужны проходы в обратном порядке, например, при реализации стека. Поэтому и односвязные списки занимают свою нишу.
Ощущаю себя олигофреном... Вроде всё схематически понятно. Но как реализовать без понятия. Посмотрел реализацию односвязного списка и ничего не понял. Реально затуп. Сложно в голову укладывается... Уважуха и белая зависть тем кто всё улавливает на лету)
@@selfedu_rus А если указывать на элемент списка чем нибудь другим, например курсором на экране, то перебирать весь список не нужно, нужно только чтобы каждый элемент связного списка указывал на предыдущий элемент и последующий.
Очень интересная тема. Большое спасибо за объяснение!
Однозначно.
О, помню как я в курсе по ООП разбирался с односвязными и двусвязными списками. На всю жизнь запомнил))
Я сейчас разбираюсь. Уже голова кругом идет. Почти что-то доходит, но очень туго ))
такое не забудешь
Вы лучший
Спасибо огромное! Очень круто!!!
Огромное спасибо!
Лучше чем эти уроки, я не видел!
Но неплохо бы было пояснить, как перебрать элементы до того элемента, после которого планируется вставка еще одного...
while node?
Смотрю это видео и двухсвязный список потому что прохожу ООП и оооочень тяжко доходит, путаница не много получается. Думаю что возьму курс по структурам данных, но хотелось бы чтобы в видео было применение в коде потому что не очень понятно (точнее совсем не понятно) как этим пользоваться, я понимаю что курс для с++ и питонистов поэтому кода нет и это очень печально что нет примеров в коде
очень полезный материал! Почему так мало лайков? Я вот смотря на степике перехожу на ютуб и лайкаю.
Уточните, пожалуйста, а почему добавление в конец это не O(n)? Мы же должны вначале последовательно дойти до текущего конечного элемента, чтобы поменять у него ссылку. Точно так же как проходим до предпоследнего когда удаляем с конца
мы когда добавляем, то на последний элемент есть указатель tail, поэтому новый элемент ptr просто цепляется к нему, то есть:
tail.next = ptr
ptr.prev = tail
tail = ptr
и все
@@selfedu_rus спасибо, вопрос возник в связи с тем, что в языке скала list это односвязный список, но при этом в документации написано что добавление в конец занимает O(n). Скорее всего, потому что tail там ссылается не на последний элемент, а на список всех кроме первого. docs.scala-lang.org/overviews/collections/performance-characteristics.html
Удаление из конца тоже должно быть О(1) - у нас есть указатель на конец списка. Разве не так?
Вопрос решил, нужно из предпоследнего ссылку удалить
Немного не понятно, как реализовать этот список с начального состояния. То есть сначала у нас нет объектов, и head, tail node равный None. Потом мы создаем первый объект, на который указывает все 3 переменные. Дальше мы создаем второй объект, на который теперь указывает tail и node, потом третий также, четвертый и т.д. Я правильно понял?
да, верно
Почему говориться что в конец односвязного списка вставка О(1) ? Просто как я понял , чтобы присвоить предпоследний элемент в тейл, нам нужно будет этот предпоследний элемент найти, итерируя список с головы. так как привиос метки у нас нет.
У нас имеется указатель tail, который всегда ссылается на последний элемент. Он формируется при добавлении новых элементов (и их удалении).
@@selfedu_rus ну, допустим. У нас есть сингл лл. У него есть тейл. У тейла есть поле некст привиос нету как в длл. Чтобы удалить тейл нам сначала же надо найти превиос. Тоесть элемент который стоит перед тейлом который и будет после удаления новым тейлом. Чтобы его найти нам надо по некстам нодов про итерировать с головы. Я об этом. Как бы удаление будет (1) но под капотом удаления ещё и итерация, а это уже О(N)
@@salten13 здесь речь о добавлении, удаление да, O(N)
@@selfedu_rus Понял. В любом случае, спасибо за пояснения!
Вродебы понятно, но для чего это используется?)
В теории вск понятно, а вот как это в код перенести,вот в чем вопрос
Почему BigO вставки нового элемента в конец связного списка равна O(1)? Нам ведь нужно пробежаться по всем элементам уже входящим в этот список перепрыгивая с одного элемента на другой по ссылке и остановится, когда у последнего элемента не окажется ссылки, и только после этого, мы связываем наш новый элемент с последним т.е. производим операцию добавления в конец. Следовательно, если мы всё равно пробегаем по всем элементам перед вставкой нельзя считать что это O(1), это O(n). А в интернетах ваших тоже пишут O(1), объясните, почему я не прав?
Если бы мы всегда знали последний элемент списка (tail) то добавление к нему нового элемента было бы за время O(1), тут вопросов нет, всё понятно, но ведь что бы узнать этот последний элемент мы поэлементно обходим список до конца и нигде не храним адрес последнего элемента (tail) храним только начало списка (head)
А указатели должны быть в обе стороны списка у каждого объекта, тогда всё быстро, не надо с самого начала перебирать.
Это уже двусвязный список будет. На самом деле не всегда нужны проходы в обратном порядке, например, при реализации стека. Поэтому и односвязные списки занимают свою нишу.
@@selfedu_rus Есть ли готовый объект с двусторонним ходом? чтобы самому не городить.
@@mslq collections.deque
@@selfedu_rus Нашёл, спасибо.
06:53
а как на счёт добавить в каждый элемент ещё и ссылку на предыдущий? тогда доступ к произвольному элементу может быть осуществлен за O(n/2) 😁
это уже будет двухсвязный список (о нем далее), а O(n/2) = O(n) - см. занятие по О большому
Ощущаю себя олигофреном... Вроде всё схематически понятно. Но как реализовать без понятия. Посмотрел реализацию односвязного списка и ничего не понял. Реально затуп. Сложно в голову укладывается... Уважуха и белая зависть тем кто всё улавливает на лету)
таких нет, мне например раза с третьего или с пятого просмотра заходит, зависит от сложности. )
все, кроме команд iterator, может быть реализовано с временной сложностью O (1) :)
произвольный доступ к элементу, в общем случае, не может, требует O(n) времени, иначе бы от массивов просто отказались бы ))
@@selfedu_rus А если указывать на элемент списка чем нибудь другим, например курсором на экране, то перебирать весь список не нужно, нужно только чтобы каждый элемент связного списка указывал на предыдущий элемент и последующий.
О от единицы, что такое О? Что такое единица?
единица это количество элементов О(n). n - это количество элементов в списке.
А что такое О? Время почему О?
@@gpankov см. первые два занятия