Bag ADT is same as before. Will call the new class IntLinkedBag to distinguish it.

Here is the list of IntLinkedBag instance variables (private) and methods (public):

IntNode head;
int manyNodes; // node count
IntLinkedBag()
void add(int element)
void addAll(IntLinkedBag addend)
Object clone()
int countOccurrences(int target)
boolean remove(int target)
int size()
static IntLinkedBag union(IntLinkedBag b1,IntLinkedBag b2)
int grab()

* all except "grab" are in IntArrayBag. Grab was added to get randomly-selected bag value. It could have been implemented for IntArrayBag but was not.

* only one constructor. With linked lists, the capacity is limited only by available memory so no constraints are put on the client.

Goal: implement IntLinkedBag methods using IntNode methods when feasible.

Example of non-use: the IntLinkedBag instance variable manyNodes is used despite the fact that IntNode method listLength() would return the same info. However, listLength() is O(n), whereas maintenance of manyNodes variable by the add(), addAll() and remove() methods is O(1).

For reference, here are IntNode method signatures:

Consider implementation of IntLinkedBag methods: add, clone, remove, countOccurrences, grab.

The easy one. Since items are not stored in order, look for O(1) algorithm. For linked list, this means inserting at beginning, end, or current position. Which of these three has an instance variable?

This is example of adding a node at the head, w/o tail reference. Don't forget to increment manyNodes.

Recall that for IntArrayBag, this required two things: one was super.clone() the other was to clone the array. Likewise, for IntLinkedBag we need to call super.clone() then make a copy of the linked list. What happens if this is not done? A linked list can be copied using what IntNode method?

  remove:

Use IntNode.listSearch() to find the targetNode, but then you're past the node who's link needs to be mended. So you cannot use removeNodeAfter.

There is a trick to doing this efficiently, based on the fact that order of the data doesn't matter. Solution:

- copy data from head node into node whose data is being removed: targetnode.setData(head.getData());

- set: head = head.getLink();

You can write it from scratch or use IntNode.listSearch() repeatedly.

Here's the trick: when you send listSearch() a reference to the list head, it doesn't really have to be the actual list head but can be any node in the list. Begin the first search with node head, and begin each subsequent search with the node following the one holding the previous occurrence. Repeat until listSearch returns null.

 grab:

This one merely selects a node at random and returns the integer value stored there. The node is selected by randomly selecting an integer in the range from 1 to manyNodes, then using IntNode.listPosition() to get the node.

Use Math.random() to get a random double from range [0-1), then multiply to expand its range and cast to int.

Random never returns 1, so if you multiply by manyNodes and cast, you'll get a value that ranges from 0 to manyNodes-1. Since list positions range from 1 to manyNodes, you need to add 1 to the result.

 size, addAll, union:

The size method is a no-brainer (accessor method for manyNodes).

Think how you would best use IntNode methods to implement the remaining IntLinkedBag methods: addAll and union.

Hint: addAll uses listCopyWithTail

Hint: union uses addAll

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )