Реализация связанного списка с хвостом

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

Просмотреть его в обратном направлении от хвостового узла к головному.

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

Реализация

Мы начнем с определения класса Node, который будет использоваться для представления каждого узла в связанном списке. Каждый объект Node будет содержать атрибут data для хранения элемента и атрибут next для ссылки на следующий узел в последовательности.

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

После этого мы определим класс LinkedList, который будет содержать ссылку на головной и хвостовой узлы последовательности. Если список пуст, атрибут head будет установлен на None, а атрибут tail будет установлен на тот же узел, что и атрибут head.

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = self.head

Append

Переключение атрибута next текущего хвостового узла на ссылку на новый узел. Затем мы обновим атрибут tail, чтобы он ссылался на новый узел.

def append(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
    else:
        self.tail.next = new_node
    self.tail = new_node
    length += 1

Временная сложность метода append составляет O(1), так как он включает только обновление атрибутов next и tail связанного списка.

PrependМетод append добавляет элемент в конец связанного списка, создавая новый узел и обновляя его.

Метод prepend добавляет элемент в начало LinkedList, создавая новый узел с заданными данными, устанавливая его атрибут next в текущий головной узел и обновляя атрибут head для ссылки на новый узел.

def prepend(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head = new_node

Вставить

Метод insert добавляет элемент в LinkedList по заданному индексу путем создания нового узла, изменения следующего атрибута предыдущего узла для ссылки на новый узел и обновления следующего атрибута нового узла для ссылки на текущий узел с этим индексом. (сначала проверьте ошибку выхода индекса за пределы диапазона, условия append и prepend)

    def insert(self, index, data):
        if index < 0 or index > self.length:
            raise IndexError("Index out of range")
        if index == 0:
            self.prepend(data)
        elif index == self.length - 1:
            self.append(data)
        else:
            current_node = self.head
            for i in range(index - 1):
                if current_node is None:
                    return
                current_node = current_node.next
            if current_node is None:
                return
            new_node = Node(data)
            new_node.next = current_node.next
            current_node.next = new_node
            if new_node.next is None:
                self.tail = new_node
        self.length += 1

Pop

Метод pop удаляет элемент по определенному индексу в связанном списке, обновляя атрибут next предыдущего узла для ссылки на следующий узел, эффективно пропуская удаляемый узел.

def pop(self, index):
    if index < 0 or index > self.length:
        raise IndexError("Index out of range")
    if index == 0:
        if self.head is None:
            self.length -= 1
            return None
        removed_node = self.head
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.length -= 1
        return removed_node.data
    
    if index == self.length-1:
        self.length -= 1
        self.tail = None


    current_node = self.head
    for i in range(index - 1):
        if current_node.next is None:
            self.length -= 1
            return None
        current_node = current_node.next

    if current_node.next is None:
        self.length -= 1
        return None

    removed_node = current_node.next
    current_node.next = removed_node.next
    if current_node.next is None:
        self.tail = current_node
    
    self.length -= 1
    return removed_node.value

Временная сложность метода pop составляет O(n), где n - длина связанного списка, так как нам может потребоваться пройти весь список, чтобы найти предыдущий узел по заданному индексу.

Обратный

Метод reverse изменит порядок следования узлов в связанном списке.

def reverse(self):
    prev_node = None
    current_node = self.head
    while current_node is not None:
        next_node = current_node.next
        current_node.next = prev_node
        prev_node = current_node
        current_node = next_node
    self.head, self.tail = self.tail, self.head

Временная сложность обратного метода составляет O(n), где n - длина связанного списка, так как нам нужно обойти весь список один раз. Обходя связанный список и изменяя следующий атрибут каждого узла для ссылки на предыдущий узел в последовательности, мы получаем

Методы Дандера

__len__

Метод __len__ возвращает длину связанного списка, то есть количество узлов в списке.

def __len__(self):
    return self.length

Временная сложность метода __len__ равна O(n), где n - длина связанного списка, так как для подсчета узлов нам нужно один раз обойти весь список.

__str__

Метод __str__ вернет строковое представление связанного списка.

def __str__(self):
    nodes = []
    current_node = self.head
    while current_node is not None:
        nodes.append(str(current_node.value))
        current_node = current_node.next
    return ' -> '.join(nodes)

Метод __str__ имеет временную сложность O(n), где n - длина связанного списка, потому что мы должны пройти весь список один раз, чтобы построить список значений узлов и затем соединить их в строку.

__getitem__

Метод __getitem__ позволит нам получить доступ к узлам в связанном списке, используя индексацию.

def __getitem__(self, index):
    if index < 0 or index >= len(self):
        raise IndexError('Index out of range')
    current_node = self.head
    for i in range(index):
        current_node = current_node.next
    return current_node.data

Временная сложность метода __getitem__ составляет O(n), где n - длина связанного списка, поскольку нам может потребоваться пройти весь список, чтобы найти узел с заданным индексом.

__setitem__

Метод __setitem__ позволит нам изменять данные узлов в связанном списке с помощью индексации.

 def __setitem__(self, index, data):
    if index < 0 or index >= len(self):
        raise IndexError('Index out of range')
    current_node = self.head
    for i in range(index):
        current_node = current_node.next
    current_node.data = data

Временная сложность метода __setitem__ составляет O(n), где n - длина связанного списка, поскольку нам может потребоваться пройти весь список, чтобы найти узел с заданным индексом.

Заключение

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

Временная сложность процедур добавления и возврата составляет O(1) и O(n), соответственно, в то время как временная сложность методов вставки и вывода составляет O(n), где n - длина связного списка. В целом, связные списки с хвостом позволяют эффективно добавлять данные, но при этом допускают обход в обоих направлениях.