Отдельно связанный список со специальными методами в python, stuck

Question

Отдельно связанный список с двумя классами, узлом и LinkedList, достаточно прост для реализации. однако моя проблема заключается в том, когда речь идет о односвязном списке с единственным доступом к первому узлу (без сохранения длины, без доступа к последнему узлу и без использования фиктивных узлов). Специальные методы, которые я не могу обернуть мою голову вокруг или найти много об Интернете похожи на питон встроенных в списке операциях с O (1) сложностью, например следующим образом:

aa = LinkedList() -- creates empty list 
aa.first() -- similar to aa[0] 
aa.rest() -- similar to aa[1:] 
aa.cons(item) -- similar to aa[item:] 
[item] + aa -- similar to aa.insert(0, item) 

Любого вид свинца, помощи, руководство будет с благодарностью оценено. По какой-то причине я просто не могу интерпретировать встроенные операторы списков pythons в свои собственные методы в LinkedList, не имея фиктивных узлов или сохраненной длины и итератора. Глядя на это, мне кажется, что я так близко, но ничего, что я делаю или не нашел, кажется, помогает. Спасибо.

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

    def getData(self): 
    return self.data 

    def getNext(self): 
    return self.next 

    def setData(self, newdata): 
    self.data = newdata 

    def setNext(self, newnext): 
    self.next = newnext 

    def __str__(self): 
    return str(self.data) 

    def __repr__(self): 
    return "Node(%s, %s)" % (repr(self.data), repr(self.next)) 

    def __eq__(self, other): 
    return self.data == other.data and self.next == other.next 

class myList: 
    def __init__(self): 
    self.first = Node() 

    def add(self, data): 
    newNode = Node() # create a new node 
    newNode.data = data 
    newNode.next = self.first # link the new node to the 'previous' node. 
    self.first = newNode # set the current node to the new one 

    def first(self): 
    return self.first.data 


    def __repr__(self): 
    plist = [] 
    for i in self: 
     plist.append(i) 
    return "LinkedList(%s)" % str(plist) 

Answer 1

Не видя кода, я думаю, что основная намек я могу дать, что если вы во время Linked операций на основе списка, он будет включать в себя много итераций. Использование такого материала, как aa.cons(item), будет неэффективным и основано на итерации, потому что, в отличие от списка на основе массива, вы не можете перейти к элементу определенного индекса.

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

Для aa.first() это должно быть легко, так как у вас уже есть переменная head, указывающая на первый элемент. Просто верни это.

Для других методов вам понадобится итерация. Это пример того, как вы можете прокручивать и распечатывать список.

current = list.first 
while current is not None: 
    print current.data 
    current = current.next 

Для aa.rest(), вам придется пропустить первый пункт, а затем петлю через остальную часть списка. Чтобы сделать шаг в списке, вы в основном отслеживаете свое текущее местоположение и повторяете его. Чтобы вернуть список [1:], я представляю себе, что проще всего сделать новый список, а затем повторить его, добавив все элементы от 1 до конца.

aa.rest() действительно просто частный случай aa.cons(item). Вы перебираете список до тех пор, пока ваш текущий указатель не достигнет item, а затем создайте новый список, содержащий все после этого.

Вам необязательно делать новые списки для возврата от rest() и cons(...), это зависит от того, как вы хотите его реализовать. Я оставлю вставку, чтобы вы подумали.

С LinkedList, что имеет только указатель на head, вы не собираетесь получить O (1) для чего-нибудь другого, чем добавление к передней части списка или доступа к первому пункту, все остальное собирается быть приблизительно O (N).

Я надеюсь, что это поможет!

Answer 2

@sgusc нашел одну действительно большую проблему с тем, что у вас есть до сих пор: присвоение функции first и присвоение имени атрибуту данных first. Последний задерживает переопределение первого (потому что функция фактически находится в class, а не в экземпляре).

Фиксация этого дает то, что близко к работе. Я упростил несколько вещей, добавил небольшой тестовый драйвер и добавил __iter__, который использует генератор для получения данных каждого узла по очереди, так что может работать for i in self (в myList.__repr__). Diff:

--- a/user1337598.py 
+++ b/user1337598.py 
@@ -1,4 +1,4 @@ 
-class Node: 
+class Node(object): 
    def __init__(self, data=None, next=None): 
    self.data = data 
    self.next = next 
@@ -19,27 +19,36 @@ class Node: 
    return str(self.data) 

    def __repr__(self): 
- return "Node(%s, %s)" % (repr(self.data), repr(self.next)) 
+ return "Node(%r, %r)" % (self.data, self.next) 

    def __eq__(self, other): 
    return self.data == other.data and self.next == other.next 

-class myList: 
+class myList(object): 
    def __init__(self): 
- self.first = Node() 
+ self.first = None 

    def add(self, data): 
- newNode = Node() # create a new node 
- newNode.data = data 
- newNode.next = self.first # link the new node to the 'previous' node. 
+ newNode = Node(data, self.first) # create a new node 
    self.first = newNode # set the current node to the new one 

- def first(self): 
+ def getFirst(self): 
    return self.first.data 

+ def __iter__(self): 
+  node = self.first 
+  while node is not None: 
+   yield node.data 
+   node = node.next 

    def __repr__(self): 
    plist = [] 
    for i in self: 
     plist.append(i) 
    return "LinkedList(%s)" % str(plist) 
+ 
+if __name__ == '__main__': 
+ lst = myList() 
+ lst.add(1) 
+ lst.add(2) 
+ print repr(lst) 

Обратите внимание, что repr использует имя LinkedList даже если имя класса myList. Я обычно пишу мои repr функции использовать self.__class__.__name__, например .:

def __repr__(self): 
    return '%s(%r, %r)' % (self.__class__.__name__, self.item1, self.item2) 

, который также позволяет базовый класс __repr__ работать для производных классов (иногда с небольшой помощью от производного класса).