Home > Assignments > Linked Lists and Patterns

Linked Lists and Patterns

I had trouble with this assignment. I was unsure of what classes we were supposed to be working with: there is List, ListI, ListC, EmptyList, Node, CollectionI. ListC does all the work for you, am I supposed to be using this class then? Well, I hope so, because that’s what I did. Anyways, I decided to implement the Observer, Visitor, and State patterns to work with the ListC and Node classes.

In order to fill my lists with Items, I needed to create an Item to store. I chose to create the Integer class, which implements Item, and is just a class that represents an integer. Therefore, I have lists of Integers, which for all purposes are just integers.

The Observer Pattern. I created a ListObserver that watches a ListC and announces when any Item is being removed from the ListC. Although the idea of having an Observer to be notified when a link is changed or broken is interesting, I had trouble deciding what data the Observer should care about. If a Node is added in the list, all the changed Nodes (the previous Node, the new Node, and the next Node) cannot be given to the Observer; that seems like it would require a big mess of conditionals and spaghetti code for the Observer to handle. The Observer would have to know which Node is now previous to the new Node and announce that. The Observer would have to know which Node is the new Node and announce that. The Observer would have to know which Node is now the next Node and announce that.

That seems too messy for a situation like this, so I just decided that the Observer would receive the Node that is being removed so it could announce “X Node/Item is being removed.” At first, the Observer called the toString() method on the received Node, but that would spit out some memory address or useless identifier. This information could be useful, but for our purposes I just decided to have the Observer spit out the toString() of the received Node’s Item, which in my project is an Integer. The toString() method of an Integer just returns an int.

So, when a Node is removed from a ListC, an Observer receives this Node and announces that Node.getItem().toString() is being removed.

The Visitor Pattern. I chose to create a ReplaceVisitor that is instantiated with 2 integers. The ReplaceV would then traverse through a given ListC and replace all instances of one integer with the other. This is where I was held up from my confusion on what classes we’re supposed to work with for this assignment. Since I was using the ListC class, when the get() method is called, it returns a List, but really that is just a Node. Anyways, the ReplaceV doesn’t mess with the actual Nodes that store the integer to replace, instead it just changes the value of the Item (Integer) that stores the integer that the ReplaceV is to replace. This works, but I would have liked for the ReplaceV to actually remove the entire Node and create a new Node with the different information, then stitch the new Node into the list. If this were the functionality, then the ReplaceV would cause the Observer to be notified.

The State Pattern. Once again, due to my confusion, I decided to implement this pattern into the Node class rather than the ListC class. To exemplify this pattern, I just create some new Nodes and manually stitched them together (rather than using the ListC class). The Node has 2 states: emptyState and fullState. The only method that is contained in these states is getItem(). When a Node has an Item in it, then it is in the fullState. When the Node does not have an Item, it is in the emptyState. When getItem() is invoked on a Node that is in the emptyState, a null is returned and a message is announced that the Node is empty and a null value was returned. When this method is invoked on a Node that is in the fullState, the Item is simply returned.

If the next of a node is set to some node that comes before it, that would form a cycle. How could that be detected? (note to say that node A is “before” B means there is a chain of one or more next pointers stepping from A to B).

Perhaps a DetectCycleVisitor could be used.  The DetectCycleVisitor would start at the beginning of the list and traverse the entire list.  In doing so, it could store every Node that it has been to and verify that its current Node is not one that it has been to already.  If this is true, then the DetectCycleVisitor could break from the recursion loop (which obviously is very important: if there is a cycle in the list, then recursion will continue infinitely) and return the Node that is referenced twice (its current Node).  I don’t have this coded up, but I imagine this could be doable, although storing every Node that the visitor has been to could be a costly process if the list is large enough, as well as having to iterate over all of them from start to finish every time it needs to check that it hasn’t already been to this Node.

This certainly would be a useful visitor though.  This could even work well with the Observer Pattern.  Every time a list changes, it notifies its Observers.  The DetectCycleVisitor could be an Observer, and when notified will tell the list to acceptVisitor(this).  Then, the visitor would traverse the list and look for any cycles that might have been created.  If this is true, the visitor will then announce this, or throw an exception, or somehow remove the cycle.  This is important because if there was a cycle and you did not send in a DetectCycleVisitor, then the next time you try and iterate over the list, an infinite loop will be created and the program will crash.

I think this sounds very cool actually, to use the Observer Pattern and Visitor Pattern together to thwart the possibility of containing cycles in a linked list.  Too bad I didn’t think of this before I did the assignment, I would have implemented this.

Categories: Assignments Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: