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

Реализация 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, чтобы применить свои знания!