Share This
Связаться со мной
Крути в низ
Categories
//Связный список на Python: что это такое и как его реализовать

Связный список на Python: что это такое и как его реализовать

28.02.2021Category : Python

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

Если вы представите себе фотографию людей, взявшихся за руки в хороводе, вы получите примерное представление о такой структуре, как связный список. Это некоторое количество отдельных узлов, связанных между собой ссылками, т. е. ссылками на другие узлы. Связные списки бывают двух видов: однонаправленные и двунаправленные (односвязные и двусвязные).

svjaznyj spisok na python chto eto takoe i kak ego realizovat 40a1d0b - Связный список на Python: что это такое и как его реализовать

Источник: Medium.com

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

Давайте попробуем реализовать связный список на Python. Возможно, вы бы начали с class Linked_list, а затем создали в нем узлы, но все можно сделать куда проще. Представьте цепочку из скрепок. Мы берем кучку скрепок и соединяем их, цепляя друг за дружку.

svjaznyj spisok na python chto eto takoe i kak ego realizovat 8f5f39b - Связный список на Python: что это такое и как его реализовать

Цепочку создают отдельные скрепки плюс тот факт, что они сцеплены между собой. Поэтому вместо создания класса Linked_list мы просто создадим класс Node и позволим отдельным узлам связываться друг с другом.

 class Node:

Далее, как обычно при создании класса на Python, мы создаем метод __init__. Этот метод инициализирует все поля, например, переменные в классе, при создании каждого нового объекта Node.

Мы будем принимать переменную data — это значение, которое мы хотим сохранять в узле. Также нам нужно определить ссылку, направленную вперед, она традиционно называется next. Сначала узел не связан ни с чем, поэтому мы устанавливаем next в None.

class Node:     def __init__(self, data):         self.data = data         self.next = None

Это почти все, что нам нужно. Можно оставить, как есть, но в книге «Cracking the Coding Interview» также реализуется метод appendToTail(), который создает новый узел и добавляет его в конец списка, проходя его, так что нам не приходится делать это вручную.

Начнем с определения этого метода в классе Node. Метод будет принимать значение, которое мы хотим поместить в новый узел, и ключевое слово self (это специфично для Python).

class Node:     def __init__(self, data):         self.data = data         self.next = None      def append(self, val):         pass

Первое, что мы делаем, это создаем новый узел с заданным значением. Назовем его end.

def append(self, val):     end = Node(val)

Затем мы создаем указатель (поинтер). Это может звучать слишком технически, но по сути мы создаем ссылку на головной элемент (head) нашего списка. Мы делаем так, потому что хотим проходить по списку, не переназначая в нем ничего. Итак, мы делаем ссылку на первый узел, self, и сохраняем его в переменной n.

def append(self, val):     end = Node(val)     n = self

Наконец, мы проходим список. Как мы это делаем? Нам нужно всего лишь перемещаться к следующему узлу, если он есть. А если следующего узла нет, мы поймем, что мы уже в конце списка. Для прохождения списка до предпоследнего узла мы используем простой цикл while.

def append(self, val):     end = Node(val)     n = self     while (n.next):         n = n.next

Наконец, мы указываем на последний узел, за которым нет следующего узла. Мы просто берем end — наш новый узел — и устанавливаем n.next = end.

def append(self, val):     end = Node(val)     n = self     while (n.next):         n = n.next     n.next = end

Вот и все! Вот как выглядит наш класс полностью:

list_node.py

class Node:     def __init__(self, data):         self.next = None         self.data = data      def append(self, val):         end = Node(val)         n = self         while (n.next):             n = n.next         n.next = end

Проверяем наш связный список

Давайте все это проверим. Начнем с создания нового объекта Node. Назовем его ll (две латинские буквы «l» в нижнем регистре как сокращение Linked List). Назначим ему значение 1.

 ll = Node(1)

Поскольку мы написали такой классный метод append(), мы можем вызывать его для добавления в наш список новых узлов.

 ll.append(2)  ll.append(3)

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

  [1] --> [2] --> [3]

Но нет способа вывести его именно в таком виде. Нам нужно пройти список, выводя каждое значение. Вы же помните, как проходить список? Мы только что это делали. Повторим:

  1. Создаем переменную, указывающую на head.
  2. Если есть следующий узел, перемещаемся к этому узлу.

И просто выводим data в каждом узле. Мы начинаем с шага № 1: создаем новую переменную и назначаем ее головным элементом списка.

 node = ll

Далее мы выводим первый узел. Почему мы не начали с цикла while? Цикл while проитерируется только дважды, потому что только у двух узлов есть next (у последнего узла его нет). В информатике это называется ошибкой на единицу (когда нужно сделать что-то Х раз плюс 1). Это можно представить в виде забора. Вы ставите столб, затем секцию забора, и чередуете пару столб + секция столько раз, сколько нужно по длине.

svjaznyj spisok na python chto eto takoe i kak ego realizovat 1e16d37 - Связный список на Python: что это такое и как его реализовать

Но вы не можете оставить последнюю секцию забора висящей в воздухе. Ограда должна закончится столбом, а не секцией. Поэтому вам приходится либо добавлять еще один столб в конце, либо (что в информатике более распространено) начать с постановки столба, а затем добавлять пары секция + столб. Это мы и сделаем.

Для начала мы выведем первый узел, а затем запустим цикл while для вывода всех последующих узлов.

node = ll print(node.data) while node.next:     node = node.next     print(node.data)

Запустив это для нашего предыдущего списка, мы получим в консоли:

 1  2  3

Ура! Наш связный список работает.

Зачем уметь создавать связный список на Python?

Зачем вообще может понадобиться создавать собственный связный список на Python? Это хороший вопрос. Использование связных списков имеет некоторые преимущества по сравнению с использованием просто списков Python.

Традиционно вопрос звучит как «чем использование связного списка лучше использования массива». Основная идея в том, что массивы в Java и других ООП-языках имеют фиксированный размер, поэтому для добавления элемента приходится создавать новый массив с размером N + 1 и помещать в него все значения из предыдущего массива. Пространственная и временная сложность этой операции — O(N). А вот добавление элемента в конец связного списка имеет постоянную временную сложность (O(1)).

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

Если вопрос производительности вас не тревожит, тогда да, проще реализовать обычный список Python. Но научиться реализовывать собственный связный список все равно полезно. Это как изучение математики: у нас есть калькуляторы, но основные концепции мы все-таки изучаем.

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

— Серия трюков по Python —

🐍 Python Tricks 💌

svjaznyj spisok na python chto eto takoe i kak ego realizovat 2dad273 - Связный список на Python: что это такое и как его реализовать

Python трюки »

🔒 Без Спама. Отписка в любой момент.

  • 4 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

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

Свежие комментарии

    Рубрики

    About Author 01.

    Roman Spiridonov
    Roman Spiridonov

    Привет ! Мне 38 лет, я работаю в области информационных технологий более 4 лет. Тут собрано самое интересное.

    Our Instagram 04.

    Categories 05.

    © Speccy 2020 / All rights reserved

    Связаться со мной
    Close