Linked List. Data Structures | Implementation in JS
Привет, друзья. Вы давно просили рассказать не только про алгоритмы, но и про структуры данных. И сегодняшним выпуском мы начинаем серию видео, посвященных именно теме Структур данных (Data Structures). И начнем мы с такой структуры данных, как Связный список.
Связный список - одна из базовых структур данных, которая сейчас не часто встречается в повседневной жизни, особенно в работе фронтендера, но понимание которой позволит вам легче разобраться с другими более сложными структурами данных, такими как бинарные деревья, графы и пр. Поэтому начинаем мы именно с нее.
В связном списке все данные хранятся линейно - один элемент за другим. Каждый элемент списка (нода) содержит в себе поле value, в котором хранятся данные, и поле next, в котором хранится ссылка на следующий элемент.
В этом видео мы с вами разберемся, что же такое связный список, а также создадим свою реализацию его методов на javascript.
⏱ Таймкоды:
00:00 Интро
00:24 Что такое Singly Linked List
01:17 Что такое Doubly linked list
01:35 Зачем нужна эта структура данных
02:51 Структура связных списков
03:48 Пишем реализацию Linked List Node
05:09 Пишем реализацию класса Linked List
05:37 Создаем метод append
09:09 Создаем метод toArray
10:54 Создаем метод toString
12:05 Пишем тесты на append
15:39 Создаем метод prepend
17:20 Пишем тесты на prepend
18:36 Создаем метод find
20:17 Пишем тесты на find
21:16 Пишем тесты на delete
25:02 Создаем метод delete
29:54 Пишем тесты на insertAfter
32:26 Создаем метод insertAfter
34:10 Сложность получившихся методов
35:04 Заключение
Music: Appreciate Ptushkin for inspiration.
👍🤩 Будем благодарны за поддержку нашего канала на Патреоне: / frontendscience
---
Если видео было для вас полезным, ставьте лайк и поделитесь им с друзьями.
Подписывайтесь на наш канал: bit.ly/fs-ytb
---
Присоединяйтесь к нам в соцсетях:
FB: / frontendscience
Instagram Сергея Пузанкова: / puzankovcom
Заходите на наш сайт: frontend-science.com/
#datastructures #linkedlist
Сергей, большое спасибо. Желаю вам безопасности и свободы! Пусть все будет хорошо у тех, кто сейчас в беде.... тримайтесь!!!
Хочу отметить высокое качество продакшна самого. Видно большой труд: свет, звук, монтаж, качество картинки, и конечно же юмор) все это в купе делает процесс усвоения как бы менее напряжным и ненавязчивым.
Так и задумывалось! Приятно, что оценили ;) 🎈
да приятно смотреть твой контент, простая подача, приятно слушать и материал на уровне@@frontendscience
Позавчера начал читать "Грокаем алгоритмы", и наткнулся там на упоминание связанных списков. Решил, что на днях поищу что-нибудь о них в контексте использования в JS. А тут такое отличное видео 🙃 Большое спасибо!
Класс! )) Стараемся 🤗
@@frontendscience Что-то я не понимаю в работе классов... Могли бы в двух словах объяснить, как каждый последующий вызов append перемещает объект с переданным value из tale в head ? Конкретно, не понятен момент, когда после this.tale.next = newNode мы переписываем весь tale назначением this.tale = newNode; а новая нода как-то оказывается в next последнего объекта в head...
@@frontendscience Переписал на функции-конструкторы, но яснее не стало. Всё так же непонятно, как новые ноды попадают в head, ведь мы всё время работаем лишь с полем tail (не считая создания объекта linkedList) Что от меня ускользает, подскажите 😒
@@frontendscience const node = new LinkedNode(value); if (!this.head) { this.head = node; this.tail = node; return this; } else { let current = this.head while (current.next) { current = current.next } current.next = node; } this.tail = node; return this; Вот здесь мне понятно, как новая нода попадает в head. А какой механизм в реализации на видео? Очень хочется разобраться. Простите за назойливость, если что 😶
Разобрался 😆 Дело в присваивании по ссылке
Нравится манера подачи материала, приятно и интересно учиться с вами! Надо посмотреть что еще у вас на канале по теме есть)
Однозначно! На этом канале будет единственный адекватный курс по алгоритмам!
Сергей, большое спасибо за эти видосы. Благодаря вам я нехило так прокачался в алгоритмах и структурах данных.
Супер! Очень рады, что наши видео полезны!
Волшебство! Только вчера писал реализацию. Теперь закрепим успех просмотром ) Требую продолжения банкета с более сложными структурами!
Ну класс! ))) 🥳
Очень круто и понятно. Спасибо
Отличное видео, спасибо, очень полезно.
Я щиро дякую за це відео!) Я хоч і пишу не на JS, але пояснюєте ви дійсно зрозуміло) Я передивилась і перечитала вже мільярд інфи. І тільки зараз дійшло!)
Я очень рад что нашел ваш канал. Спасибо вам.
спасибо за материал! был бы очень благодарен за видео по остальным структурам данных 🤠
Спасибо! Отличное видео!
З'явилась таска, яку треба реалізувати через лінкед ліст, а я ніколи не юзав цей алгоритм... Дуже дякую за крутий контент!
Как же мне не хватало этого видео месяц назад)
Заказывайте новые :) Буду стараться успевать ;)
Очень хорошо объяснил, спасибо. Стало понятнее, но все равно очень сложно. Видео очень хорошее, особенно благодаря картинкам стало понятнее, что происходит при перемещении указателей. Огромное спасибо!
Вот только закончил "грокаем алгоритмы". Прям магия какая-то!) Ждём новые выпуски про структуры данных и алгоритмы) Лайк не глядя)
Будет обязательно!
Видео просто замечательные, смотрю тебя ещё с видео на канале Яндекса!)
видео пушка, спасибо)
Спасибо! Я только начал изучать, Связный список.
Вауу, прям мои мысли читаете ✨
🪄🧞
Месяц назад тыкалась в раздел задач по связанным спискам на leetcode, в итоге пока забросила. после этого видоса собираюсь вернуться и добить тему. спасибо за полезный контент!
Рад, что пригодилось :) мы тоже планируем задачки по связным спискам ;)
while (this.head && this.head.value === value) Так цикл выполниться лишь в том случая, если value будет равно первому next.value
Сергей, огромное спс! Когда следующие по уровню дин. массивы графа и прочие основы программирования, я лично очень жду!
Поставил в очередь)
👏
Здравствуйте, подскажите, пожалуйста, с чего начать изучение frontend? Хороши ли книги Джона Дакетта для освоения азов HTML, CSS, JS? К каким курсам в интернете стоит присмореться?
Вчера проходил собеседование, спросили о паттернах. Изучая базовый JS, я паттерны обошел стороной. Может сделаете туториал ?
Есть в планах
Это на Джуна?
привет! спасибо за видео) что то полезное взял для себя))) Слушай, возник вопрос в процессе практики, сверстал макет и запушил на github pages, и заметил что на мобильных устройствах у которых слабое железо есть подвисания при открытии аккордеон меню, реализация аккордеона на js - элементу добавляем max-height = scrollHeight. Когда тестировал на компьютере или на других телефонах все было отлично) Как быть со слабым железом на телефонах? Забивать на них?)) Просто даже обычный transform: translate() у бургер меню подвисает) Проблема не в коде, я еще заходил на различные сайты с того телефона с которого лагало и там тоже были проблемы, что посоветуешь предпринять для анимаций на сайте для слабых устройств??
Для слабых устройств нужно минимизировать количество анимаций. Но для этого понадобится детект устройства/браузера. Чтобы скармливать разные css’ки. Что же касается scrollHeight, я так понимаю ты апдейтишь высоту при каждом скролл ивенте. Если это так - то лагать будет сильно. В этом случае обычно используется throttle (у нас на канале есть видео про него), но тогда оно будет работать скачкообразно но не будет подвисать само устройство и тут уже надо добавлять css transform. В общем сложно сказать не понимая реализации. Но надеюсь основные идеи понятны.
@@frontendscience , нет, не при скролле, а при нажатии на само аккордеон меню )) Изначально оно в закрытом состоянии, у них разный контент и я использую в качестве высоты при открытии scrollHeight. Но мне все понятно, спасибо огромное! Буду пробовать))
Огромное спасибо за ваш канал! 🫶 У меня вопрос по поводу метода delete: // ... проверка головы списка ... let currentNode = this.head.next // присваиваем след. после head элемент, т.к. head уже поставлен на первый не удаленный элемент if (currentNode !== null) { while(currentNode.next) { if (currentNode.next.value === value) { //
сори, вы там потом исправляете это! Вопрос снят)
А зачем в 21 строке проверяем !this.tail, если и так понятно что если нету head, то это новый пустой список? И зачем в конструкторе ноды this.next = next, если мы при создании новой ноды еще не создали следующую ноду и можно просто null туда записать?
Отличное видео! Но вот вопрос - пытался кто-то это всё повторить? И никто не получил ошибку в консоли - ReferenceError: describe is not defined?
Установил jest и всё заработало
В insertAfter аргументу prevNode наверное надо дать значение null по умолчанию.
Это обязательный аргумент. Поэтому ему ничего и не назначаем по умолчанию. Мы же не задаем value - по умолчанию. Почему тогда для prevNode надо делать дефолт?
Если разговор пошёл о связанном списке, то не плохо бы рассмотреть и разворот связанного списка, задачка с собеседований.
Уже готовится такое видео!
а в Javascript разве нет чего-то вроде Collection Framework как в Java ?
Нет
Не надо так в массив значения пушить. Стоит сразу писать какой размер у массива будет. Динамическое измените размера массива весьма затратное в плане производительности, что будет особенно видно на большом объеме данных.
Нихрена не понятно, но очень интересно)
Спасибо. Если можно, без музыки пожалуйста. Отвлекает. Мы же не на дискотеке)
12-14 минута что за структура describe(LinkedList , () => {}) ? функция? , мы ее ранее не объявляли, откуда оно взялось, браузер ругается : "describe is not defined" . Разобрался : автору нужно все таки было упомянуть про использование стороннего Фреймворка Jest , без него ошибки!
Помогите пожалуйста разобраться в логике Javascript (она ведь должна быть, правда же?) console.log(false==[]); // true console.log([]==true); // false Это логический контекст, пустой массив трактуется как 0 или false или null А теперь оператор if: if ([]) // тоже логический контекст, ожидаю false console.log('y') // но получаю true - output 'y' else console.log('n') Почему так?
есть разница между тем когда просто в if () записываем [] или используем оператор не строгого сравнения ==. при == происходит приведение к числу. и потом сравниваются числа.
@@frontendscience Большое спасибо за ответ. Тогда перефразирую свой вопрос: если пустой массив не является согласно документации falsy-значением, то почему console.log(Number([]) ); выдает 0? не логичнее ли было бы Nan, при том что Number([0]) это 0, Number([1]) это 1 и т.д. Я понимаю, что некоторые вещи просто исторически сложились, это тоже приемлемый ответ. Но для человека, пришедшего из типизированного языка это трудно понять - пустой массив не должен занимать память, это null. В javascript, чтобы не потерять тип array/object, надо где-то хранить служебные данные, поэтому [] не null. Насколько верно мое предположение?
А что за редактор использовался для js?
webstorm
@@frontendscience Уж очень на pycharm похож )
А куда сбрасывать задачи с собеседования ?
Просто в комментарии под видео. Ссылки ютуб не принимает, поэтому если что-то большое, то можно выложить на кодпен и прислать айди сюда
как не печально но я ни слова не понял (((
метод delete не очень понятно)
не крайний, а последний. Иначе linked list не получится, потому что с переднего края нельзя встать
У Сергея времени полно - он может позволить себе баловаться какими-то там бессвязными списками! :))) Мы как люди очень занятые пользуемся только массивами! Они и работают быстрее, и, вообще, круче! Хотел скинуть решение суммы трех, но Ютуб опять все затирает, собака...
А кто сказал что массивы работают быстрее? Смотря для каких целей. С помощью списков можно очень быстро удалять или вставлять элемент, нужно всего лишь изменить две ссылки. Если удалять элемент у массива, в худшем случае, если элемент стоит на первом месте, то придется весь массив смещать на одну позицию вперед. У массива плюсом является то, что к элементам можно произвольно обращаться, у списков такого нет, придется итерироваться до тех пор пока не дойдешь до нужного элемента.
@@hyphast171 Да, все верно сказано. Кстати, чтобы удалить элемент из массива необязательно полностью сдвигать. Можно удалить через delete, тогда там останется empty.
@@hyphast171 в случае с одномсвязным списком (как в видео) удаление последнего элемента все еще будет O(n)
Як шкада, што пан Сяргей спыніў выпуск ролікаў (((
35 минут говорить про то, чем ни кто не пользуется... ну такое...
«Вы кажетесь профессионалом!» (с) Ну такое….
Я не понимаю как this.tail.next = newNode изменяет this.head.next ???
Щас тоже с этим затупил. Не разобрался почему так происходило?
@@Alex-cy1is Если разберёшься маякни
@@Alex-cy1is this.tail и this.head ссылаются на один и тот же объект node! Поэтому изменения в этом объекте будут видный и в head, и в tail!