Week 8 SLOG: Linked List

From the last week lectures, I learned something about linked list. 

Initially, a linked list is a linear sequence of nodes and we will keep a reference to the front of the sequence. Furthermore, in the lecture, we define two different classes which are LLNode and LinkedList. LLNode represents a single node and LinkedList represents the linked list as a whole.

First of all, we need to define LLNode class, including __init__, __str__ and __eq__ methods:

class LLNode:

     def __init__(self, value, nxt=None):

        ''' (LLNode, object, LLNode) -> NoneType

        Create LLNode (self) with data value and successor nxt.
        '''
        self.value, self.nxt = value, nxt

    def __str__(self):

        ''' (LLNode) -> str

        Return a user-friendly representation of this LLNode.

        >>> n = LLNode(4, LLNode(6))
        >>> print(n)
        4 -> 6 ->|
        '''
        if self.nxt is None:
            return '{} ->|'.format(str(self.value))
        else:
            return '{} -> {}'.format(str(self.value), str(self.nxt))

 def __eq__(self, other):

        ''' (LLNode, object) -> bool

        Return whether LLNode (self) is equivalent to other.

        >>> LLNode(3).__eq__(3)
        False
        >>> n = LLNode(4, LLNode(6))
        >>> n2 = LLNode(4, LLNode(6, None))
        >>> n.__eq__(n2)
        True
        '''
        return (type(self) == type(other) and
                (self.value, self.nxt) == (other.value, other.nxt))

And then we go to define the LinkedList class,  including __init__, __str__, __eq__  and prepend methods:

class LinkedList:
    def __init__(self):
        ''' (LinkedList) -> NoneType

        Create an empty linked list.
        '''
        self.front, self.back = None, None
        self.size = 0

    def __str__(self):
        ''' (LinkedList) -> str

        Return a human-friendly string representation of
        LinkedList (self)

        >>> lnk = LinkedList()
        >>> lnk.prepend(5)
        >>> print(lnk)
        5 ->|
        '''
        return str(self.front)

    def __eq__(self, other):
        ''' (LinkedList, object) -> bool

        Return whether LinkedList (self) is equivalent to
        other.

        >>> LinkedList().__eq__(None)
        False
        >>> lnk = LinkedList()
        >>> lnk.prepend(4)
        >>> lnk2 = LinkedList()
        >>> lnk2.prepend(4)
        >>> lnk.__eq__(lnk2)
        True
        '''
        return (type(self) == type(other) and
                (self.size, self.front) == (other.size, other.front))


    def prepend(self, value):
        ''' (LinkedList, object) -> Nonetype

        Insert value at front of LLNode (self).

        >>> lnk = LinkedList()
        >>> lnk.prepend(0)
        >>> lnk.prepend(1)
        >>> lnk.prepend(2)
        >>> str(lnk.front)
        '2 -> 1 -> 0 ->|'
        >>> lnk.size
        3
        '''
        self.front = LLNode(value, self.front)
        if self.back is None:
            self.back = self.front
        self.size += 1