3
\$\begingroup\$

Here's my implementation of doubly linked list in Python:

 class DList:

    def __init__(self):
        self.head = None
        self.size = 0

    def insert(self, data):
        self.size += 1
        if self.head is None:
            self.head = Node(data)
        else:
            p = Node(data)
            p.next = self.head
            self.head.previous = p
            self.head = p

    def remove(self, index):
        if self.head is None:
            raise ValueError('Removing off an empty list')
        if index < 0 or index >= self.size:
            raise IndexError("Index is either negative or greater than the list size.")
        current = self.head
        if index == 0:
            self.head = self.head.next
            self.head.previous = None
        else:
            for _ in range(index -1):
                current = current.next
            p = current.next.next
            if p is None:
                current.next = None
            else:
                current.next = p
                p.previous = current

    def __sizeof__(self):
        return self.size

    def __repr__(self):
        res = '[ '
        current = self.head
        while current is not None:
            res += str(current.data)
            res += ' '
            current = current.next
        res += ']'
        return res


class Node:
    def __init__(self, data):
        if data is None:
            raise ValueError('Node value cannot be None')
        self.data = data
        self.previous = None
        self.next = None
\$\endgroup\$
  • \$\begingroup\$ It would be nice if you made an attempt to incorporate advice from your previous question. \$\endgroup\$ – 200_success Dec 19 '16 at 21:31
  • \$\begingroup\$ Which I assume I did. Which advice am I missing in this implementation, again, except adding docstring. \$\endgroup\$ – Stacker Dec 19 '16 at 21:33
  • 1
    \$\begingroup\$ remove() is still unable to remove the last element of the list, for example. \$\endgroup\$ – 200_success Dec 19 '16 at 21:37
  • 1
    \$\begingroup\$ Fixed the remove() bug. \$\endgroup\$ – Stacker Dec 19 '16 at 22:31
5
\$\begingroup\$

OK, a few things:

  1. I would make head and size private, you don't want them changed from outside the class.

  2. You should use __len__ instead of __sizeof__ - they have different meanings.

  3. Implement __iter__

  4. After doing #3, format the repr using:

    "[{}]". format(", ". join(map(str, self)))
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Making head and size private is just adding an _ before them, right? \$\endgroup\$ – Stacker Dec 19 '16 at 23:39
  • \$\begingroup\$ I'm also a little lost on how to implement iter on this list. I understand one has to implment next and return self. A little help will be appreciated. \$\endgroup\$ – Stacker Dec 19 '16 at 23:43
  • \$\begingroup\$ You are correct about the underscore. Implementing iter is simpler than that - it should be a function using the yield keyword. I'll suggest you Google it up. Ask if you need further explanation. \$\endgroup\$ – Shain Dec 20 '16 at 0:03

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.