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

Не видя вашего кода, я думаю, что основной совет, который я могу дать, заключается в том, что если вы выполняете операции на основе связанного списка, это потребует большого количества итераций. Использование таких вещей, как 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() вам придется пропустить первый элемент, а затем просмотреть остальную часть списка. Чтобы сделать шаг в списке, вы, по сути, отслеживаете свое текущее местоположение и выполняете итерацию. Чтобы вернуть list[1:], мне кажется, проще всего создать новый список, а затем выполнить итерацию, добавляя все элементы с 1 до конца.

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

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

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

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

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

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

--- 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__ работать с производными классами (иногда с небольшой помощью производного класса).