Это статья об основах программирования на Go. На канале я рассказываю об опыте перехода в IT с нуля, структурирую информацию и делюсь мнением.
Хой, джедаи и амазонки!
Просматривал блог Николая Тузова по теме "Как попасть в IT - проблемы стажёров и как их решать":
Один из программистов сказал такую вещь: я с кандидатом начинаю собеседование так:
1. Можешь построить односвязный список? Если да, то,
2. Можешь обернуть его? Если да, то продолжаем общение.
Решил, что непременно нужно это дело изучить.
Также примерно в то же время, когда смотрел 3-ю лекцию Алгоритмов 6.0, мы писали свой стек на Go. Разберёмся и с этой структурой данных.
1. Стек
Начнём с того, что попроще. Стек.
Стек можно сравнить с книжной стопкой. Что с этой стопкой (стеком) можно сделать:
1. Положить книгу на верх стопки;
2. Посмотреть что лежит на верху стопки;
3. Забрать книгу с верха стопки.
Часто есть ещё возможность узнать размер стека - сколько в нём сейчас элементов.
А вот чего делать нельзя:
- Сунуть книгу в середину стопки;
- Забрать книгу из середины стопки.
Называется такой способ организации данных LIFO: last In - first Out. Последний пришёл - первый вышел.
В структурированном линейном списке, организованном по принципу LIFO, элементы могут добавляться и выбираться только с одного конца, называемого «вершиной списка».
В Go стек реализуется с помощью слайса:
Сам стек - это просто срез. Можно создать его в функции гонять между функциями pop и push. Либо как здесь - через структуру.
Функция push, т.е. добавить элемент в стек - просто расширяем срез через append, а функция pop - удаляем последний элемент среза. Всё просто.
Какая будет алгоритмическая сложность по времени работы со стеком?
Тут два момента - при просмотре значения верхнего элемента, получении информации о размере стека, удалении или добавлении элемента, время будет О(1). Однако, если срез достигнет своего максимального размера, потребуется выделение новой памяти и копирование элементов в новый базовый массив, что увеличивает время выполнения до O(n) в этот момент. Но из-за амортизированной сложности, в среднем за несколько операций это все равно будет O(1).
Работа со стеком выполняется за амортизированное время О(1) .
Где может понадобиться стек? Например, для определения корректности скобочной последовательности. Тема из Алгоритмов 6.0:
Причём, стек нужен для определения корректности скобочных последовательностей, состоящей из разных скобок; т.к. для определения корректности скобочных последовательностей из одного вида скобок, даже никакой стек не нужен.
Думаете, пример далёкий от практики? Вот пример, где может быть полезно посчитать скобочную последовательность:
Вот, что в это время говорит лектор:
Современные браузеры отчаялись дожидаться того светлого будущего, когда все пишут валидные теги в html и научились обрабатывать теги самостоятельно.
Возможно в другой публикации разберу эту и другие задачи на стек. Пока ограничимся его реализацией. Код можно посмотреть здесь.
2. Односвязный список
Односвязный список - это структура данных, состоящая из узлов, в каждом из которых есть поле или несколько полей с основными данными и поле с указателем на следующий элемент в списке.
Для срезов характерно быстрое чтение и вероятная медленная вставка; т.к. данные в массивах хранятся последовательно в памяти.
Для связанных списков характерно медленное чтение и быстрая вставка; т.к. данные в списках могут храниться как последовательно, так и хаотично размещёнными в памяти.
Иллюстрация сравнения времени работы с массивами и списками ниже:
В Go односвязный список реализуется через пользовательскую структуру данных, в которой есть поле (или поля) с полезной информацией, и поле с указателем на следующий элемент в списке. Если следующего элемента нет, то поле равно nil'у:
Также создаётся "голова" списка - элемент списка с индексом ноль, можно так сказать.
Соответственно, чтобы прочитать последний элемент списка, нужно прочитать все элементы списка. Тогда как в массиве можно сразу по индексу получить информацию, хранимую в массиве.
Есть два подхода к созданию односвязных списков:
1. Когда мы вставляем новый элемент в конец списка.
2. Когда мы вставляем новый элемент в начало списка.
В моём примере будет реализация для вставки в конец списка.
Операция вставки
Операция печати элементов списка
Операция поиска элемента списка по индексу
Обращаем список
Или можно использовать синтаксический сахар, используя три переменные в цикле, вместо четырёх:
Вызов всех этих функций и вывод в терминал может выглядеть так:
Так мы познакомились с тем, как создать в Golang односвязный список и развернуть его. Сюда ещё можно добавить операцию удаления и тесты - оставим это на домашнюю работу.
Код на Гитхабе >>> здесь <<<
Где могут применяться односвязные списки? Я попробовал поискать ответ на этот вопрос, но так и не нашёл - если знаете реальные примеры, напишите. Из того что нашёл, идея сводится к временному хранению данных при частой вставке элемента в список и редком чтении. Например, при получении данных от клиента, и их длительной обработкой перед помещением в БД.
3. Выводы
Познакомились со структурами данных, которых нет в стандартной библиотеке Go, но которые могут быть полезны при собеседованиях, или даже в реальной работе программистом.
Тут главное практика - если со стеком всё интуитивно понятно, один-два раза стоит написать, то со списком, думаю, нужно много раз его переписать, чтобы принцип усвоился. Особенно с оборачиванием списка могут быть сложности.
На этом всё, благодарю, что дочитали публикацию до конца. Успехов, и будем на связи.
Бро, ты уже здесь? 👉 Подпишись на канал для начинающих IT-специалистов «Войти в IT» в Telegram, будем изучать IT вместе 👨💻👩💻👨💻