4
\$\begingroup\$

I know that Python has a built-in list data structure, but I want to implement my own linked list and stack data structures for practice.

I have three classes Node, Stack and List.

The code works, but I feel there is a better way to do this.

I would like to have some general critique.

class Node:
    def __init__(self):
        self.item = None
        self.link = None


class Stack:
    def __init__(self):
        self.top = 0
        self.head = Node()

    def isEmpty(self):
        return top == 0

    def push(self, item):
        oldHead = self.head
        self.head = Node()
        self.head.item = item
        self.head.link = oldHead
        self.top += 1


    def pop(self):
        item = self.head.item
        self.head = self.head.link
        self.top -= 1
        return item

class List:
    def __init__(self):
        self.top = 0
        self.head = Node()

    def get(self, *args):
        if not args:
            return self.head.item
        elif type(args[0]) is int:
            pos = args[0]
            current = self.head
            count = 0
            while count < pos - 1 and current.link != None:
                current = current.link
                count += 1
           return current.item
       else:  
            raise TypeError

    def pop(self, *args):
        if not args:
            item = self.head.item
            head = self.head.link
            return item

    def append(self, item):
        oldhead = self.head
        self.head = Node()
        self.head.item = item
        self.head.link = oldhead
        self.top += 1

    def insert(self, item, pos):
        current = self.head
        count = 0
        while count < pos - 1 and current.link != None:
            current = current.link
            count += 1
        node = Node()
        node.item = item

        node.link = current.link
        current.link = node
        self.top += 1
\$\endgroup\$
2
  • \$\begingroup\$ It’s more idiomatic to use if x is (not) None rather than the Boolean operators == and !=. \$\endgroup\$ – alexwlchan Apr 16 '15 at 16:33
  • \$\begingroup\$ Okay, makes sense. \$\endgroup\$ – Bhargav Apr 16 '15 at 16:42
4
\$\begingroup\$

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:

import collections
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 push and 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 List and Stack both inherit from the LinkedList.

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 and top methods. 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:

class LinkedList:
    def __init__(self):
        self.top_index = 0
        self.head = Node()

    def push(self, item):
        # Code from push / append here

    def pop(self):
        # Code that removes and returns the top here.

    def top(self):
        # Code that just returns the head here.

    def is_empty(self):
        return self.top_index == 0

class List(LinkedList):
    def insert(self, item, pos=0):
        # Code for insert here.

class Stack(LinkedList):
    # 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
        return item

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 *args. Using get as a model, something like this:

def get(self, pos=0):
    if pos == 0:
        return self.head.item
    elif pos > 0:
        current = self.head
        count = 0
        while count < pos - 1 and current.link != None:
            current = current.link
            count += 1
       return current.item
    else:
       raise IndexError()

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 :)

\$\endgroup\$
3
  • \$\begingroup\$ Wow, thanks for such a detailed response. I have only skimmed through it but there is so much for me to learn here. Thank you so much! \$\endgroup\$ – Bhargav Apr 28 '15 at 14:12
  • \$\begingroup\$ And yes, the pop method is incomplete. I really need to look more into default arguments. \$\endgroup\$ – Bhargav Apr 28 '15 at 14:18
  • \$\begingroup\$ @Bhargav You're welcome, glad I could help. Default arguments are one of my favorite features of Python, and one of the few things from C++ that I miss when I'm using Java :) \$\endgroup\$ – tsleyson Apr 28 '15 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.