first part

# Merges two sorted lists to create and return a new sorted list.

def mergeSortedLists( listA, listB ) : # Create the new list and initialize the list markers.

newList = list() a=0 b=0

# Merge the two lists together until one is empty.

listA = [1, 3, 5, 7, 9] listB = [2, 4, 6, 8, 10] 

whilea

a b

list_b

 newList.append( listA[a] ) 

a += 1 else :

 newList.append( listB[b] ) b += 1 

list_a

# If listA contains more items, append them to newList. 

whilea

# Or if listB contains more items, append them to newList. 

whileb

return newList

second part

1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 

# Implements the Bag ADT using a singly linked list. 

class Bag : # Constructs an empty bag.

def __init__( self ): self._head = None self._size = 0

 # Returns the number of items in the bag. 

def __len__( self ): return self._size

 # Determines if an item is contained in the bag. 

def __contains__( self, target ): curNode = self._head while curNode is not None and curNode.item != target :

curNode = curNode.next return curNode is not None

 # Adds a new item to the bag. 

def add( self, item ): newNode = _BagListNode( item ) newNode.next = self._head # Prepend the new node (See earlier code)

 self._head = newNode self._size += 1 

# Removes an instance 

of the item from the bag. 

):

def remove( self, item predNode = None curNode = self._head while curNode is not

None and curNode.item != item : curNode = curNode.next

predNode = curNode 

# The item has to be in the bag to remove it.

assert curNode is not None, "The item must be in the bag."

 # Unlink the node and return the item. 

self._size -= 1 if curNode is head :

self._head = curNode.next # Special case else :

predNode.next = curNode.next return curNode.item

 # Returns an iterator for traversing the list of items. 

def __iter__( self ): return _BagIterator( self._head )

# Defines a private storage class for creating list nodes. 

class _BagListNode( object ): def __init__( self, item ) :

 self.item = item self.next = None 

Test the implementation of the mergeSortedLists() function in Listing 5.9 (page 146) in your book. Demonstrate with several examples that the function behaves as expected. Question 6 Test the implementation of the Bag class in Listing 6.5 (page 166) in your book. Your demonstration must include the iterator for the Bag class! Demonstrate with several examples that the function behaves as expected