4
\$\begingroup\$

This is my code for the implementation of a singly linked list in Python:

class SList:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, item):
        try:
            if not item:
                raise ValueError
            self.size += 1
            if self.root is None:
                self.root = Node(item)
            else:
                p = Node(item)
                p.next = self.root
                self.root = p
        except ValueError:
            raise ValueError('Cannot add None item to a list')

    def remove(self, index):
        try:
            if index < 0 or index >= self.size:
                raise ValueError

            current = self.root
            count = 0
            while count < index:
                current = current.next
                count += 1
            current.next = current.next.next
            self.size -= 1
        except ValueError:
            raise ValueError('Index cannot be negative or greater than the size of the list')

    def __sizeof__(self):
        return self.size


class Node:
    def __init__(self, data):
        try:
            if not data:
                raise ValueError
            self.data = data
            self.next = None
        except ValueError:
            raise ValueError('Node cannot be instantiated without an item')
\$\endgroup\$
5
\$\begingroup\$

raise + except + raise = raise

def remove(self, index):
    try:
        if index < 0 or index >= self.size:
            raise ValueError

            ...

    except ValueError:
        raise ValueError('Index cannot be negative or greater than the size of the list')

It make no sense to except and raise again, simplify to:

if index < 0 or index >= self.size:
    raise IndexError('Index cannot be negative or greater than the size of the list')

...

The function will look like:

def insert(self, item):
    if item is None:
        raise ValueError('Cannot add None item to a list')
    self.size += 1
    if self.root is None:
        self.root = Node(item)
    else:
        p = Node(item)
        p.next = self.root
        self.root = p

for instead of counting loop

for is a more streamlined way of looping n times than a while loop:

        count = 0
        while count < index:
            current = current.next
            count += 1

Becomes:

for _ in range(index):
    current = current.next

(Please note _ is a convention meaning the value will not be used)

\$\endgroup\$
  • \$\begingroup\$ I'm new to Python, as regards the try and except, what do I put in the except block in this case. \$\endgroup\$ – Stacker Dec 19 '16 at 20:11
  • \$\begingroup\$ @Stacker nothing, you just remove it \$\endgroup\$ – Caridorc Dec 19 '16 at 20:12
  • \$\begingroup\$ My editor gives a compilation time squiggly if I remove the except block \$\endgroup\$ – Stacker Dec 19 '16 at 20:13
  • 1
    \$\begingroup\$ @Stacker added example \$\endgroup\$ – Caridorc Dec 19 '16 at 20:21
  • \$\begingroup\$ If you have "Index cannot...", you could use IndexError instead of ValueError: the index is wrong, not the value. \$\endgroup\$ – Laurent LAPORTE Dec 20 '16 at 0:16
4
\$\begingroup\$

Docstrings would be a good idea. It is not immediately obvious, for example, that insert() manipulates the head of the list. Also, "head" is a more common term when talking about linked lists; "root" would be more appropriate for graphs.

Judging by raise ValueError('Cannot add None item to a list'), this is wrong:

if not item:
   raise ValueError

It looks like you intended to forbid None from being inserted, but you are actually also preventing 0, False, or empty strings from being inserted as well.

raise ValueError is poor style as well, if what you really mean to do is raise ValueError('Cannot add None item to a list'). But that seems to be redundant with the check that you wrote in the Node constructor.


Your remove() method is unable to remove the last element in the list.

Counting loops, such as the one in remove(), are idiomatically done using range() or xrange().

You can use a double-ended inequality to check that the index is in range. I'd raise an IndexError instead of a ValueError if the index is out of range.

if not 0 <= index < self.size:
    raise IndexError('Index cannot be negative or greater than the size of the list')

The code would be simplified by having the Node constructor accept an optional next parameter.

class Node:
    def __init__(self, data, next=None):
        if data is None:
            raise ValueError('Node value cannot be None')
        self.data = data
        self.next = next

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

    def insert(self, value):
        """Insert a value (which cannot be None) at the head of the list."""
        self.head = Node(value, self.head)
        self.size += 1
\$\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.