Введение в связанные списки

Реализация на Python

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

Несколько недель назад я начал переключать свое внимание на лучшее изучение объектно-ориентированного программирования, как вы могли заметить из моих последних сообщений. Это открыло для меня много дверей, в том числе одну ведущую в мир структур данных, поскольку их реализация легче всего достигается с помощью ООП.

Структуры данных

Структуры данных в вычислениях относятся к конкретным способам организации данных для эффективного использования. Пользователи Python должны быть знакомы с некоторыми из этих простых структур данных, присущих языку:

• Списки

[1, 2, 3]

• Кортежи

(1, 2, 3)

• Наборы

{1, 2, 3}

• Словари

{'first': 1, 'second': 2, 'third': 3}

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

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

Связанные списки

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

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

1 -> 5 -> -2 -> None

У нас есть три элемента в связанном списке выше. Каждый элемент называется узлом. Каждый узел имеет два свойства: значение и ссылку на следующий узел в последовательности. Под «ссылкой» я подразумеваю стрелку, указывающую на следующее значение. Вы можете думать о приведенном выше связанном списке как о следующем, где каждое поле представляет собой узел.

+------+ +------+ +-------+ 
| 1 -> | | 5 -> | | -2 -> | None
+------+ +------+ +-------+ 

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

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

Первый узел связанного списка называется заголовком. При построении связанных списков мы всегда начинаем с головы. В приведенном выше примере наша голова - это узел со значением 1, указывающий на узел со значением 5.

И что? Давайте посмотрим, что мы можем делать со связанными списками.

Вставка

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

В начале:

0 -> 1 -> 5 -> -2 -> None

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

В середине после узла со значением 5:

1 -> 5 -> 0 -> -2 -> None

Это медленнее, потому что компьютер не знает, где узел со значением 5, пока мы не пройдемся по нему, чтобы найти его. Итак, смотрим на голову. Это значение 5? Нет, поэтому мы смотрим на следующий узел, значение которого удобно равно 5. Теперь мы просто вставляем новый узел и убеждаемся, что он продолжает цепочку ссылок.

В конце:

1 -> 5 -> -2 -> 0 -> None

Еще один простой случай, но занимает больше всего времени, потому что нам нужно перебрать весь список, чтобы найти последний узел, а затем добавить новый узел в конце. Опять же, мы следим за тем, чтобы это продолжало нашу цепочку ссылок.

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

Удаление

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

1 -> 5 -> -2 -> None

В начале:

5 -> -2 -> None

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

В середине (удалите узел со значением 5):

1 -> -2 -> None

Медленнее, чем удаление в начале, потому что нам нужно найти узел со значением 5, чтобы удалить его.

В конце:

1 -> 5 -> None

Самый медленный, потому что нам нужно найти последний узел, чтобы его удалить.

Реализация на Python

Теперь, когда у нас есть представление об основных строительных блоках односвязного списка, давайте посмотрим на базовую реализацию этого в Python.

Для этого нам нужны два класса: класс Node и класс LinkedList, который отслеживает нашу голову и имеет методы для вставки / удаления узлов.

Узел

Напомним, что узел отслеживает только две вещи: значение и ссылку на другой узел. Таким образом, наш метод __init__() позаботится об этих двух вещах за нас. Ссылку self.next присваиваем позже.

LinkedList

Абсолютно простейшая реализация этого класса просто отслеживает голову.

Затем мы можем составить и увидеть наш связанный список выше со следующими назначениями:

Результатом цикла while является

1
5
-2

Большой! Давайте посмотрим, как мы можем вставлять элементы.

Вставка: Начало

Помните, что есть три способа вставки. Начнем с начала связанного списка.

Обратите внимание на параметр self, потому что это фактически метод в LinkedList.

Мы следуем той же логике, что и в наглядном примере выше. Таким образом, если мы имеем

llist: 1 -> 5 -> -2

и мы бежим

llist.push(0)

мы получим структуру

0 -> 1 -> 5 -> -2 -> None

Вставка: Средний

В этом методе может быть меньше шагов, но у вас уже должен быть prev_node, чтобы вставить новый узел. В llist_02.py мы создали llist, second и third. Мы могли бы вставить узел со значением 0 в наш связанный список, вызвав

llist.insert_after(second, 0)

давая нам

llist: 1 -> 5 -> 0 -> -2 -> None

Вставка: Конец

Чтобы использовать это на практике, мы просто берем связанный список и добавляем его!

llist.append(0)

Дает

llist: 1 -> 5 -> -2 -> 0 -> None

Удаление

Это следует той же интуиции, что и описанная выше, и будет хорошим упражнением для всех, кто последует за вами, чтобы попробовать себя. Если нет, то на моем GitHub будет код с решениями и многим другим.

Последние мысли

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

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