Goals
This lab was just me writing down a bunch of questions and suggestions to focus attention
on some key issues from the first three weeks of the course. What are the things
I most want you to be thinking about?
- A class gives you a way to create Abstract Data Types in Java. Recall that ADTs
have two parts: what is the ADT made of (data) and what operations does it support (methods)?
Instance variables answer the question of "what constitutes a Person?" or "what is a Maze made of?"
And public methods represent "what operations can you perform on a Person or a
LinkedList or a Maze?"
When you create a Maze or a Person or whatever, you should imagine that some other programmer
is going to use your code in a separate program. If that's the case, what operations will that
other programmer want and/or need? Mark public the things that hypothetical other programmer needs,
and mark everything else private.
For example, if I as a programmer knew that I could use your
Maze in my cool new game, I would want to have the load, solve, and print methods. But if you
have some sort of internal method that you created to make your computation easier inside
Maze (e.g. void printRow(ArrayList<MazeSquare> row)), I don't really care about that. Also,
I don't want to know whether you used an ArrayList of ArrayLists of MazeSquare or a 2D array of
Strings or whatever to store your Maze data internally. I only want to know whether you can
load it, solve it, and print it for me. So you should mark load, solve, and print public
and mark everything else private so I don't accidentally mess up your Maze-internal computations.
- Start practicing counting operations in every algorithm (even tiny ones). Think about whether
LinkedList's add(String) method takes N steps or just 1 or 2 steps for an N-node list. Think about
how many steps it takes to initialize a Maze. Think about how many steps it takes to search for
a particular string in an ArrayList of strings. That's what Section 2.1 of the textbook is about,
and it will be a big part of our work the rest of the term.
- Think about this: what's the difference between an interface and an implementation?
For example, a Stack<String>'s interface consists of the list of its public method signatures:
public Stack<String>()
public void push(String data)
public String pop()
public String peek()
public int size()
public boolean isEmpty()
But the Stack's implementation, inside its source code, could be based on an ArrayList or a LinkedList
or some other secret approach. Hypothetical programmers using the Stack don't have to worry about
the implementation; they only need to know the interface if they want to incorporate Stack in their programs.
main, public, private, and static
Make copies of your PeopleSorter.java and Person.java files in some temporary directory.
You're going to mess with them.
- Create a main method in Person, and just put a "Hi from Person" print statement in it.
- Comment out everything in PeopleSorter's main method, and put a "Hi from PeopleSorter" print statement there.
- Compile both source files, and run "java PeopleSorter" and "java Person". Did it do what you expected?
- In PeopleSorter's main, instantiate one Person object and print the person's name:
Person p = new Person("Newton", "Isaac", 1642, 12, 25);
System.out.println(p.getFullName());
Then compile and run PeopleSorter. Does it do what you expect?
- Now, still in PeopleSorter's main, add this at the end:
p.givenName = "Fig";
System.out.println(p.getFullName());
What happens if you compile and run PeopleSorter now? Why?
- Take those four lines of code you just added to PeopleSorter's main, and copy them into Person's main.
Then run "javac Person.java" and "java Person". What happens now? Is it different from when you did it
in PeopleSorter? Why?
Complexity examples
Implementing stacks
- Create a new class called Stack. (Don't import Java's Stack class, since you're going to build your own.)
- Give it stub methods for a 0-parameter constructor, size, push, peek, and pop. You can just copy the
method signatures from Java's Stack.
- Give it an instance variable of type LinkedList. (Use your own LinkedList class, since it has a print method
that you can use for testing your stack.)
- Write a main method that (1) instantiates a Stack, (2) pushes a few strings, and (3) calls print on the
LinkedList.
- Implement push by inserting a new element at the front of the LinkedList instance variable.
Test it using your main method. Does the printout look like you expected it to?
- Implement size, peek, and pop by looking at or removing the front node in the LinkedList. Modify main to test those.
Working? Great. Now:
- How many Node assignment statements does push require?
- How manu Node assignment statements does pop require?
Fancier linked lists
- Try modifying your LinkedList class (make a copy! don't mess with the original!) to give it an
instance variable private Node tail that will be null for empty lists, and will point to the
last Node in the list otherwise. Which methods need to change?
- If you have a LinkedList with a tail instance variable, do your answers to the first two questions
under Complexity examples above change?
- Try modifying your LinkedList class to be a doubly linked list. That is, give every Node
a Node previous instance variable that will point to the previous Node in the list.
Which methods will need to change and how?
- For your doubly linked list, do any of the complexities of the methods change?