Python Data Structures and Algorithms

Getting the size of the list

We would like to be able to get the size of the list by counting the number of nodes. One way we could do this is by traversing the entire list and increasing a counter as we go along:

    def size(self):         count = 0         current = self.tail         while current:             count += 1             current = current.next         return count 

This works, but list traversal is potentially an expensive operation that we should avoid when we can. So instead, we shall opt for another rewrite of the method. We add a size member to the SinglyLinkedList class, initializing it to 0 in the constructor. Then we increment size by one in the append method:

class SinglyLinkedList:     def __init__(self):         # ...         self.size = 0     def append(self, data):         # ...         self.size += 1 

Because ...