CS 241 Lab 3: Linked Lists and Stacks

This assignment follows up on several informal exercises suggested in lecture, so you should have most of this done already. The assignment is partly an exercise in implementation (which should be straightforward) and partly one in design (which may be both a bit harder and more nebulous): the design part comes in specifically in the interface for the linked lists, where you must make some decisions on what is reasonable to include (and to implement).

Linked lists in two styles

Write up the following interfaces and classes for linked lists in Java (some were given in lecture, but make sure you have your own copies, to check that they all compile together):

Be ready to defend decisions you made concerning what operations you included in the interface, and any challenges you encountered in implementing the interface for the two different classes.

Stacks in two styles

Write up the following interfaces and classes for stacks in Java, along with one project implementation (the bracket checker); you may use either implementation to test your project.

Finally, you should provide a short little project which checks for balanced brackets in a string, using a stack. The idea is that an input string (read in via GUI or command line) will contain a mixture of parentheses (round: "()"), brackets (square: "[]") and braces (curly: "{}"), and that your program should either validate that it contains only well-nested, well-sequenced pairs, or indicate what sort of error happens. (Let's allow spaces, too, just to make it easier to write the examples: just ignore the spaces.)

For example, on input "( ()[] { [] () } )" your program would respond that the brackets (in the general sense) are all balanced properly. But on input "( [ ] { ( } ) )" you would report a mis-match at the first closing (curly) brace, since it does not match the preceding open parenthesis.

(How do you implement this? Simple! Just use a stack! Push every "left" bracket and make sure you can pop (off the top of the stack) a corresponding "right" one, i.e., of the corresponding "shape". You should always find a match, never see an empty stack, when matching, and end up with an empty stack at the end. (Why?)