Структуры данных
Реализация Python (LinkedList)
# Полная работающая программа LinkedList на Python в 55 строках кода.
Шаг 1 — класс Node(object)
Мы начнем с создания класса для представления Node. В этом узле мы будем хранить значение и переменную, указывающую на следующий узел.
Мы используем __init__
для инициализации нового Node
. С узлом связан некоторый self.value
(это может быть что угодно — число, строка, символ и т. д.), и у него есть переменная, указывающая на self.next
узел в связанном списке.
Вот код узла, который будет отдельной единицей в связанном списке:
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
Теперь мы просто устанавливаем, что LinkedList
— это то, что имеет head
Node
, который является первым узлом в списке. Если мы установим новый LinkedList
без head
, по умолчанию будет None.
class LinkedList(object):
def __init__(self, head=None):
self.head = head
Шаг 2 — append() и getPosition()
Наш первый метод добавит новый Node
в конец нашего LinkedList
.
Приведенный ниже код проверяет, есть ли у LinkedList
уже head
, затем он будет перебирать ссылку next
в каждом Node
, пока не будет достигнут конец список. Установите current.next
, чтобы конец списка был new_node
. В качестве альтернативы, если head
еще нет, вы должны просто назначить ему self.head = new_node
и больше ничего не делать.
def append(self, new_node):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_node
else:
self.head = new_node
Если вы хотите добавить дополнительные функции, можете реализовать следующий код, чтобы получить точную позицию узла в LinkedList.
def get_position(self, position):
counter = 1
current = self.head
if position < 1:
return None
while current and counter <= position:
if counter == position:
return current
current = current.next
counter += 1
return None
Шаг 3 — Insert() и delete()
Следующие строки кода позволят вам вставить новый узел в любую желаемую позицию.
def insert(self, new_node, position):
counter = 1
current = self.head
if position > 1:
while current and counter < position:
if counter == position - 1:
new_node.next = current.next
current.next = new_node
current = current.next
counter += 1
elif position == 1:
new_node.next = self.head
self.head = new_node
Приведенный ниже код позволит пользователю удалить любой узел в очереди из Link-List, вызвав приведенный ниже метод.
def delete(self, value):
current = self.head
previous = None
while current.value != value and current.next:
previous = current
current = current.next
if current.value == value:
if previous:
previous.next = current.next
else:
self.head = current.next
Полная реализация
Тестовые случаи
Хорошей практикой является тестирование вашего кода, чтобы увидеть, работает ли он (:
Поздравляем с завершением реализации LinkedList на Python. Итак, это основы реализации LinkedList. Методы довольно логично следуют из фактического дизайна и алгоритма, лежащего в его основе :)
Теперь попробуйте решить задачу/задачу по кодированию в LinkedList, чтобы применить свои знания!