5
\$\begingroup\$

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

Note this is an edit from the original post: Linked List implementation in Python

Have made the following edits to the code according to the answer by @AJNeufeld:

  1. Made Node class & its attributes private
  2. Added __slots__ to save memory
  3. Added docstrings for all methods - including one for class that explains the assumed structure and indexing
  4. Removed unnecessary attribute self._args
  5. Added private helper methods:
    1. _is_head(self, index)
    2. _is_tail(self, index)
    3. _get_values(self)
  6. Made __repr__(self) in accordance with Python Standard
  7. Added __str__(self) to represent "Linking values"
  8. Added iteration protocol
    • I think the way I built it is O(n^2) and wondering if there is a faster implementation?
    • I did not account for the container size changing through iteration? Any hints on this?
    • Also is anything ever put in the __iter__(self) method, or should it just trivially return the object?

Please find below the new implementation

class Linkedlist:
    """A linear container data structure that provides O(1) time insertion/deletion of items
    to/from the head and tail of the sequence of values.

    Utilizes _Node object as underlying data structure
    ----------------------------------------------------
    Structure of class is as follows:

    Index 0: 1st Node <- Head Node
    Index 1: 2nd Node
    Index 2: 3rd Node
    ...
    Index n - 1: Nth Node <- Tail Node
    ----------------------------------------------------
    Methods:
    1). __getitem__(self, index)

        Time Complexity: O(n)
        Space Complexity: O(1)

    2). __delitem__(self, index)

        Time Complexity: O(n)
        Space Complexity: O(1)

    3). __iter__(self)

        Time Complexity: O(n^2)
        Space Complexity: O(1)

    4). __repr__(self)

        Time Complexity: O(n)
        Space Complexity: O(n)

    5). __str__(self)

        Time Complexity: O(n)
        Space Complexity: O(n)

    6). append(self, value)

        Time Complexity: O(1)
        Space Complexity: O(1)

    7). prepend(self, value)

        Time Complexity: O(1)
        Space Complexity: O(1)

    8). insert(self, value, index)

        Time Complexity: O(n)
        Space Complexity: O(n)
    """

    class _Node:
        """Data structure used to implement Linked List - has fields:
        1. Data value
        2. Pointer to next node
        """

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

            self._value = value
            self._next = None

    def __init__(self, *args):
        self.head = self._Node()
        self.tail = self.head
        self._size = 0
        self._iter_counter = 1
        for val in args:
            self.append(val)

    def __len__(self):
        """Returns number of non-empty nodes in Linked List"""
        return self._size

    def _get_prev_node(self, index):
        """helper method to obtain Node previous to given index in O(n) time
        i.e. if index is 1, will return 1st Node
        i.e. if size of linked list is 6 & index is -3, will return 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 _is_head(self, index):
        """Helper method to determine if given index is head node"""
        if index >= self._size or index < -self._size:
            raise IndexError
        return index == 0 or index == -self._size

    def _is_tail(self, index):
        """Helper method to determine if given index is tail node"""
        if index >= self._size or index < -self._size:
            raise IndexError
        return index == -1 or index == self._size - 1

    def _get_values(self):
        """Helper method to generate string values of all node values"""
        cur_node = self.head
        for _ in range(self._size):
            yield str(cur_node._value)
            cur_node = cur_node._next

    def __getitem__(self, index):
        """Getter method to obtain value of a node at given index in O(1) time - this is considering that finding the node is encapsulated by helper method self._get_prev_node(index)
        """
        if self._is_head(index):
            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):
        """Method to delete value of a node at given index in O(1) time - this is considering that finding the node is encapsulated by helper method self._get_prev_node(index)
        """
        if self._is_head(index):
            self.head = self.head._next
        else:
            prev_node = self._get_prev_node(index)
            prev_node._next = prev_node._next._next
            if self._is_tail(index):
                self.tail = prev_node
        self._size -= 1

    def __iter__(self):
        """Returns iterator object which user can iterate through"""
        return self

    def __next__(self):
        """Loops through iterator returning each Node value"""
        # TODO See if there's a way to improve iteration speed from quadratic to linear
        cur_node = self.head
        if self._iter_counter > self._size:
            self._iter_counter = 1
            raise StopIteration
        prev_node = self._get_prev_node(self._iter_counter)
        self._iter_counter += 1
        return prev_node._value

    def __repr__(self):
        """Provides valid Python expression that can be used to recreate an object with the same value"""
        values = ', '.join(self._get_values())
        cls_name = type(self).__name__
        return f'{cls_name}({values})'

    def __str__(self):
        """Displays printable representation of Linked List"""
        return ' -> '.join(self._get_values())

    def append(self, value):
        """Inserts node with given value to end of Linked List in O(1) time"""
        if self.head._value is None:
            self.head._value = value
        else:
            new_node = self._Node(value)
            self.tail._next = new_node
            self.tail = new_node
        self._size += 1

    def prepend(self, value):
        """Inserts node with given value to front of Linked List in O(1) time"""
        if self.head._value is None:
            self.head._value = value
        else:
            new_node = self._Node(value)
            new_node._next = self.head
            self.head = new_node
        self._size += 1

    def insert(self, value, index):
        """Inserts node with given value at a given index of Linked List in O(n) time.
        If insertion occurs at head or tail of Linked List, operation becomes O(1).
        n := len(self)
        * Index must be in interval [-n, n]
        """
        if abs(index) > self._size:
            raise IndexError
        elif self._is_head(index):
            self.prepend(value)
        elif index == self._size:
            self.append(value)
        else:
            prev_node = self._get_prev_node(index)
            new_node = self._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 1st 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()
\$\endgroup\$
1
\$\begingroup\$

I think you’ve misunderstood the purpose of """docstrings""". If someone using your code types help(LinkedList), they will get the contents of the class’s docstring and the public member docstrings, formatted together into one long output string describing (ideally) how to use the class and its member functions. The internal details of how the class works should not be included.

Moreover, the class docstring should not repeat the information given in a member function. For example, you don’t need to document LinkedList.append in the LinkedList docstring, because help(LinkedList) automatically also output the help for help(LinkedList.append).


Yes, your __iter__ implementation is \$O(n^2)\$. Instead of returning an iterator Object, you’ve returned the original list, and made the original list implement the iterator protocol. This means you cannot have two iterators going at the same time. Also, you cannot iterate halfway through the list, stop and then start a new iteration from the beginning.

You should either create a new class LinkedList._Iter object (which implements the iterator protocol) and return that from __iter__ or, use the same technique you used in _get_values() and return a generator that yields successive values from the list. In either case, these returned objects/generators would be independent; you could have multiple iterations running separately, and/or abandoned halfway through iteration without messing up future iterations.


Edge case:

  • start with empty list: head = tail = empty-node
  • append one item: head = tail = node-with-value
  • delete element 0: head = None; tail = node-with-value
  • every subsequent operation (other than len()) will now raise an exception due to referencing an attribute of self.head, which is now None.
\$\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.