Python LinkedList с 2 указателями - PullRequest
Новая
       77

Python LinkedList с 2 указателями

0 голосов
/ 16 октября 2018 
class Node:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None

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

    def insert_node(self, node_data):
        node = Node(node_data)

        if not self.head:
            self.head = node
        else:
            self.tail.next = node


        self.tail = node

# Complete the printLinkedList function below.

    def printList(self):
        while self.head is not None:
            print(self.head.data)
            self.head = self.head.next

l = LinkedList()
l.insert_node(5)
l.insert_node(10)
l.insert_node(19)
l.printList()

Я пытаюсь реализовать связанный список, используя итерационный метод.У меня 2 указателя (голова, хвост).так или иначе, чтобы избежать использования двух указателей без рекурсии.а для функции printList рекомендуется использовать только указатель на голову.Любые отзывы приветствуются

1 Ответ

0 голосов
/ 16 октября 2018

С вашей текущей реализацией связанного списка, self.tail действительно не служит никакой другой цели, кроме ускорения вставки в конце.Вы можете отбросить его, выполнив итерацию всех операций связанного списка с указателем заголовка, как в методе printList().Имейте в виду, хотя это и позволяет избежать рекурсии, это по своей сути заставляет все операции быть O (n);это неплохо, так как это типично для упрощенных связанных списков.

Назначение указателя хвоста и узлов, ссылающихся на предыдущие узлы, заключается в том, что вы также можете поддерживать обратный обход.Это простая оптимизация, но улучшение становится только O (n / 2): достаточно хорошо для коротких списков, но бессмысленно в больших списках.Опять же, это обучающий момент использования такой структуры над векторизованными, упорядоченными и древовидными структурами данных.

...