Связанный список — одна из самых важных структур данных, которая очень популярна и широко используется в различных реальных проектах.

GPS-навигация в Google Maps, Очередь музыкального проигрывателя в Spotify, история посещенных веб-сайтов в Google Chrome ,почти вездев операционной системе Windows и контроле версий Git……

Мы можем перечислять это вечно.

Знаешь что?

Сегодня я расскажу вам,что такое связанный список,почему вам нужно знать об этой мощной структуре данных и как вы можете эффективно начать использовать ее в своих проектах, чтобы стать более опытным инженером-программистом. Давайте начнем!

Односвязный список

Начнем с разбора термина односвязный список. Это список узлов, где каждый узел помнит, кто следует за ним. Первый узел знает, какой узел идет за ним, третий узел знает, какой следующий узел после него и т. д.

Вы не можете просто сломать эту структуру, и поэтому простые операции с массивами, такие как вставка нового элемента, удаление элемента или поиск элемента, относительно разные и могут показаться вам немного сложными.

NEXT — это просто атрибут, указывающий на следующий узел массива.

HEAD — это текущий узел, на котором мы находимся в односвязном списке.

Временная сложность

Произвольный доступ в односвязном списке O(n) ,поскольку узлы недоступны по индексу, мы всегда начинаем с HEAD, а затем двигаемся вниз , что занимает O(n) времени.

Вставка и удаление в начале равно O(1), потому что изначально у нас есть доступ к первому узлу в односвязном списке.

Вставка и удаление в конце — это O(n), потому что, как я уже упоминал, изначально у нас есть доступ только к первому узлу, поэтому нам нужно перейти к концу односвязного списка, пока мы дойдем до последнего, который занимает O (n) времени.

Вставка или удаление в произвольном местоположении — это O(n), потому что мы не знаем, где находится узел в односвязном списке, и нам нужно выполнить обход, пока мы не найдем его, что занимает O(n) времени.

Важно упомянуть об узле связанного списка.

Когда вы возвращаете узел связанного списка, вы не возвращаете только один элемент, как в обычном массиве, вы также возвращаете все узлы, следующие за этим узлом, так как он имеет связь по следующему указателю.

Если вы хотите просто вернуть узел A, вам нужно разорвать связь с его следующим элементом,которым является узел B, установив A.nextNode на Нет.

Реализация односвязного списка в Python

Ниже приведена реализация узла односвязного списка, самого односвязного списка и его основных операций, таких как переворачивание списка, вставка нового элемент, удаление элемента и поиск элемента.

Двойной связанный список

Двухсвязный список имеет больше преимуществ по сравнению с односвязным списком, поскольку он оптимизирован для перемещения в обоих направлениях, вперед и назад, обеспечивая более высокую гибкость. Вы даже можете комбинировать его с другими структурами данных, чтобы улучшить временную сложность вашего кода.

Ключевое отличие от односвязного списка

  1. В отличие от односвязного списка, двухсвязный список также имеет указатель на предыдущий узел, что позволяет нам двигаться назад.

2. Имеет лучшую временную сложность.

Временная сложность

Сложность времени для двусвязного списка такая же, как и для односвязного списка, за исключением того, что для удаления узлов требуется O(1). Довольно внушительный.

Реализация двусвязного списка с использованием Python

Ниже приведен код Python для узла двухсвязного списка и двухсвязного списка.

Вахх, слишком много кода! Но как только вы поймете, как это работает, картинка станет ярче.

Настоятельно рекомендуем вам посетить каналы Back To Back SWE, NeetCode на Youtube и посмотреть несколько видеороликов о Linked List объяснение. Ребята сделали это до смешного просто.

Основная цель и почему важно освоить этот DSA.

Почти все низкоуровневые API в мире используют связанные списки, некоторые из них косвенно, но теперь это стало фундаментальной вещью, без которой не может жить ни одна программная система. Четкое понимание этой концепции поможет вам улучшить низкоуровневое проектирование и лучше понять, как работает большинство низкоуровневых механизмов.

Вот несколько задач для практики как для SLL, так и для DLL.

Для односвязного списка

  1. Обратно связанный список ~ [Легко]
  2. Объединить два отсортированных списка ~ [Просто]
  3. Удалить N-й узел из конца списка ~ [Просто]
  4. Удалить дубликаты из связанного списка~ [Просто]
  5. Цикл связанного списка ~ [Легко]
  6. Повернуть список ~ [Средний]
  7. Список разделов ~ [Средний]
  8. Поменять местами узлы парами ~ [Средний]

Для двухсвязного списка

  1. Кэш LRU ~ [Средний]
  2. Кэш LFU ~ [Сложно]

Заключение

Сегодня мы рассмотрели одну из самых важных структур данных, где она используется и почему вам, как инженеру-программисту, важно знать о ней.

Если вы открыли для себя что-то новое, обязательно нажмите на эту статью и поделитесь с другими.

На следующем занятии мы реализуем Очередь музыкального проигрывателя, используя Двойной связанный список и FastAPI Web Framework, чтобы попробовать этот DSA на реальном примере.

Свяжитесь со мной на LinkedIn.

Хорошего дня :)