Изучение структур данных Python

На пути каждого разработчика рано или поздно наступает время, когда стандартные структуры данных, такие как строки, целые числа, списки, наборы, кортежи, словари, не соответствуют требованиям проекта. Именно здесь в игру вступают абстрактные типы данных (ADT). АТД представляют собой набор операций, которые могут выполняться с данными и определяются поведением данных, а не их реализацией. В этой серии мы рассмотрим различные структуры данных Python, начиная, пожалуй, с самой простой — Односвязные списки.

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

Как, вероятно, видно из рисунка выше, основное различие между массивом и связанным списком заключается в том, что массив хранит информацию в последовательном порядке, тогда как связанные списки хранят информацию динамически в разных ячейках памяти. Динамическая мода SSL исходит из того факта, что все данные связаны друг с другом с помощью так называемых «указателей». Каждая часть данных, хранящихся в памяти, содержит (мы будем называть их узлами) два значения: первое — это фактические данные, которые будет использовать наша программа, а второе — указатель на следующий узел в ссылке. На рисунке ниже последовательное представление того, о чем мы говорим.

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

Создание связанного списка на самом деле не так сложно, но требует некоторого планирования, прежде чем мы начнем. Первое, что нужно упомянуть здесь, это то, что наш список предполагает, что начало списка (0x1000) будет его «ХВОСТОМ», а последним узлом в списке будет «ГОЛОВА». Я видел, как люди делают это наоборот, но на самом деле не так уж важно, как вы их сокращаете, если вы используете их с осторожностью в своей программе.

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

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

Довольно просто, правда? И это так просто. Мы только что создали один узел с простым конструктором, который принимает в качестве аргументов сам объект (self) и данные<. /em> что он держит. Еще одна часть информации, которую мы собираемся хранить в нашем узле, — это ссылка на следующий узел в ссылке. Для следующей переменной в конструкторе задано значение None, потому что в начале мы не знаем, куда направить создаваемый нами узел. Итак, давайте начнем и создадим несколько узлов.

# main.py
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3

>>> print(node1.data)
1
>>> print(node2.data)
2
>>> print(node3.data)
3

# Node 1
>>> print (hex(id(node1)))
0x16e9160
>>> print (hex(id(node1.next))) 
0x16e91f0
>>> print (hex(id(node1.data))) 
0x5d41e7b0
# Node 2
>>> print (hex(id(node2)))        
0x16e91f0
>>> print (hex(id(node2.data))) 
0x5d41e7c0
>>> print (hex(id(node2.next))) 
0x16e92b0
# Node 3
>>> print (hex(id(node3)))      
0x16e92b0
>>> print (hex(id(node3.data))) 
0x5d41e7d0
>>> print (hex(id(node3.next))) 
0x5d408ce8
>>> print(node3.next)
None

>>> print(node1)
>>> <__main__.Node object at 0x16E9160>

# main.py
def __str__(self):
    return str(self.data)

# main.py
class Node():
    def __init__(self, data):
        self.data = data
        self.next = None
    def __str__(self):
        return str(self.data)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3