Не тратьте время зря. Делайте правильные вещи в нужный момент.
Я всегда говорю это другим. Так что не теряйте времени зря, просто переходите к основной теме.
Что такое связанный список?
Проще говоря, связанный список — это линейная структура данных, которая содержит несколько узлов (контейнеров), и каждый узел содержит данные и указатель (указатели) на следующий или предыдущий узел.
Хорошо, давайте поиграем в коробочки. В каждой коробке несколько долларов. Первый содержит 5 долларов, а другие также содержат деньги в порядке возрастания. Я даю вам первую коробку с 5 долларами и случайным образом прячу другие коробки в спальне и на кухне. Если вы можете найти другие коробки по очереди, вы можете выиграть общую сумму денег во всех коробках. Но условие в том, что вы не можете открыть и увидеть деньги, пока не найдете последнюю коробку.
К счастью, сегодня твой день рождения, поэтому я также хочу, чтобы ты выиграл деньги. Вот почему я кладу на каждую коробку подсказку о том, где вы можете найти следующую коробку. Вы берете коробку и обнаруживаете, что в ней есть два отделения с подсказкой и призом. Вы открываете отделение для подсказок и находите записку. В нем есть буква «К». Вы умны, поэтому можете легко догадаться, что следующая коробка находится на кухне. Затем вы найдете вторую коробку. Также есть записка и она содержит букву «Б». Вы также найдете эту коробку с запиской. Но эта нота содержит ноль «0». Ты супер умный, поэтому ты можешь сказать мне, что это последняя коробка, и ты выиграешь все деньги.
На самом деле так работает связанный список. Связный список представляет собой контейнер из двух элементов. Один — это данные, такие как деньги внутри коробки, а другой — указатель на следующий контейнер, например ключ к следующему ящику. Вам всегда будет предоставлен первый контейнер списка, который является головным. И вы можете легко перейти к последнему контейнеру. Как вы можете догадаться, что это последний контейнер. Потому что он имеет указатель на None как ничто. И это односвязный список. В двусвязном списке все контейнеры содержат два указателя. Один указатель указывает на следующий контейнер, а другой указатель указывает на предыдущий контейнер. В циклическом связанном списке нет указателя None. Последний указатель снова указывает на первый контейнер.
Таким образом, в контейнере связанного списка (или мы можем назвать его node) необходимы две вещи. данные и указатель на следующий узел (контейнер).
Пришло время внедрить нашу игру «Ящики» в связанный список. Создайте файл с именем linked_list_box_example.py и напишите приведенный ниже код.
Итак, это наш класс узла (создатель контейнера/коробки). Мы будем создавать экземпляры узлов по мере необходимости. Давайте создадим три экземпляра узла. Обновите файл linked_list_box_example.py, как указано ниже.
Давайте рассмотрим некоторые основные атрибуты и функциональные возможности односвязного списка.
Основные атрибуты связанного списка
Узлы:
- данные, значение — (удерживать данные/значение)
- next, next_node — (указатель на следующий узел)
Связанный список:
- head — (головной/первый узел. Он нам нужен всегда)
- хвост — (последний узел списка. иногда он нам не нужен)
Основные функции связанного списка:
- insert, push, append (insert — данные в определенную точку связанного списка, push — вставка данных в начало, append — вставка данных в хвост)
- remove, pop, pop_back (remove — удалить узел и вернуть данные в определенной точке связанного списка, pop — удалить узел и вернуть данные из головы, pop_back — удалить узел и вернуть данные из хвоста)
- peek/top, peek_back/back, get/get_at (peek/top — возвращаются только данные начала, peek_back/back — возвращаются только данные хвоста, get/get_at — возвращаются данные из определенной точки связанного списка)
- найти/поиск (возвратить первый соответствующий номер индекса или true, если значение присутствует в списке)
- display (отображать все данные списков)
- size/len (возвращает размер связанного списка)
Использование связанного списка
В веб-разработке основное использование связанного списка — это кеширование ссылок поисковым роботом и следующей ссылки от этой ссылки. Больше вы можете узнать здесь https://www.geeksforgeeks.org/applications-of-linked-list-data-structure/
Чтобы визуализировать и четко понять связанный список, вы можете посетить https://visualgo.net/en/list.
Реализация односвязного списка
Односвязный список — это вид связанного списка, в котором каждый узел имеет одно значение и один указатель на следующий узел. Над изображением 1.1 и примером кода находится односвязный список.
Пришло время реализовать односвязный список. Перейдите в каталог кода и создайте файл с именем singly_linked_list.py. Напишите код ниже. Помните, что ваша работа состоит в том, чтобы понять каждый метод, проверить, как он работает. Затем улучшите его для угловых случаев. Вы можете написать тестовые примеры для своего связанного списка.
Реализация двусвязного списка
В двусвязном списке все узлы имеют два указателя. Один будет указывать на предыдущий узел, другой будет указывать на следующий узел.
Теперь ваша задача — реализовать двусвязный список.
Реализация циклического связанного списка
В круговом связанном списке последний узел будет указывать на первый узел.
Ваша задача — реализовать круговой связанный список
Круто, ты сделал это. Вы реализовали три вида связанных списков и поняли основы. Теперь вы хотите узнать о сложности времени и пространства. Я надеюсь, что вы изучили алгоритмы анализа до изучения структур данных и алгоритмов. Чтобы узнать о временных и пространственных сложностях некоторых распространенных структур данных и алгоритмов, я бы посоветовал вам эту ссылку;
Хватит учиться на сегодня.
Любовь к кодированию…
