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()

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.