It's a little hard to review code like this in Python because we're pretending there's no built-in list class, but a Python without a list doesn't feel like Python at all, so the code ends up looking like some other language.
I mention this because there are named tuples in Python 2.7 and Python 3, and they pretty much do exactly what your
Node class does:
Node = collections.namedtuple('Node', ['item', 'link'])
n = Node(item=22, link=self.head) # Make a new node.
Then again, if we're pretending lists don't exist, maybe we should pretend tuples don't exist either.
There's a lot of duplication in your code. These two classes are very similar. The
append methods appear to be exactly the same method, for example. The two
pop methods are almost exactly the same. The constructors are the same. So this seems like a good place to use inheritance. Make a base class, maybe with a name like
LinkedList, which has the constructor and any methods which are exactly the same. Make the
Stack both inherit from the
In your current code, you have separate implementations for
pop that seem to do exactly the same thing, except that the stack version also removes the item. I would add separate
pop always removes and returns the top item, while
top just returns the item without removing it. Then, if you want to make it impossible to remove the top item of a list, override the
pop method to just call
top. This is more or less how C++'s STL works, although C++'s
pop doesn't return the item it removed.
So the final code would look something like this:
self.top_index = 0
self.head = Node()
def push(self, item):
# Code from push / append here
# Code that removes and returns the top here.
# Code that just returns the head here.
return self.top_index == 0
def insert(self, item, pos=0):
# Code for insert here.
# Whatever functionality is unique to the stack.
# If there isn't any, you can consider not having a stack
# class and just using a LinkedList.
I'll leave the details up to you, but that's basically how I would do it.
Am I right in thinking the following function is incomplete?
def pop(self, *args):
if not args:
item = self.head.item
head = self.head.link
Were you going to add an
else clause the retrieves the item at a specified index, like what you have in
get? If that was what you had in mind, I think default arguments would be a better solution than using
get as a model, something like this:
def get(self, pos=0):
if pos == 0:
elif pos > 0:
current = self.head
count = 0
while count < pos - 1 and current.link != None:
current = current.link
count += 1
I find this clearer than the version with
*args. Also, in case you wanted to use
*args in the future, you can now do so without having to parse it.
Your use of style conventions and code formatting looks good. It can be confusing to get this right in Python since the standard library sets such a horrible example :)