Linked List implementation in Python

Question

I'm a data scientist attempting to build stronger CS fundamentals, particularly in Data Structures & Algorithms.

Below is my attempt at implementing a Singly Linked List. Looking for advice regarding:

1. Code style
2. Can space/time complexity of methods be improved?
3. Debugging in case I missed any edge cases
4. Checking for premature optimizations

Demonstrates implementation of a linked list and helper Node class

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None


class Linkedlist:
    def __init__(self, *args):
        self.head = Node()
        self.tail = self.head
        self.size = 0
        # Nodes indexes defined from 0, 1, ..., N - 1 (where N = self.size) but are counted as First Node, Second Node, ..., Nth-Node respectively
        self._args = args
        if len(self._args) > 0:
            for val in self._args:
                self.append(val)

    def __len__(self):
        return self.size

    def _get_prev_node(self, index):
        """gets Node previous to given index
        i.e. if index is 1, will return Node 0 (1st Node)
        i.e. if size of linked list is 6 & index is -3, will return Node 3 (4th Node)
        """
        if index < 0:
            index += self.size
        cur_node = self.head
        prev_node_number = 1
        while prev_node_number < index:
            cur_node = cur_node.next
            prev_node_number += 1
        return cur_node

    def __getitem__(self, index):
        if index >= self.size or index < -self.size:
            raise IndexError
        elif index == 0 or index == -self.size:
            return self.head.value
        else:
            prev_node = self._get_prev_node(index)
            cur_node = prev_node.next
            return cur_node.value

    def __delitem__(self, index):
        if index >= self.size or index < -self.size:
            raise IndexError
        elif index == 0 or index == -self.size:
            self.head = self.head.next
        else:
            prev_node = self._get_prev_node(index)
            prev_node.next = prev_node.next.next
            if index == -1 or index == self.size - 1:
                self.tail = prev_node
        self.size -= 1

    def __repr__(self):
        values = []
        cur_node = self.head
        for _ in range(self.size):
            values.append(str(cur_node.value))
            cur_node = cur_node.next
        return ' -> '.join(values)

    def append(self, value):
        if self.head.value is None:
            self.head.value = value
        else:
            new_node = Node(value)
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def prepend(self, value):
        if self.head.value is None:
            self.head.value = value
        else:
            new_node = Node(value)
            new_node.next = self.head
            self.head = new_node
        self.size += 1

    def insert(self, value, index):
        # Inserts node with value before given index
        if abs(index) > self.size:
            raise IndexError
        elif index == 0 or index == -self.size:
            self.prepend(value)
        elif index == self.size:
            self.append(value)
        else:
            prev_node = self._get_prev_node(index)
            new_node = Node(value)
            new_node.next = prev_node.next
            prev_node.next = new_node
            self.size += 1


def main():
    def disp_attributes(lnk_list_obj):
        print(f'Linked List: {lnk_list_obj}')
        print(f'\tSize: {len(lnk_list_obj)}')
        print(f'\tHead node value: {lnk_list_obj.head.value}')
        print(f'\tTail node value: {lnk_list_obj.tail.value}')

    print('<< Instantiate empty Linked List >>')
    lnk = Linkedlist()
    disp_attributes(lnk)

    print('<< Append -3, 1, 0 to Linked List >>')
    values = -3, 1, 0
    for val in values:
        lnk.append(val)
        disp_attributes(lnk)

    print('<< Prepend -12 to Linked List >>')
    lnk.prepend(-12)
    disp_attributes(lnk)

    print(f'Linked List value at first Node: {lnk[0]}')

    print('<< Instantiate Linked List with values 1, -2, -6, 0, 2 >>')
    lnk2 = Linkedlist(1, -2, -6, 0, 2)
    disp_attributes(lnk2)

    print('<< Prepend 6 to Linked List >>')
    lnk2.prepend(6)
    disp_attributes(lnk2)

    print(f'Linked List value at second Node: {lnk2[1]}')

    print('<< Delete First Node >>')
    del lnk2[0]
    disp_attributes(lnk2)

    print('<< Delete Last Node >>')
    del lnk2[-1]
    disp_attributes(lnk2)

    print('<< Append 7 to LinkedList >>')
    lnk2.append(7)
    disp_attributes(lnk2)

    print('<< Delete 3rd Node >>')
    del lnk2[2]
    disp_attributes(lnk2)

    print('<< Insert -10 before 2nd Node >>')
    lnk2.insert(-10, 1)
    disp_attributes(lnk2)


if __name__ == '__main__':
    main()

Answer 1

You should add """docstrings"""" for each public class and method, describing what it does and how to use it.

---

class Node

This class has members value and next, which are not for use outside of the linked list implementation. You should rename these member to _value and _next, to indicate they are "private".

Actually, Node itself is an implementation detail of the LinkedList, so you could name it class _Node, and/or encapsulate it within the LinkedList class itself.

class LinkedList:
    """
    A data structure providing O(1)-time insertion/deletion of items
    to/from the head and tail of the list.
    """

    class _Node:
        def __init__(self, value=None):
            self._value = value
            self._next = None

    # ... remainder of LinkedList class ...

Consider using __slots__ to make you Node class faster and consume less memory:

    class _Node:
        __slots__ = ('_value', '_next')

        def __init__(self, value=None):
            self._value = value
            self._next = None

---

class LinkedList

Why are you storing self._args = args in the constructor? It is never used later on, so is just wasted storage. The if statement is unnecessary, if args is an empty list, iterating over it will iterate zero times. Simply use:

        for val in args:
            self.append(val)

---

Your indexing is complex enough for a special comment describing how they work, so they are complex enough to benefit from a common normalization function. Then you wouldn't need to always test for two values (if index == value or index == value - self.size:); just the one normalized value can be used (if index == value:).

---

Iteration

Something that is always done for collections is iterating over all elements. You should define an __iter__(self) method which returns an iterator for the collection.

Since iteration over a collection can be non-deterministic if the collection changes during iteration, you should track the number of times the collection is modified (insert/remove), memorize that value in the iterator when it is first created, and fast-fail the iterator if the value changes.

---

__repr__(self):

Called by the repr() built-in function to compute the “official” string representation of an object. If at all possible, this should look like a valid Python expression that could be used to recreate an object with the same value (given an appropriate environment). If this is not possible, a string of the form <...some useful description...> should be returned.

Your repr method could use values.append(repr(cur_node.value)) and return 'LinkedList(' + ', '.join(values) + ')' to return a more compliant representation.

Or you could rename the method to __str__(self), and leave the body unchanged.