Singly Linked List with special methods in python, stuck

Question

A singly linked list with two classes, Node and LinkedList, is easy enough to implement. however my issue is when it comes to a singly linked list with only first node access (No stored length, No last node access, and without the use of dummy nodes). The special methods I can't wrap my head around or find much about online are similar to pythons built-in list operations with O(1) complexity, such as follows:

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)

Any sort of lead, help, guidance would be greatly appreciated. For some reason I just cant interpret pythons built-in list operators into my own methods in LinkedList without having dummy nodes or stored length and an iterator. Looking at it it just seems like I'm so close yet nothing I do or find seems to help. Thank you.

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

Without seeing your code, I think the basic hint I can give is that if you're during Linked List-based operations, it's going to involve a lot of iteration. Using stuff like aa.cons(item) is going to be inefficient and based on iteration because unlike an array-based list, you can't jump to an item at a particular index.

For the following examples, I'm going to assume your LinkedList class has a variable called first that points to the first item in the list and each Node has a variable called next that points to the next item in the list and a variable called data that holds the data at that node.

For aa.first(), that should be easy since you already have a variable head pointing to the first item. Just return that.

For the other methods, you'll need iteration. This is an example of how you might loop through and print out the list.

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

For aa.rest(), you'll have to skip the first item and then loop through the rest of the list. To take a step in the list, you essentially keep track of your current location and iterate. To return list[1:], I imagine the easiest thing to do is make a new list and then iterate, adding all the items from 1 to the end.

aa.rest() is really just a special case of aa.cons(item). You iterate through the list until your current pointer reaches item and then make a new list containing everything from after that.

You don't necessarily have to make new lists to return from rest() and cons(...), it just depends on how you want to implement it. I'll leave insert for you to think about.

With a LinkedList that only has a pointer to the head, you're not going to get O(1) for anything other than adding to the front of the list or accessing the first item, everything else is going to be approximately O(N).

I hope that helps a bit!

Answer 2

@sgusc found the one really big problem with what you have so far: naming a function first and naming a data attribute first as well. The latter winds up overriding the former (because the function is actually in the class rather than the instance).

Fixing this gives something that is close to working. I simplified a few things, added a little test driver, and added an __iter__ that uses a generator to yield each node's data in turn, so that for i in self (in myList.__repr__) can work. 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)

Note that repr uses the name LinkedList even though the class name is myList. I usually write my repr functions to use self.__class__.__name__, e.g.:

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

which also allows a base-class __repr__ to work for derived classes (sometimes with a little assistance from the derived-class).