5
\$\begingroup\$

A school student here. Hope you are having a nice day.

So, I implemented a Singly Linked List in Python and of course also a Node. I tried to make it have the best Big O time complexity I could. Here it is, please tell me what do you think can be improved, changed, etc.

class LinkedList():
    """
    A basic class implementing a Singly Linked List.

    LinkedList() - new empty linked list
    LinkedList(iterable) - new linked list with items of iterable:
    head - iterable[0] tail - iterable[-1]
    """

    class Node():
        """A class for a singly linked list node."""

        def __init__(self, value):
            """Initialize default values."""
            self.value = value
            self.link = None  # by default a node is linked to nothing

    def __init__(self, seq=()):
        """Initialize default values."""
        self.size = 0
        # While instantiated there are no elements in list
        # but None, to which will be linked the first element
        self.head = None
        node = self.head
        for i in seq:  # iterate through and copy contents
            new_node = self.Node(i)
            if node:
                node.link = new_node
                node = node.link
            else:
                # runs only once, at the first item,
                # when the list is empty(head is None)
                self.head = new_node
                node = self.head
            self.size += 1

    def __len__(self):
        """Implement len(self). Return the number of items in list."""
        return self.size

    def __iter__(self):
        """Implement iter(self)."""
        node = self.head
        while node:
            yield node.value
            node = node.link

    def __repr__(self):
        """Return repr(self)."""
        return self.__str__()

    def __str__(self):
        """Define string casting for the list."""
        node = self.head
        s = ''
        while node:
            s += str(node.value) + ' => '
            node = node.link
        return s + 'None'

    def __getitem__(self, index):
        """Implement indexing access: a[b]."""
        # change index if negative
        index = self.size + index if index < 0 else index
        if 0 <= index < self.size:
            i = 0
            node = self.head
            while i < index:
                node = node.link
                i += 1
            return node.value
        else:
            raise IndexError('list index out of range')

    def __setitem__(self, index, item):
        """Implement indexed assignment."""
        # change index if negative
        index = self.size + index if index < 0 else index
        if 0 <= index < self.size:
            i = 0
            node = self.head
            while i < index:
                node = node.link
                i += 1
            node.value = item
        else:
            raise IndexError('list assignment index out of range')

    def __delitem__(self, index):
        """Implement indexed deletion."""
        # change index if negative
        index = self.size + index if index < 0 else index
        # check .remove() method for explanation
        if 0 < index < self.size:
            i = 0
            node = self.head
            while i < index - 1:
                node = node.link
                i += 1
            node.link = node.link.link
            self.size -= 1
        elif index == 0:
            self.head = self.head.link
            self.size -= 1
        else:
            raise IndexError('list deletion index out of range')

    def __contains__(self, item):
        """Implement 'in' access: if item in..."""
        i = 0
        node = self.head
        while i < self.size:
            if node.value == item:
                return True
            node = node.link
            i += 1
        return False

    def insertStart(self, item):
        """Insert an item to the head of the link."""
        self.size += 1
        new_node = self.Node(item)

        if not self.head:  # check in the list has a head
            self.head = new_node
        else:
            new_node.link = self.head  # link the node to the head
            self.head = new_node  # make it the head

    def insertEnd(self, item):
        """Insert an item at the tail."""
        new_node = self.Node(item)
        if self.head:  # check if list is empty
            node = self.head
            while node.link:  # iterate through the list to get to the tail
                node = node.link
            node.link = new_node
        else:
            self.head = new_node  # create a head
        self.size += 1

    def insert(self, index, item):
        """Insert given item before specified index."""
        t = type(index)
        if t is not int:
            raise TypeError('{} cannot be interpreted as an integer'.format(t))
        else:
            # change index if negative
            index = self.size + index if index < 0 else index
            if index > self.size - 1:  # check for special cases
                self.insertEnd(item)
            elif index <= 0:
                self.insertStart(item)
            else:  # iterate through and insert item
                i = 0
                node = self.head
                while i < index - 1:
                    node = node.link
                    i += 1
                new_node = self.Node(item)
                new_node.link = node.link
                node.link = new_node
                self.size += 1

    def remove(self, value=None):
        """
        Remove the first occurence of the value(default head).

        Raises a ValueError if the is not present.
        Raises an IndexError if the list is empty.
        """
        if not self.head:
            raise IndexError("remove from an empty list")
        else:
            if value:  # check if value is provided
                if self.head.value == value:
                    self.head = self.head.link
                else:
                    node = self.head
                    try:
                        # iterate through the list while checking for
                        # given value and being one step behind to be
                        # able to efficiently remove it
                        while node.link.value != value:
                            node = node.link
                        node.link = node.link.link
                    except AttributeError:  # mute the original error
                        raise ValueError('value not present in list') from None
            else:
                self.head = self.head.link  # value not present. remove head
            self.size -= 1

    def index(self, item):
        """Return index of first occurence of specified item. -1 if absent."""
        i = 0
        node = self.head
        while i < self.size:
            if node.value == item:
                return i
            node = node.link
            i += 1
        return -1

    def reverse(self):
        """Reverse list in place."""
        current_node = self.head
        prev_node = None
        next_node = None

        while current_node:
            next_node = current_node.link
            current_node.link = prev_node

            prev_node, current_node = current_node, next_node
        self.head = prev_node
\$\endgroup\$
0

1 Answer 1

2
\$\begingroup\$

Your code is good because you implemented many __methods__ that allow natural use of the class with for and print built-ins.

A great way to make it easier to improve the code is to add automatic tests, for example with doctest.

Let me show you a practical example:

I note that __str__ repeats logic already inside __iter__, so first thing I write a test to see how it works now:

import doctest

class LinkedList():
  def __str__(self):
    """
    Define string casting for the list.

    >>> str(LinkedList([1, 2, 3]))
    '1 => 2 => 3 => None'
    """
    # old code

if __name__ == "__main__":
  doctest.testmod()

Than I write the new implementation that uses __iter__ through the for keyword:

def __str__(self):
    """
    Define string casting for the list.

    >>> str(LinkedList([1, 2, 3]))
    '1 => 2 => 3 => None'
    """
    return ' => '.join((str(x) for x in self)) + ' => None'

Just executing the code runs the test and I know that the new implementation works the same as the old one at least in this case. More tests can be added for example for empty list or different data types inside the list but this is the basic idea.

The same can be said for index, you can reuse the __iter__ logic once again:

def index(self, item):
    """
    Return index of first occurence of specified item. -1 if absent.

    >>> LinkedList(['a', 'b', 'c', 'd']).index('b')
    1

    """
    for index, x in enumerate(self):
        if x == item:
            return index
    return -1

In general when you write a collection the __iter__ method is very useful for implementing other methods.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Thanks for telling me that I could use __iter__ method inside class definition. I didn't know that it could be used inside definition so I went for more manual solutions. I will definitely keep that in mind. \$\endgroup\$
    – Nick
    Aug 27, 2018 at 19:28
  • 1
    \$\begingroup\$ What about map(str, self) instead of (str(x) for x in self)? \$\endgroup\$ Aug 27, 2018 at 22:29
  • \$\begingroup\$ @Solomon Ucko Yes It is the same, you can use It no problem \$\endgroup\$
    – Caridorc
    Aug 28, 2018 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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