#
Print Statistics

#======================================================================= # Author: Isai Damier # Title: Singly Linked List # Project: geekviewpoint # Package: datastructure # # Description: A LinkedList is a data structure that allows access # to a collection of data using pointers/references. While an # array can also be defined as above, LinkedLists and arrays differ # in how they are stored in memory and in the operations they # allow. Unlike an array that must be stored in a block of memory, # the nodes of a LinkedList can be stored anywhere because each # node has a reference to the node that succeeds it. Because the # nodes are stored so loosely, inserting nodes into a LinkedList # is easy; whereas in an array, all the succeeding elements must # be shifted. Of course, insertion also means changing the size of # the array, which means creating the entire array anew. # # Perhaps the greatest beauty of LinkedList is that it allows # accessing an entire sequence of nodes using only one variable: # a reference to the first node in the sequence. # # Countless operations can be performed on LinkedLists. Following # are a few, ranging from the common to the very interesting. #======================================================================= #===================================================================== # Time Complexity of Solution: # O(n). # # Description: Retrieve the following statistics about this # LinkedList: min_value, max_value, total, size, and avg. # # Technical Details: # #===================================================================== import collections class SinglyLinkedList( object ): def __init__( self ): self.head , self.tail = None, None def printStats( self ) : # min_value, max_value, avg, total, size if None == self.head: return None min_value, max_value, total, size = 0, 0, 0, 0 t = self.head while None != t: if t == self.head: min_value = max_value = self.head.data else: if min_value > t.data: min_value = t.data if max_value < t.data: max_value = t.data total += t.data size += 1 t = t.next return [min_value, max_value, total, size, total / size] class Node( object ): def __init__( self, data, next = None ): self.data = data self.next = next

import unittest from algorithms.SinglyLinkedList import SinglyLinkedList import random class Test( unittest.TestCase ): #===================================================================== # Test of printStats method, of class SinglyLinkedList. #===================================================================== def testPrintStats( self ): tape = [9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11] linkedList = SinglyLinkedList() for i in range( len( tape ) ): linkedList.addToTail( tape[i] ) result = linkedList.printStats() expected = [0, 19, 107, 15, 7] self.assertEquals( expected, result )