#8. Односвязный список. Структура и основные операции | Структуры данных

Что такое односвязный список. Структура односвязного списка. Основные операции: добавление и удаление элементов, произвольный доступ к элементам.

[Максим-тши]

О, помню как я в курсе по ООП разбирался с односвязными и двусвязными списками. На всю жизнь запомнил))

[siarheiulas]

Очень интересная тема. Большое спасибо за объяснение!

[eltimccc]

Лучше чем эти уроки, я не видел!
Но неплохо бы было пояснить, как перебрать элементы до того элемента, после которого планируется вставка еще одного...
while node?

[kish_mish_haha]

Смотрю это видео и двухсвязный список потому что прохожу ООП и оооочень тяжко доходит, путаница не много получается. Думаю что возьму курс по структурам данных, но хотелось бы чтобы в видео было применение в коде потому что не очень понятно (точнее совсем не понятно) как этим пользоваться, я понимаю что курс для с++ и питонистов поэтому кода нет и это очень печально что нет примеров в коде

[donfedor]

очень полезный материал! Почему так мало лайков? Я вот смотря на степике перехожу на ютуб и лайкаю.

[СергейФролов-ъя]

Уточните, пожалуйста, а почему добавление в конец это не O(n)? Мы же должны вначале последовательно дойти до текущего конечного элемента, чтобы поменять у него ссылку. Точно так же как проходим до предпоследнего когда удаляем с конца

[АндрейДеревяшко-зи]

Удаление из конца тоже должно быть О(1) - у нас есть указатель на конец списка. Разве не так?

[ВячеславОсипов-чь]

Вродебы понятно, но для чего это используется?)

[wizardx_X]

Немного не понятно, как реализовать этот список с начального состояния. То есть сначала у нас нет объектов, и head, tail node равный None. Потом мы создаем первый объект, на который указывает все 3 переменные. Дальше мы создаем второй объект, на который теперь указывает tail и node, потом третий также, четвертый и т.д. Я правильно понял?

[salten]

Почему говориться что в конец односвязного списка вставка О(1) ? Просто как я понял, чтобы присвоить предпоследний элемент в тейл, нам нужно будет этот предпоследний элемент найти, итерируя список с головы. так как привиос метки у нас нет.

[youtubeyoutube]

06:53
а как на счёт добавить в каждый элемент ещё и ссылку на предыдущий? тогда доступ к произвольному элементу может быть осуществлен за O(n/2) 😁

[КонстантинАлексеев-ыб]

В теории вск понятно, а вот как это в код перенести, вот в чем вопрос

[РоманМомотов-шй]

Почему BigO вставки нового элемента в конец связного списка равна O(1)? Нам ведь нужно пробежаться по всем элементам уже входящим в этот список перепрыгивая с одного элемента на другой по ссылке и остановится, когда у последнего элемента не окажется ссылки, и только после этого, мы связываем наш новый элемент с последним т.е. производим операцию добавления в конец. Следовательно, если мы всё равно пробегаем по всем элементам перед вставкой нельзя считать что это O(1), это O(n). А в интернетах ваших тоже пишут O(1), объясните, почему я не прав?

[mslq]

А указатели должны быть в обе стороны списка у каждого объекта, тогда всё быстро, не надо с самого начала перебирать.

[ДенисАнциборов-бт]

Ощущаю себя олигофреном... Вроде всё схематически понятно. Но как реализовать без понятия. Посмотрел реализацию односвязного списка и ничего не понял. Реально затуп. Сложно в голову укладывается... Уважуха и белая зависть тем кто всё улавливает на лету)

[gpankov]

О от единицы, что такое О? Что такое единица?

[buzzerbeatz]

все, кроме команд iterator, может быть реализовано с временной сложностью O (1) :)