5
\$\begingroup\$

I am currently reading through an algorithm book and trying to implement everything as I go. I am also learning python at the same time. This is my implementation of a simple linked-list. I am mainly concerned with whether the code looks "looks python like" any tips on how I can refactor would be greatly appreciated.

class Linked(object):
    # init
    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, data):
        temp = Node(data, None, None)
        if (self.head is None):
            self.head = temp
            self.tail = temp
        else:
            self.tail.setAfter(temp)
            temp.setBefore(self.tail)
            self.tail = temp

    def find(self, data):
        if (self.head is None):
            return "Empty List"
        else:
            current = self.head
            while (current is not None):
                if (current.element() is data):
                    return current
                current = current.next()
        return "Element not in List"

    def remove(self, data):
        if (self.head is None):
            return "Empty List"
        elif(self.find(data).element() is data):
            temp = self.find(data)
            if (temp is self.head and temp is self.tail):
                self.head = None
                self.tail = None
            elif (temp is self.head):
                self.head = temp.next()
                self.head.setBefore(None)
                return
            elif (temp is self.tail):
                temp.before.setAfter(None)
                return
            else:
                temp.before.setAfter(temp.after)
                temp.after.setBefore(temp.before)

    def iterator(self):
        if (self.head is None):
            return "Empty List"
        else:
            current = self.head
            while (current is not None):
                print(current.element())
                current = current.next()


class Node(object):
    # init
    def __init__(self, data=None, before=None, after=None):
        self.data = data
        self.before = before
        self.after = after

    def element(self):
        return self.data

    def setBefore(self, before):
        self.before = before

    def setAfter(self, after):
        self.after = after

    def next(self):
        return self.after
\$\endgroup\$
7
\$\begingroup\$

You could make your life a lot easier if you used the fact that Python allows you to give custom classes built-in behavior. This allows you to define classes for which e.g. a + b is defined or, as in this case for x in obj.

The way Python allows this is via so called dunder (short for double-underscore) or magic methods. These are special method names which get invoked under certain circumstances.

If you ask Python to iterate over an object obj, it calls the method obj.__iter__ (or at least tries to). If you write a + b it first calls a.__add__(b) and if that does not work b.__radd__(a).

A linked list is predestined to have this method:

class Linked(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, data):
        temp = Node(data, None, None)
        if self.head is None:
            self.head = self.tail = temp
        else:
            self.tail.next = temp
            temp.prev = self.tail
            self.tail = temp

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current.data
            current = current.next
        raise StopIteration

Together with a greatly simplified Node class:

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

    def __repr__(self):
        return repr(self.data)

This already allows simple things like iterating:

l = Linked()
l.add(1)
l.add(3)
print(list(l))
# [1, 3]
for x in l:
    print(x)
# 1
# 3

The other methods can then take advantage of the fact that it is easy to iterate over the object:

class Linked(object):
    def __init__(self, data=None):
        self.head = None
        self.tail = None
        if data is not None:
            for x in data:
                self.append(x)

    def append(self, data):
        if self.head is None:
            self.head = self.tail = Node(data)
        else:
            node = Node(data, self.tail)
            self.tail.next = node
            self.tail = node

    def __iter__(self):
        current = self.head
        while current is not None:
            yield current
            current = current.next

    def find(self, data):
        for x in self:
            if x.data == data:
                return x
        return None

    def __len__(self):
        return sum(1 for _ in self)

    def __repr__(self):
        return repr(list(self))

    def remove(self, data):
        x = self.find(data)
        if x is None:
            return
        if x is self.head:
            if x is self.tail:
                self.head = self.tail = None
            else:
                self.head = x.next
                self.head.prev = None
        elif x is self.tail:
            x.prev.next = None
        else:
            x.prev.next = x.next
            x.next.prev = x.prev

Here I modified the __iter__ method to yield the nodes, not just the data, removed the manual raising of StopIteration (it is not needed and actually deprecated in Python 3), added a __len__ and __repr__ method for convenience (the latter gets called when you call repr(obj) or when you just enter the variable name in an interactive session), renamed add to append (to mirror the normal list interface), added an optional argument to the constructor to ease initializing a linked list from an iterable and used the optional arguments of Node to make the append method slightly easier to read.

Also note that your class is actually a doubly-linked list, since each node has a pointer to the previous and the next node.

\$\endgroup\$
  • \$\begingroup\$ Okay, so I did some reading up on dunder methods. Just to clarify, Since I pass object as a parameter when I define my classes they both inherit the methods from object. You then overrode those methods in __iter__, __len__, and __repr__. Is that correct? \$\endgroup\$ – k4iru May 15 '18 at 21:25
  • \$\begingroup\$ @k4iru No, not really. The inheritance from object does not have anything to do with it. This also works with old-style classes in Python 2, which do not inherit from object. It is just a feature of Python that it looks for these method names. Also note that in Python 3 all classes inherit from object (they are new-style classes) so you don't need to actually do it explicitly (but it is ok for backwards compatibility). \$\endgroup\$ – Graipher May 16 '18 at 6:42
  • \$\begingroup\$ I see, so Python just has a list of built in dunder methods. Thank you! \$\endgroup\$ – k4iru May 16 '18 at 20:19
1
\$\begingroup\$

You should avoid the extra parens. Returning strings in cases where the list is empty is pretty odd, too. iterator() doesn't work like I'd expect it to. element() seems like a weird name for a getter, and I think it'd be more idiomatic to not have a getter. I'd try to get find and remove to use the iterator.

\$\endgroup\$

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.