Week7 - LinkedList ADT

Hi Everyone!

This week we learned LinkedList ADT it reminds me of Stack ADT though it was generated from Tree ADT. I am not very good at it right now. We didn't finish this topic in lecture. Therefore, I will only talk about LinkedList's basic definition, its  __init__ method and its difference with Stack. At the end I will share with you my lab work for implementing Queue with LinkedList. I didn't finish the lab work during the lab time, so I spend extra hours to work on that. Any comment will be appreciated.  Hope I can say more in next week's post~

LinkedList Definition:

This kind of ADT is generated from Tree ADT, since we can think the LinkedList as a linear tree --- the tree only has one branch and every node has exactly one child. Therefore a LinkedList is a sequence of list each with a head (value) and a reference to rest (its successors).

LinkedList reminds me of Stack and Queue ADT that we learned from lecture and lab. They have very similar characteristic in the form of a linear "list". In addition, their methods such as __repr__, __eq__, is_empty are very similar. Even though some of these methods only appear in one ADT, I guess these methods can be implemented to other ADTs by the same logic. Therefore, I am not going to talked about them here. I will list the main difference between them as following and I will provide the corresponding functions after. 

__init__ method:

def __init__(self: 'LinkedList', head: object=None,

             rest: 'LinkedList'=None) -> None:

    """Create a new LinkedList"""

    self.empty = (head is None) and (rest is None)

    if not self.empty:

        self.head = head

        if rest is None:

            self.rest = LinkedList()

        else:

            self.rest = rest

I thought this __init__ method has no difference with those __init__ methods we implemented before. However, when I got to preprend method's "self.empty = False" I was confused. I thought the "self.item = item" has already showed that head is not None. But after I delete "self.empty = False" and rerun the code with the same example, I understood that only when self.empty = True, the code under this condition will run, self.item can be assigned with item. Otherwise, values cannot be assigned to variables and both self.head and self.rest are still None, as before.

Prepend Method with self.empty = False:

>>> lnk = LinkedList()

>>> lnk.prepend(7)

>>> lnk

LinkedList(7, LinkedList())

Prepend Method Code without self.empty = False:

>>> lnk = LinkedList()

>>> lnk.prepend(7)

>>> lnk

LinkedList()

LinkedList vs Stack: 

Stack: add item to the end, delete item from the end

LinkedList: add item to the front, delete item from the end

As for a LinkedList, the most difficult part I feel is their are linked. In Stack, we can add or delete item by simply attach or detach. In LinkedList, every time we change it, we need to consider both the head and the rest, modify the LinkedList as a whole.

Stack (push, pop):

def push(self: 'Stack', o: object) -> None:

        """Place o on top of the stack."""

        self._data.append(o)

def pop(self: 'Stack') -> object:

        """Remove and return the top item."""

        return self._data.pop()

LinkedList(prepend, decapitate):

def prepend(self: 'LinkedList', head: object) -> None:

    """Add new head to front of self """

    self.head, self.rest, self.empty = head, copy(self), False    

def decapitate(self: 'LinkedList') -> None:

    """Delete head from LinkedList self."""

    if self.empty:

        raise Exception("Can't decapitate empty list!")

    elif not self.rest.empty:

        self.head, self.rest = self.rest.head, self.rest.rest

    else: #self.rest.empty

        self.empty = True #if delete this line,  AttributeError: self has no attribute head

        del(self.head)

        del(self.rest)

*The logic for decapitate is first check if the LinkedList is empty, if it's empty raise error. If it's not empty, then we check if self.rest is empty. If self.rest is empty, the if we decapitate the LinkedList it will be empty. Therefore, we let self.empty = True, and then delete self.head and self.rest. If self.rest is not empty, then decapitate is equivalent to shift the LinkedList one unit to the left. Therefore, self.rest.head become self.head, and self.rest.rest = self.rest.

Implement Queue with LinkedList:

Queue ADT we've seen in our first lab, but at that time we implemented with reference to Stack ADT. In this week's lab, we implemented it with a LinkedList.

Queue: add item to the end, delete item from front

Queue(enqueue, dequeue) *implement by a linkedlist:

    def enqueue(self: 'Queue', item: object) -> None:

        """ Add item to the back"""

        if self.linked_list.empty:

            self.linked_list.prepend(item)

        else:

            self.back = self.back.rest

            self.back.prepend(item)

    def dequeue(self: 'Queue') -> None:

        """ Delete item from the front"""

        a = self.front()

        self.linked_list.decapitate()

        return a

We went to skiing during the reading week~ How's everyone's vacation?
I think the midterm is ok and I did well. How does everyone feel >< ?

Hope I will be more familiar with LinkedList next week~ See you there!